首先把每个点向上向下向左向右能够扩展的最长距离\(u_i,d_i,l_i,r_i\)求出来。那么一个点作为十字中心的最长长度\(len_i\)为\(min(l_i,r_i)\)。
那么如果我们枚举两个十字的中心\(p,q\),会出现两种情况:
若\(len_p\ge len_q\),那么共有\(\frac{len_q(len_q-1)}{2}u_p d_q\)种双十字
若\(len_p< len_q\),那么共有\(\sum_{i=1}^{len_p}(len_q-i)u_p d_q=len_pu_p len_q d_q-\frac{(len_p)(len_p+1)}{2}u_p d_q\)种双十字
那么用树状数组分别维护一下每个点上面的\(\sum{u_p},\sum{len_p u_p},\sum{\frac{(len_p)(len_p+1)}{2}u_p}\)即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
// <2727.cpp> - Tue Feb 28 09:03:39 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; template<typename T> inline void gg(T &res){ res=0;T fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); res*=fh; } inline int gi(){int x;gg(x);return x;} inline lol gl(){lol x;gg(x);return x;} const int MAXN=10010; const int INF=1e9; const int MOD=1e9+9; vector <int> a[MAXN],l[MAXN],r[MAXN],d[MAXN]; int n,m,c[3][MAXN]; int rt[3],re[3][MAXN]; inline void restore(){ for(int i=0;i<3;i++) while(rt[i])for(int x=re[i][rt[i]--];x<=m;x+=x&-x)c[i][x]=0; } inline void add(int p,int x,int y){ re[p][++rt[p]]=x; for(;x<=m;x+=x&-x)c[p][x]=(c[p][x]+y)%MOD; } inline int get(int p,int x){ int res=0; for(;x;x-=x&-x)res=(res+c[p][x])%MOD; return res; } int main(){ n=gi(),m=gi();int k=gi(); for(int i=0;i<=n+1;i++){ a[i].resize(m+2); l[i].resize(m+2); r[i].resize(m+2); d[i].resize(m+2); for(int j=1;j<=m;j++)a[i][j]=1; } for(int i=1;i<=k;i++){int x=gi(),y=gi();a[x][y]=0;} for(int i=n;i;i--){ for(int j=1;j<=m;j++)l[i][j]=a[i][j]?l[i][j-1]+1:0; for(int j=m;j;j--)r[i][j]=a[i][j]?r[i][j+1]+1:0; for(int j=1;j<=m;j++)d[i][j]=a[i][j]?d[i+1][j]+1:0; for(int j=1;j<=m;j++)l[i][j]=a[i][j]?min(l[i][j],r[i][j])-1:0; } int ans=0; for(int j=1;j<=m;j++){ int u=0; for(int i=1;i<=n;i++){ if(!a[i][j]){restore();u=0;continue;} if(l[i][j]){ int s1=(get(0,m)-get(0,l[i][j]-1)+MOD)%MOD; ans=(ans+1ll*s1*(l[i][j]*(l[i][j]-1)>>1)%MOD*(d[i][j]-1))%MOD; ans=(ans+1ll*get(1,l[i][j]-1)*l[i][j]%MOD*(d[i][j]-1))%MOD; ans=(ans-1ll*get(2,l[i][j]-1)*(d[i][j]-1)%MOD+MOD)%MOD; } if(l[i-1][j]){ add(0,l[i-1][j],u-1); add(1,l[i-1][j],l[i-1][j]*(u-1)); add(2,l[i-1][j],1ll*(l[i-1][j]*(l[i-1][j]+1)>>1)*(u-1)%MOD); } u++; } restore(); } printf("%d",ans); return 0; } |