[SDOI2009]虔诚的墓主人

题解

垃圾luogu数据毁我青春

不知道为什么bz一遍过了luogu上狂wa不停

这题就是让你求一个

[sum_{i=0}^nsum_{j=0}^m[(i,j)notin Tree]binom{up}{k}binom{down}{k}binom{L}{k}binom{R}{k}]

好像没什么好说的呀

我们开一根扫描线，一行一行的扫过去，对于两个相邻的树之间统计答案

就是用树状数组查一个区间和就行了

当然是要离散化的

代码

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
#define lowbit(i) ((i)&(-i))
#define re register
#define maxn 100010
inline int read() {
    int x=0;char c=getchar();while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
std::vector<int> v[maxn];
struct P{int x,y;}a[maxn];
int C[maxn][12],n,m,K,t,ans,b[maxn];
int c[maxn],sz,tot,L[maxn],R[maxn];
inline void add(int x,int val) {for(re int i=x;i<=sz;i+=lowbit(i)) c[i]+=val;}
inline int ask(int x) {int now=0;for(re int i=x;i;i-=lowbit(i)) now+=c[i];return now;}
inline int query(int l,int r) {return ask(r-1)-ask(l);}
inline int cmp(P A,P B) {if(A.x==B.x) return A.y>B.y;return A.x<B.x;}
inline int find(int x) {
    int l=1,r=sz;
    while(l<=r) {
        int mid=l+r>>1;
        if(b[mid]==x) return mid;
        if(b[mid]<x) l=mid+1;else r=mid-1;
    }
    return 0;
}
int main() {
    n=read(),m=read();t=read();
    for(re int i=1;i<=t;i++) a[i].x=read(),a[i].y=read();
    K=read();C[0][0]=1;
    for(re int i=1;i<=t;i++) C[i][0]=C[i][i]=1;
    for(re int i=1;i<=t;i++)
        for(re int j=1;j<=K;j++) {
            if(j>=i) continue;
            C[i][j]=C[i-1][j-1]+C[i-1][j];
        }
    std::sort(a+1,a+t+1,cmp);
    for(re int i=1;i<=t;i++) b[++tot]=a[i].y;
    std::sort(b+1,b+tot+1);sz=std::unique(b+1,b+tot+1)-b-1;
    for(re int i=1;i<=t;i++) a[i].y=find(a[i].y),R[a[i].y]++;
    tot=0;a[0].x=-1;
    for(re int i=1;i<=t;i++) {
        if(a[i].x!=a[i-1].x) ++tot;
        v[tot].push_back(a[i].y);
    }
    for(re int i=1;i<=tot;i++) {
        int up=0,down=(int)v[i].size();
        for(re int j=0;j<v[i].size();j++) {
            up++,down--;
            if(up<K||down<K) continue;
            if(v[i][j]!=v[i][j+1]) ans+=query(v[i][j+1],v[i][j])*C[up][K]*C[down][K];
        }
        for(re int j=0;j<v[i].size();j++) {
            int k=v[i][j];
            add(k,-1*C[L[k]][K]*C[R[k]][K]);
            L[k]++,R[k]--;
            add(k,C[L[k]][K]*C[R[k]][K]);
        }
    }
    printf("%dn",ans&2147483647);
    return 0;
}