题解：P8363 [COI2009] PLAHTE

截至到 2024/11/18，应当是本题断档最优解（？）。有图片为证明。

提供一种普及组选手做法 qwq，供大佬们爆踩。

简单来说，题目就是多次求一个左下角在 (-t, -t)，右上角在 (t, t) 的正方形和 n 个矩形面积交的和。这个正方形随着 t 变大会向着四个象限扩展，不好维护。同一个矩形的交，是可以把这个矩形切成两半再加起来。并且正方形是对称的。所以考虑将所有矩形都切割，翻转到第一象限中。这是平凡的，细节请见代码。接下来只考虑左下角在 (0, 0)，右上角在 (t, t) 的矩形。

这样一个正方形只会在第一象限内扩展，像这样：

其中灰色代表正方形，黄色为要统计的矩形。灰色正方形的对角线在红线上。

现在考虑如何统计答案。

• 一个矩形对答案产生贡献前提是与灰色正方形有交。不难发现充要条件是 \min\{x_1, y_1\} \le t。
• 从图上也容易想到，如果以 (t, t) 为原点建立平面直角坐标系，可以以 (x2, y2) 在哪个象限分别计算贡献。更具体的讨论：

发现进行简单拆分以后，所有问题似乎都变成了 t 和某些矩形元素乘与和的计算。于是可以得到一个大概的思路：用四个集合分别维护四个象限的点。对于每个集合内还要统计以上这些项的和。最后的统计也是平凡的。具体细节见代码 qwq。

现在问题转化为如何对每个点所在象限进行维护。注意到一个点的所在象限随着 t 逐步增大只会有这几种变化：第一到二到三象限；第一到四到三象限；第一到三象限；第二到三象限；第四到三象限。

因此对于第一象限要用两个集合维护，一个集合以 x_2 为关键字从小到大对其中元素进行排序，来处理第一象限到第二、三象限的点；另一个集合以 y_2 为关键字，用来处理第一象限到第四，三象限的点。对于第二象限以 x_2 为关键字，处理到第三象限的点，对于第四象限以 y_2 为关键字。在处理的时候对贡献同时更新即可。

由于每个点最多只会在一个象限中出现/删除一次，如果用 multiset 维护每个象限，那么时间复杂度为 O(n\log_2 n)。

以上说的很笼统。实际上我个人认为当变成了“对各个象限分别统计贡献”的时候，其实已经变成一个大模拟了 qwq。所以详细细节请见下面代码。代码略长，不过相信还是较为清楚的 qwq。

#include <bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
const int N = 8 * 1e5;
il int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
inline void write(ll x)
{
    if(!x) {
        putchar('0');
        return ;
    }
    char f[200];
    ll tmp=x>0?x:-x,cnt=0;
    if(x<0)putchar('-');
    while(tmp>0)f[cnt++]=tmp%10+'0',tmp/=10;
    while(cnt>0)putchar(f[--cnt]);
}
struct node {
    int x1, y1, x2, y2, ind;
} Q[N + 10];
il bool cmp(node &x, node &y) {
    return max(x.x1, x.y1) < max(y.x1, y.y1);
}

int tot = 0, n;

il void ins(int x1, int y1, int x2, int y2) {
    Q[++tot] =(node){x1, y1, x2, y2, tot};
}
il void prep(int x1, int y1, int x2, int y2) {//将一个矩形切割，翻转，使所有矩形都在第一象限。
    vector <node> vec;
    if(x1 <= 0) {
        if(x2 <= 0) vec.push_back((node){-x2, y1, -x1, y2});
        else {
            vec.push_back((node){1, y1, -x1, y2});
            vec.push_back((node){0, y1, x2, y2});
        }
    }
    else vec.push_back((node){x1, y1, x2, y2});

    for(int i = 0; i < vec.size(); i++) {
        if(vec[i].y1 <= 0) {
            if(vec[i].y2 <= 0) ins(vec[i].x1, -vec[i].y2, vec[i].x2, -vec[i].y1);
            else {
                ins(vec[i].x1, 0, vec[i].x2, vec[i].y2);
                ins(vec[i].x1, 1, vec[i].x2, -vec[i].y1);
            }
        }
        else ins(vec[i].x1, vec[i].y1, vec[i].x2, vec[i].y2);
    }
}

bool ifj(int l1, int r1, int l2, int r2) {
    if(r1 < l2 || r2 < l1) return 0;
    else return 1;
} 

struct nodex {
    int x1, y1, x2, y2, ind;
    il bool operator < (const nodex &other) const {
        return x2 < other.x2;
    }
};
struct nodey {
    int x1, y1, x2, y2, ind;
    il bool operator < (const nodey &other) const {
        return y2 < other.y2;
    }
};
multiset <nodex> S1, S4;//S1, T1 均维护第一象限中的点，但是排序关键字不一样
multiset <nodey> T1, S2;//S2 维护第二象限中点，S4 维护第四象限中的点

int bel[N + 10], cnt1 = 0;// bel[i] 代表点 i 在第几象限。这是为了防止一个点被多次统计（比如第一象限的点很有可能在 S1 和 T1 中各被统计一次
ll sum[5][5];//上面式子中的各项和
il void upd(int opt, int x1, int y1, int x2, int y2, int type) {
//把矩形 (x1, y1, x2, y2) 加入（type = 1) 或者删除 (type = -1)，在第 opt 象限
    if(opt == 1) {
        cnt1 += type;//cnt1 是第一象限内的点数
        sum[1][1] += (ll)(x1 - 1) * (ll)(y1 - 1) * (ll)type;//直接统计
        sum[1][2] += (ll)(x1 + y1 - 2) * (ll)type;
    }
    else if(opt == 2) {
        sum[2][1] += (ll)(x2 - x1 + 1) * (ll)type;
        sum[2][2] -= (ll)(x2) * (ll)(y1 - 1) * (ll)type;
        sum[2][3] += (ll)(x1 - 1) * (ll)(y1 - 1) * (ll)type;
    }
    else if(opt == 3) {
        sum[3][1] += (ll)(x2 - x1 + 1) * (ll)(y2 - y1 + 1) * (ll)type;
    }
    else if(opt == 4) {
        sum[4][1] += (ll)(y2 - y1 + 1) * (ll)type;
        sum[4][2] -= (ll)(y2) * (ll)(x1 - 1) * (ll)type;
        sum[4][3] += (ll)(x1 - 1) * (ll)(y1 - 1) * (ll)type;
    }
}

il ll calc(ll t) {//计算所有的贡献
    return t * t * cnt1 - sum[1][2] * t + sum[1][1] +
    t * sum[2][1] + sum[2][2] + sum[2][3] + sum[3][1] +
    t * sum[4][1] + sum[4][2] + sum[4][3];
}
signed main() {
    n = read();
    for(int i = 1, x1, y1, x2, y2; i <= n; i++) {
        x1 = read(), y1 = read(), x2 = read(), y2 = read();
        prep(x1, y1, x2, y2);
    }

    sort(Q + 1, Q + tot + 1, cmp);//将所有点先按照 max(x1, y1) 从小到大排序，这样就可以依次加入了

    int m, i = 1; cin >> m;
    while(m--) {
        int t; t = read();

        while(i <= tot && max(Q[i].x1, Q[i].y1) <= t) {
            if(Q[i].x2 >= t && Q[i].y2 >= t) {//1 象限
                bel[Q[i].ind] = 1;
                S1.insert((nodex){Q[i].x1, Q[i].y1, Q[i].x2, Q[i].y2, Q[i].ind});
                T1.insert((nodey){Q[i].x1, Q[i].y1, Q[i].x2, Q[i].y2, Q[i].ind});
                upd(1, Q[i].x1, Q[i].y1, Q[i].x2, Q[i].y2, 1);
            }
            else if(Q[i].x2 < t && Q[i].y2 >= t) {//2
                bel[Q[i].ind] = 2;
                S2.insert((nodey){Q[i].x1, Q[i].y1, Q[i].x2, Q[i].y2, Q[i].ind});
                upd(2, Q[i].x1, Q[i].y1, Q[i].x2, Q[i].y2, 1);
            }
            else if(Q[i].x2 < t && Q[i].y2 < t) {//3 
                bel[Q[i].ind] = 3;
                upd(3, Q[i].x1, Q[i].y1, Q[i].x2, Q[i].y2, 1);
            }
            else if(Q[i].x2 >= t && Q[i].y2 < t) { //4
                bel[Q[i].ind] = 4;
                S4.insert((nodex){Q[i].x1, Q[i].y1, Q[i].x2, Q[i].y2, Q[i].ind});
                upd(4, Q[i].x1, Q[i].y1, Q[i].x2, Q[i].y2, 1);
            }
            i++;
        }
        while(!S1.empty()) {//一->二，三
            multiset <nodex>::iterator it = S1.begin();
            nodex w = (*it);
            if(bel[w.ind] != 1) {
                S1.erase(it);
                continue;
            }
            if(w.x2 < t && w.y2 >= t) {
                S1.erase(it);
                S2.insert((nodey){w.x1, w.y1, w.x2, w.y2, w.ind}); 
                bel[w.ind] = 2;
                upd(1, w.x1, w.y1, w.x2, w.y2, -1);
                upd(2, w.x1, w.y1, w.x2, w.y2, 1);
            }
            else if(w.x2 < t && w.y2 < t) {
                S1.erase(it);
                bel[w.ind] = 3; 
                upd(1, w.x1, w.y1, w.x2, w.y2, -1);
                upd(3, w.x1, w.y1, w.x2, w.y2, 1);
            }
            else break;
        }

        while(!T1.empty()) {//一->四、三
            multiset <nodey>::iterator it = T1.begin();
            nodey w = (*it);
            if(bel[w.ind] != 1) {
                T1.erase(it);
                continue;
            }
            if(w.x2 >= t && w.y2 < t) {
                T1.erase(it);
                S4.insert((nodex){w.x1, w.y1, w.x2, w.y2, w.ind}); 
                bel[w.ind] = 4;//QAQ 一开始把这里打成 2 调试了 30min，太笨蛋了 QAQ
                upd(1, w.x1, w.y1, w.x2, w.y2, -1);
                upd(4, w.x1, w.y1, w.x2, w.y2, 1);
            }
            else if(w.x2 < t && w.y2 < t) {
                T1.erase(it);
                bel[w.ind] = 3; 
                upd(1, w.x1, w.y1, w.x2, w.y2, -1);
                upd(3, w.x1, w.y1, w.x2, w.y2, 1);
            }
            else break;
        }

        while(!S2.empty()) {//二->三
            multiset <nodey>::iterator it = S2.begin();
            nodey w = (*it);
            if(bel[w.ind] != 2) {
                S2.erase(it);
                continue;
            }
            if(w.x2 < t && w.y2 < t) {
                S2.erase(it);
                bel[w.ind] = 3; 
                upd(2, w.x1, w.y1, w.x2, w.y2, -1);
                upd(3, w.x1, w.y1, w.x2, w.y2, 1);
            }
            else break;
        }

        while(!S4.empty()) {//四->三
            multiset <nodex>::iterator it = S4.begin();
            nodex w = (*it);
            if(bel[w.ind] != 4) {
                S4.erase(it);
                continue;
            }
            if(w.x2 < t && w.y2 < t) {
                S4.erase(it);
                bel[w.ind] = 3;
                upd(4, w.x1, w.y1, w.x2, w.y2, -1);
                upd(3, w.x1, w.y1, w.x2, w.y2, 1); 
            }
            else break;
        }

        write(calc(t));
        putchar('\n');
    }
}