【BZOJ2727】【HNOI2012】双十字

首先把每个点向上向下向左向右能够扩展的最长距离\(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}\)即可

// <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;
}

// <2727.cpp> - Tue Feb 28 09:03:39 2017

// This file is created by XuYike's black technology automatically.

// 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;

}