题目链接：
题意：
思路：思路来自。首先对于每个位置(i,j)用C[i][j]表示该位置同时向左右能延伸的最大长度，用down[i][j]表示向下能延伸的最大长度（其实这里可以用一维的）。然后就是统计。我们一列一列枚举。对于每一列，一行一行来。每次到达一行，(i,k)，若C[i][k]>0就可以统计答案了。若该行的上面有一行j（当然j<i-1了），C[j][k]>0，那么就要增加答案了。设k列最上的1的行为top。可知：
我们不管dowm[i][j]的话，可以得到三个参数：
因此我们只要开三个树状数组维护上面三个值就可以了。
i64 S1[N],S2[N],S3[N];int d[N],n,m,K,L[N],R[N],C[N],down[N];void up(i64 &x,i64 y){ x=(x+y)%mod;}void add(i64 S[],int p,i64 x){ while(p<=m) S[p]=(S[p]+x)%mod,p+=p&-p;}i64 get(i64 S[],int p){ i64 ans=0; while(p>0) up(ans,S[p]),p-=p&-p; return ans;}int ID(int i,int j){ return (i-1)*m+j;}void init(){ int i,j; FOR1(i,n) { L[ID(i,1)]=d[ID(i,1)]?-1:0; R[ID(i,m)]=d[ID(i,m)]?-1:0; for(j=2;j<=m;j++) { if(d[ID(i,j)]) L[ID(i,j)]=-1; else L[ID(i,j)]=L[ID(i,j-1)]+1; } for(j=m-1;j>=1;j--) { if(d[ID(i,j)]) R[ID(i,j)]=-1; else R[ID(i,j)]=R[ID(i,j+1)]+1; } FOR1(j,m) C[ID(i,j)]=min(L[ID(i,j)],R[ID(i,j)]); } FOR1(j,m) { down[ID(n,j)]=d[ID(n,j)]?-1:0; for(i=n-1;i>=1;i--) { if(d[ID(i,j)]) down[ID(i,j)]=-1; else down[ID(i,j)]=down[ID(i+1,j)]+1; } }}int top,pre;void clear(){ top=pre=0; int i; for(i=0;i<=m;i++) S1[i]=S2[i]=S3[i]=0;}i64 ans;void update(i64 x,int i,int j){ i64 temp=get(S1,x)*x%mod-get(S2,x); temp+=x*(x-1)/2%mod*(get(S3,m)-get(S3,x))%mod; temp%=mod; ans=(ans+temp*down[ID(i,j)])%mod;}i64 S(i64 x) {return x*(x+1)/2%mod;}void deal(){ int i,j,k,x; for(j=2;j<m;j++) { clear(); for(i=1;i<n;i++) { if(d[ID(i,j)]) clear(); else if(top==0) top=i; else { if(C[ID(i,j)]>0) update(C[ID(i,j)],i,j); if(pre) { x=C[ID(i-1,j)]; add(S1,x,x*(i-1-top)%mod); add(S2,x,S(x)*(i-1-top)%mod); add(S3,x,i-1-top); pre=0; } if(C[ID(i,j)]) pre=i; } } } PR(ans);}int main(){ RD(n,m,K); int i,x,y; FOR1(i,K) RD(x,y),d[ID(x,y)]=1; init(); deal();}