[bzoj1227] [SDOI2009]虔诚的墓主人

　　终于填上了这个万年巨坑....从初二的时候就听说过这题...然后一直不敢写QAQ

　　现在感觉也不是很烦（然而我还是写麻烦了

　　离散化一波，预处理出组合数什么的。。

　　要维护对于当前行，每列上方和下方节点凑出合法方案的个数。

　　然后对于当前行上两棵相邻的常青树，求一下左边、右边合法方案数，乘上中间空的列的合法方案总数就好了。

　　单点修改，区间查询。。我竟然跑去写线段树...懒得改了。。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #define ui unsigned int

 using namespace std;

 const int maxn=,mxnode=maxn<<;

 struct zs{int v,id;}X[maxn],Y[maxn];

 struct poi{int x,y;}a[maxn];

 int lc[mxnode],rc[mxnode],num1[mxnode],num2[mxnode],tot;

 int mp[maxn],st[maxn],top;

 ui sm[mxnode],ans,SM,c[maxn][];

 int i,j,k,n,m,kk,L,R,P;

 int ra,fh;char rx;

 inline int read(){

     rx=getchar(),ra=,fh=;

     while((rx<''||rx>'')&&rx!='-')rx=getchar();

     if(rx=='-')fh=-,rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;

 }

 void build(int a,int b){

     int x=++tot;

     if(a==b){num2[x]=mp[a];return;}

     int mid=a+b>>;

     lc[x]=tot+,build(a,mid),rc[x]=tot+,build(mid+,b);

 }

 void change(int x,int a,int b){

     if(a==b){

         num1[x]++,num2[x]--,sm[x]=c[num1[x]][kk]*c[num2[x]][kk];

         return;

     }

     int mid=a+b>>;

     if(P<=mid)change(lc[x],a,mid);else change(rc[x],mid+,b);

     sm[x]=sm[lc[x]]+sm[rc[x]];

 }

 void query(int x,int a,int b){

     if(L<=a&&R>=b){

         SM+=sm[x];return;

     }

     int mid=a+b>>;

     if(L<=mid)query(lc[x],a,mid);

     if(R>mid)query(rc[x],mid+,b);

 }

 bool cmp(zs a,zs b){return a.v<b.v;}

 bool cmpa(poi a,poi b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}

 int main(){

     n=read(),m=read();

     n=read();

     for(i=;i<=n;i++)X[i].v=read(),Y[i].v=read(),X[i].id=Y[i].id=i;

     kk=read();

     for(i=;i<=n;i++)c[i][]=;

     for(i=;i<=n;i++)for(j=;j<=kk;j++)c[i][j]=c[i-][j]+c[i-][j-];

 //  for(i=1;i<=n;i++)printf("C(%d %d)  %u\n",i,kk,c[i][kk]);return 233;

     sort(X+,X++n,cmp),sort(Y+,Y++n,cmp);int cntx=,cnty=;

     for(i=;i<=n;a[X[i].id].x=cntx,i++)

         if(X[i].v!=X[i-].v||i==)cntx++;

     for(i=;i<=n;a[Y[i].id].y=cnty,mp[cnty]++,i++)

         if(Y[i].v!=Y[i-].v||i==)cnty++;

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

     build(,cnty);

     for(i=;i<=n;){

         int r=i-,top=;

         while(r<n&&a[r+].x==a[i].x)r++,st[++top]=P=a[r].y,change(,,cnty);//,printf("   %d",P);puts("");

         if(top>=(kk<<))

         for(j=kk;j<=top-kk;j++)if(st[j]+<st[j+])

             SM=,L=st[j]+,R=st[j+]-,query(,,cnty),

             ans+=SM*c[j][kk]*c[top-j][kk];

         i=r+;

     }

     printf("%d\n",ans<<>>);

 }