CF1379F2 Chess Strikes Back (hard version) 题解

题意：

请注意，简单版本和困难版本之间的区别在于，困难版本中不可用的格子可以再次变为可用，而简单版本中则不可以。只有在所有版本都解决后，才能进行破解。

伊尔达和伊万对国际象棋感到厌倦，但他们非常喜欢棋盘，于是他们发明了一种新游戏。棋盘是一个 \(2n \times 2m\) 的棋盘：它有 \(2n\) 行，\(2m\) 列，如果第 \(i\) 行和第 \(j\) 列的格子满足 \(i+j\) 是偶数，那么该格子是白色，否则是黑色。

游戏进行如下：伊尔达将棋盘上的某些白色格子标记为不可用，并要求伊万在剩余的白色格子上放置 \(n \times m\) 个国王，使得没有国王相互攻击。一个国王可以攻击另一个国王，如果它们位于共享一个边或一个角的相邻格子上。

伊尔达想探索不同的格子组合。最初所有格子都标记为可用，然后他有 \(q\) 个查询。在每个查询中，他要么将一个格子标记为不可用，要么将之前不可用的格子标记为可用。在每个查询之后，他想知道是否可以在可用的格子上以期望的方式放置国王。请帮助他！

输入格式：

输入的第一行包含三个整数 \(n,m,q\)（\(1 \leq n, m, q \leq 200,000\)）——棋盘的大小和查询的数量。

接下来是 \(q\) 行，每行包含一个查询的描述：两个整数 \(i\) 和 \(j\)，表示棋盘上的一个白色格子（\(1 \leq i \leq 2n\)，\(1 \leq j \leq 2m\)，\(i + j\) 是偶数）。如果格子 \((i, j)\) 在查询前是可用的，那么它变为不可用。否则，如果该格子不可用，则它变为可用。

输出格式：

输出 \(q\) 行，第 \(i\) 行应该包含伊尔达的第 \(i\) 个查询后的棋盘答案。如果可以在可用的格子上以期望的方式放置国王，则该行应包含 "YES"，否则包含 "NO"。

看题解区有线段树的解法，那我就来讲~~更容易理解~~的 CDQ 分治吧（大雾）

如果把 \(2\times 2\) 的格子看作一格，那么初始情况下每格刚好能放一个国王。

并且由于白色格子只有左上和右下，他们将同时位于左上或右下。

考虑一次操作标记了某个格子的右下角，那么这个格子以及它所有左方或上方的格子的国王站到左上角。

此时任何标记右下角的操作都不会减少被迫站到左上角的国王的个数，反而会增加，不过仍然没有产生冲突。

假设此时有一个标记左上角的操作出现在了已经标记右下角的格子，当然这将导致这一格站不了国王。

那么对于没有撤销操作的情况，我们只需要统计是否有冲突的标记即可。

对于包含撤销操作的情况，例如刚才的那个左上角标记，我们需要消除它造成的冲突。

于是现在题目就变成了，有若干个四维点 \((o,t,x,y)\) ，求出

对于 \(o_i=1\) 的点，满足 \(o_j=2,~t_j \le t_i,~x_j \le x_i,~y_j \le y_i\) 的 \(j\) 的个数。
对于 \(o_i=2\) 的点，满足 \(o_j=1,~t_j \ge y_i,~x_j \ge x_i,~y_j \ge y_i\) 的 \(j\) 的个数。

CDQ分治，启动！

时间复杂度 \(\mathcal{O}(n \log^2 n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(4e5 + 55))

const int M = 400005;
int ans[N], tr[N];
map< int, map<int, char> > vis;
struct node { int op, t, x, y, f; } a[N];
bool cmp1(node x, node y) { return x.t < y.t; }
bool cmp2(node x, node y) { return x.x == y.x ? x.y < y.y : x.x < y.x; }
int lowbit(int x) { return x & (-x); }
void add(int x, int v) { for(int i = x; i <= M; i += lowbit(i)) tr[i] += v; }
int qry(int x, int r = 0) { for(int i = x; i; i -= lowbit(i)) r += tr[i]; return r; }
void cdq(int l, int r)
{
    if(l == r) return;
    int mid = (l + r) >> 1; cdq(l, mid); cdq(mid + 1, r);
    sort(a + l, a + 1 + mid, cmp2); sort(a + 1 + mid, a + 1 + r, cmp2);
    int j = l;
    for(int i = mid + 1; i <= r; i++)
    {
        for(; a[j].x <= a[i].x && j <= mid; j++) if(a[j].op == 1) add(a[j].y, a[j].f);
        if(a[i].op == 2) ans[a[i].t] += a[i].f * qry(a[i].y);
    }
    for(int i = l; i < j; i++) if(a[i].op == 1) add(a[i].y, -a[i].f);
    j = mid;
    for(int i = r; i > mid; i--)
    {
        for(; a[j].x >= a[i].x && j >= l; j--) if(a[j].op == 2) add(a[j].y, a[j].f);
        if(a[i].op == 1) ans[a[i].t] += a[i].f * (qry(M) - qry(a[i].y - 1));
    }
    for(int i = mid; i > j; i--) if(a[i].op == 2) add(a[i].y, -a[i].f);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m, q; cin >> n >> m >> q;
    for(int i = 1, x, y; i <= q; i++)
    {
        cin >> x >> y; int op = (x & 1) ? 1 : 2;
        if(!vis[x][y]) { a[i] = {op, i, x, y, 1}; vis[x][y] = true; }
        else { a[i] = {op, i, x, y, -1}; vis[x][y] = false; }
    }
    sort(a + 1, a + 1 + q, cmp1); cdq(1, q); int sum = 0;
    for(int i = 1; i <= q; i++) { 
        sum += ans[i]; cout << (sum ? "NO" : "YES") << '\n';
    }
    return 0;
}