https://www.luogu.org/problem/P2154
下面记一个点上下左右点数分别为 \(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;
- }
来源: http://www.bubuko.com/infodetail-3206321.html