P1884题解

· · 个人记录

题目链接

蒟蒻最近刚学差分，考虑用差分做。 看到1e8的范围，直接枚举T飞，所以离散化（接下来有提到）

（一）二维差分

刚拿到手：这不是二维差分修改的裸题吗？根据差分式子：

d_{i,j}=a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1}

不过这题不需要，因为初始化都是0，所以d也是0。 修改操作：

a_{i,j}=d_{i,j}+d_{i-1,j}+d_{i,j-1}-d_{i-1,j-1}

到这里，假如你能注意到一个细节，题目的坐标并不知真正的左上角和右下角，这里做一下处理，那么恭喜你，{\color{red}60pts}why?由于离散化的局限性，来看下面的一组例子：

分别为离散化前后。发现中间空出一部分未染色，而我们的操作将它染色了！

如何处理：

考虑讲二维前缀和降维打击，变成一维前缀和然后暴力枚举每一行，和二维效果一样。这样的好处就在于可以更方便的（或许二维也可以？会的大佬指点一下）修改每一次操作的边界，让他的右边和下面向内缩，这样原来刚好到现在也不会少，原来少的现在就由于多了一空无法算进答案了。

（女少口阿） 附上代码：

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define repp(i, a, b) for(int i = a; i >= b; i--)
#define ll long long
using namespace std;
ll N;
ll l[1011][4];
ll a[4011], c[4011];
ll f[4011][4011];
int cnta, cntc;
ll ans;
int main(){
//  freopen("f.in","r",stdin);
//  freopen("f.out","w",stdout);
    scanf("%lld",&N);
    rep(i, 1, N){
        scanf("%lld%lld%lld%lld",&l[i][0], &l[i][1], &l[i][2], &l[i][3]);
        rep(j, 0, 3)  a[++cnta] = l[i][j];

    }
    sort(a + 1, a + cnta + 1);
    a[0] = -1;
    rep(i, 1, cnta)if(a[i] != a[i - 1])c[++cntc] = a[i];
    rep(i, 1, N){
        rep(j, 0, 3){
            l[i][j] = lower_bound(c + 1, c + cntc + 1, l[i][j]) - c;
        }
    }
    rep(i, 1, N){
        rep(j, l[i][0], l[i][2]-1){
            f[j][l[i][3]]++; f[j][l[i][1]]--;
        }

    }
    rep(i, 1, cntc){
        rep(j, 1, cntc){
            f[i][j] += f[i][j - 1];
        }
    }
    rep(i, 1, cntc - 1){
        rep(j, 1, cntc - 1){
            if(f[i][j]){
                ans += (long long)((c[i + 1] - c[i]) * (c[j + 1] - c[j]));
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

又用二维做了一遍。。。（好像更方便。。打脸）思路一样，不多解释了，代码：

#include<bits/stdc++.h>
#define ll long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define repp(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
int N;
ll x11[1011], y11[1011];
ll x2[1011], y2[1011];
ll a[4011], c[4011];
int delta[4011][4011];
int f[4011][4011];
int cnta, cntc;
ll ans;
int main(){
    scanf("%d",&N);
    rep(i, 1, N){
        scanf("%lld%lld%lld%lld",&x11[i], &y11[i], &x2[i], &y2[i]);
        x11[i] += 1e7;y11[i] += 1e7;x2[i] += 1e7;y2[i] += 1e7;
        a[++cnta] = x11[i];a[++cnta] = y11[i];a[++cnta] = x2[i];a[++cnta] = y2[i];
    }
    stable_sort(a + 1, a + cnta + 1);
    a[0] = -66666666;
    rep(i, 1, 4 * N)if(a[i] != a[i - 1])c[++cntc] = a[i];

    rep(i, 1, N){
        int xx1 = lower_bound(c + 1, c + cntc + 1, x11[i]) - c;
        int yy1 = lower_bound(c + 1, c + cntc + 1, y11[i]) - c;
        int xx2 = lower_bound(c + 1, c + cntc + 1, x2[i]) - c;
        int yy2 = lower_bound(c + 1, c + cntc + 1, y2[i]) - c;
        delta[xx2 - 1][yy2]++;//主要是这里 
        delta[xx2 - 1][yy1]--;
        delta[xx1 - 1][yy2]--;
        delta[xx1 - 1][yy1]++;
    }
    repp(i, cntc, 1){
        rep(j, 1, cntc){
            f[i][j] = f[i + 1][j] + f[i][j - 1] - f[i + 1][j - 1] + delta[i][j];//递推公式 

        }
    }

    rep(i, 1, cntc - 1){
        rep(j, 1, cntc - 1){
            if(f[i][j]){
                ans += (long long)((c[i + 1] - c[i]) * (c[j + 1] - c[j]));
            }

        }
    }
    printf("%lld",ans);
    return 0;
}