题解 P3221 【[HNOI2012]双十字】

· · 题解

（格式复制过来乱了点，原版在我博客里）

myblog: http://blog.csdn.net/miaomiao\_ymxl/article/details/54908607

思路：

首先因为R与C不确定，所以我们需要将点们放在一个一维数组中，算算编号就好了

接下来记录lr[i]与down[i]分别表示点i最多可以向左右延伸和向下延伸多少个1(不包括自己)

然后我们枚举双十字的下面那个交点，推一推公式：

{注：len是下面横线的长度，top表示能到达的最上的位置（连续的1），j是上面的横线的中心位置}

对于一个点i，它对答案的贡献是：

∑lr[i]len=1min(lr[j],len−1)×down[i]×(j−top)

显然这个min非常恶心，我们考虑把它拆开成下面的样子：

1.当(lr[j] <= len-1) 贡献是∑lr[i]len=1lr[j]×down[i]×(j−top)

2.当(lr[j] > len-1) 贡献是∑lr[i]len=1(len−1)×down[i]×(j−top)

再进一步变形：

1.当(lr[j] <= lr[i]) 贡献是(lr[i]×lr[j]−lr[j]×(lr[j]+1)/2)×down[i]×(j−top)

2.当(lr[j] > lr[i]) 贡献是lr[i]×(lr[i]−1)/2×down[i]×(j−top)

（对于1的解释:lr[i]×lr[j]是总方案数，lr[j]×(lr[j]+1)/2是不合法方案数）

现在，需要解决的是所有带j的式子，我们定义3个树状数组t1, t2, t3，分别记录:

1.−lr[j]∗(lr[j]+1)/2)×(j−top)

2.lr[j]×(j−top)

3.(j−top)

把lr[i]作为位置插入，先枚举列再枚举行，每次注意清空。

并且因为两根横线不能挨在一起，所以枚举点(i, j)插入(i-1, j)的值

代码：

<
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
#define Set(a, v) memset(a, v, sizeof(a))
#define For(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define Forr(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define N (10000+5)
#define NM (1200000+5)
const LL MOD = 1e9+9;
int n, m, lr[NM], L[NM], R[NM], down[NM];
bool is0[NM];
struct Tbit{
    LL c[N];
    void clear(){Set(c, 0);}
    int lowbit(int x){return x&(-x);}
    void add(int x, LL v){
        while(x < N){c[x] = (c[x]+v)%MOD; x += lowbit(x);}
    }
    LL query(int x){
        LL ret = 0;
        while(x > 0){ret = (ret+c[x])%MOD; x -= lowbit(x);}
        return ret;
    }
}t1, t2, t3;
int ID(int x, int y){return m*(x-1)+y;}
inline void init(){
    For(i, 1, n){
        L[ID(i,1)] = !is0[ID(i,1)]; R[ID(i,m)] = !is0[ID(i,m)];
        For(j, 2, m) if(!is0[ID(i,j)]) L[ID(i,j)] = L[ID(i,j-1)]+1;
        Forr(j, m-1, 1) if(!is0[ID(i,j)]) R[ID(i,j)] = R[ID(i,j+1)]+1;
        For(j, 1, m) if(!is0[ID(i,j)]) lr[ID(i,j)] = min(L[ID(i,j)], R[ID(i,j)])-1;
    }
    For(i, 1, m){
        down[ID(n,i)] = !is0[ID(n,i)];
        Forr(j, n-1, 1) if(!is0[ID(j,i)]) down[ID(j,i)] = down[ID(j+1,i)]+1;
        Forr(j, n, 1) if(down[ID(j,i)]) down[ID(j,i)]--;
    }
}
inline void work(){
    int top, now;
    LL ans = 0;
    For(j, 1, m){
        top = 0; t1.clear(); t2.clear(); t3.clear(); 
        For(i, 1, n){
            if(is0[ID(i,j)]){top=i; t1.clear(); t2.clear(); t3.clear(); continue;}
            now = ID(i,j);
            ans += t1.query(lr[now])*down[now]%MOD;
            ans += t2.query(lr[now])*down[now]*lr[now]%MOD;
            ans += (t3.query(m)-t3.query(lr[now]))*lr[now]*(lr[now]-1)/2*down[now]%MOD; ans %= MOD;
            if(i==1) continue;
            now = ID(i-1,j);
            if(lr[now]){
                t1.add(lr[now], -lr[now]*(lr[now]+1)/2%MOD*(i-1-top-1)%MOD);
                t2.add(lr[now], lr[now]*(i-1-top-1)%MOD); t3.add(lr[now], i-1-top-1);
            }
        }
    }
    printf("%lld\n", (ans+MOD)%MOD);
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int cnt1, x, y;
    scanf("%d%d%d", &n, &m, &cnt1);
    For(i, 1, cnt1){scanf("%d%d", &x, &y); is0[ID(x, y)] = true;}
    init(); work();
    return 0;
}
>