luogu P2154 [SDOI2009]虔诚的墓主人

下面记一个点上下左右点数分别为\(u_i,d_i,l_i,r_i\)

枚举每个中间点太慢了,考虑枚举两个点之间横的一条线段,这里面的点左边点数目都相同,右边点数目都相同,然后只要查一下区间内\(\sum_{i=x_L+1}^{x_R-1} \binom{u_i}{k}\binom{d_i}{k}\)乘上\(\binom{l_L}{k}\binom{r_R}{k}\)就是这一段的贡献.写的时候按照纵坐标排序枚举点,然后每两个相邻点算区间的答案,区间的\(\binom{u_i}{k}\binom{d_i}{k}\)可以树状数组维护,每次处理完这个纵坐标后进行单点修改即可

#include<bits/stdc++.h>

#define LL long long

#define uLL unsigned long long

#define db double

using namespace std;

const int N=1e5+10;

const LL mod=2147483648;

int rd()

{

	int x=0,w=1;char ch=0;

	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

	return x*w;

}

struct node

{

	int x,y;

	bool operator < (const node &bb) const {return x!=bb.x?x<bb.x:y<bb.y;}

}a[N];

int n,kk,bb[N],m;

LL ans,c[N][11],bt[N],nb[N],cl[N],cr[N];

void add(int x,LL y){while(x<=m) bt[x]=(bt[x]+y)%mod,x+=x&(-x);}

LL gsm(int x){LL an=0;while(x) an=(an+bt[x])%mod,x-=x&(-x);return an;}

int main()

{

	rd(),rd();

	n=rd();

	for(int i=1;i<=n;++i)

	{

		a[i].x=rd(),a[i].y=rd();

		bb[++m]=a[i].y;

	}

	sort(bb+1,bb+m+1),m=unique(bb+1,bb+m+1)-bb-1;

	for(int i=1;i<=n;++i) a[i].y=lower_bound(bb+1,bb+m+1,a[i].y)-bb;

	sort(a+1,a+n+1);

	kk=rd();

	for(int i=0;i<=n;++i)

	{

		c[i][0]=1;

		for(int j=1;j<=i&&j<=kk;++j) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;

	}

	for(int i=1;i<=n;++i) ++cr[a[i].y];

	for(int i=1,j=1;i<=n;++j)

	{

		while(j<n&&a[j+1].x==a[j].x) ++j;

		LL nl=1,nr=j-i;

		for(int k=i;k<j;++k,++nl,--nr)

			ans=(ans+(gsm(a[k+1].y-1)-gsm(a[k].y)+mod)%mod*c[nl][kk]%mod*c[nr][kk]%mod)%mod;

		while(i<=j)

		{

			add(a[i].y,mod-nb[a[i].y]);

			++cl[a[i].y],--cr[a[i].y];

			nb[a[i].y]=c[cl[a[i].y]][kk]*c[cr[a[i].y]][kk]%mod;

			add(a[i].y,nb[a[i].y]);

			++i;

		}

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

luogu P2154 [SDOI2009]虔诚的墓主人

最新文章

热门文章