CF1679C 题解

伞兵二号zja · 2022-05-17 20:58:32 · 个人记录

题意

在 n \times n 的棋盘上，支持三种操作/询问：

• 在给定位置放入一个车

• 删除给定位置的车

• 询问给定子矩阵中是否每格都被至少一个车的攻击范围所覆盖

思路

记询问的子矩阵左上、右下顶点分别为 (x_1,y_1),(x_2,y_2) 。

注意到当满足询问条件时，以下两点须至少符合一点：

因为若存在第 x 行未放入车，且存在第 y 列未放入车，则存在行列交点 (x,y) 不在任何一个车的攻击范围中。

因此我们考虑设计一种数据结构，支持单点修改、区间查询。简单的，树状数组或线段树即可。笔者这里选用线段树。

对于行和列分别维护一棵线段树：

• 每个节点维护所示区间内非零权值的个数 val ，对于叶子节点，额外维护一个值 num ：当前行（列）中车的数目。

• 放入车和删除车的操作，相当于对横纵坐标对应的叶子节点的 num 进行单点修改；

• 查询返回区间 val 值和。若 val=len ，说明区间所示每一行（列）都放入了至少一个车，即符合了询问的条件。

时间复杂度 O(qlogn) ，可以通过本题。

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int M = 1e5 + 10;

struct Segment_Tree {
    int val[M << 2], num[M << 2];

    void build(int p, int l, int r) {
        val[p] = num[p] = 0;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
    }

    void add(int p, int l, int r, int L, int R, int k) {
        if (l == L && r == R) {
            num[p] += k; 
            if (num[p] == 0) val[p] = 0;
            else val[p] = 1;
            return;
        }
        int mid = (l + r) >> 1;
        if (L <= mid) add(p << 1, l, mid, L, R, k);
        else add(p << 1 | 1, mid + 1, r, L, R, k);
        val[p] = val[p << 1] + val[p << 1 | 1];
    }

    int query(int p, int l, int r, int L, int R) {
        if (L <= l && r <= R) return val[p];
        int res = 0, mid = (l + r) >> 1;
        if (L <= mid) res += query(p << 1, l, mid, L, R);
        if (R > mid) res += query(p << 1 | 1, mid + 1, r, L, R);
        return res;
    }

} segx, segy;

int n, q, op;
int x, xx, y, yy;

int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while ((ch > '9' || ch < '0') && ch != '-') ch = getchar();
    if (ch == '-') { ch = getchar(); f = - 1; }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

signed main() {
    n = read(); q = read();
    segx.build(1, 1, n); segy.build(1, 1, n);
    for (int i = 1; i <= q; i++) {
        op = read();
        if (op == 1) {
            x = read(); y = read();
            segx.add(1, 1, n, x, x, 1);
            segy.add(1, 1, n, y, y, 1);
        } else if (op == 2) {
            x = read(); y = read();
            segx.add(1, 1, n, x, x, - 1);
            segy.add(1, 1, n, y, y, - 1);
        } else {
            x = read(); y = read();
            xx = read(); yy = read();
            int ansx = segx.query(1, 1, n, x, xx),
                ansy = segy.query(1, 1, n, y, yy);
            if (ansx == xx - x + 1 || ansy == yy - y + 1) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}