容斥原理 get ！

A4paper · 2018-10-14 19:12:08 · 个人记录

上手：

传送门

树状数组 + 容斥

首先，开两棵 BIT 一棵存哪几行被占过，一棵存哪几列被占过。

然后，运用容斥原理，即：

哪几行变成了 1 加上 哪几列变成了 1 再减去重叠的部分，由于重叠的部分被加了两次。所以减去的时候要乘 2

那么问题来了，重叠的部分怎么算呢？

设有 X 列被占，有 Y 行被占，暂且假设每个点的 x,y 都不重复。

那么可以这么想，把这几个点拿出来，横竖划线，形成的交点总数（含本身）为 X * Y

于是就有了下面的式子：

X*(y2-y1+1)+Y*(x2-x1+1)-X*Y*2

但是问题又来了，如果有两个点的行或列重复了（或者两个点根本就是重叠的）怎么办呢？

这一点我想了很久，后来发现如果某一个点为 1 ，它也是可以被占的，但此时该点仍然为 1 ，而它的上下左右都取反了，

先粗略想一下，假设点 p 与要放的点是同一列，那么就相当于把这一列都变了回去,把 p 的位置变成了 1，而列不变，那么对于点 p 就相当于这一列的点数变回了 0 ，而这一行仍为一。

这时问题再次出现了，点 p 变成了 1，但列数变为了 0 ， 为什么会成立呢？

这里可以这么想，把列数变成了 0 ，那就说明这一列上没有点，所以容斥时就不需要扣去这个点了，所以这个点要加上 1 ，正好符合题意。

或者也可以这么想，列数变成了 0 ，所以这一列变了回去这没得说，但这一行并不会改变，所以这一行仍被一个神秘的点 magic （NOIP 2018 初赛的梗）控制着，所以要变成 1 ，此时运用容斥必没有问题，符合题意。

long long Lowbit(long long x)   {return x & -x;}

void add1(long long x, long long w){
    for(;x<=n;x+=Lowbit(x)) tree1[x] += w;
}

long long query1(long long x){
    long long ans = 0;
    for(;x;x-=Lowbit(x)) ans += tree1[x];
    return ans;
}

void add2(long long x, long long w){
    for(;x<=m;x+=Lowbit(x)) tree2[x] += w;
}

long long query2(long long x){
    long long ans = 0;
    for(;x;x-=Lowbit(x)) ans += tree2[x];
    return ans;
}

int main(void)
{
    cin >> n >> m >> q;
    for(long long i=1;i<=q;++i)
    {
        cin >> num;
        if(num == 1)
        {
            long long x,y;
            cin >> x >> y;
            if(!vis1[x])
            {
                vis1[x] = 1;
                add1(x,1);
            }
            else
            {
                vis1[x] = 0;
                add1(x,-1);
            }
            if(!vis2[y])
            {
                vis2[y] = 1;
                add2(y,1);
            }
            else
            {
                vis2[y] = 0;
                add2(y,-1);
            }
        }
        if(num == 2)
        {
            long long x1,x2,y1,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            long long X = query1(x2)-query1(x1-1);
            long long Y = query2(y2)-query2(y1-1);
            cout << X*(y2-y1+1)+Y*(x2-x1+1)-X*Y*2 << endl;
        }
    }
    return 0;
}

树形：

传送门

这是一道树形 DP ，但我看到有大佬用简短的容斥把它解决了。

先理顺一下思路，

对于每个点 u ，若要走 k 步，那我们找与它相邻的点 v ，转移就是 u 走 k 步能到达的所有点权和等于 v 走 k-1 步所能到达的所有的点权和减去 v 向 u 方向走 k-1 步的点权和再加上点 v

然后就是一个容斥 + DP

**C[i][j] 表示点 i 走 j 步能到的点权和，map.P[1/0][j] 表示