题解：CF1679C Rooks Defenders

Yuexingfei_qwq · 2025-01-27 21:06:39 · 题解

一篇无需线段树/树状数组的题解

思路

观察到求能攻击到的不好求，但是可以求攻击不到的。

建立两个结构体 r,c 分别表示行上不能攻击到的和列上不能攻击到的格子。结构体由一个 set 和一个用于记录数字个数的数组 cnt 组成。set 用于记录 cnt 里面出现次数 \ge 1 的数字。

当然，我们需要重构一下 set 的 insert、erase功能，再新加上查询函数。查询函数可以直接用 lower_bound。结构体重构后的代码如下。

struct Info {
    int cnt[110000];
    std::set<int> s;
    /*重构insert和erase*/
    inline bool insert(int x) {//这里的bool是为了做一点优化，改为void也是可以的
        cnt[x]++;
        if (cnt[x] == 1) {
            s.insert(x);
        }
        return 0;
    }
    inline bool erase(int x) {//与上面同理
        cnt[x]--;
        if (!cnt[x]) {
            s.erase(x);
        }
        return 0;
    }

    inline bool query(int l, int r) {//查询函数
        auto x = s.lower_bound(l);
        return *x > r;
    }
} r, c;

主函数的询问里操作一和操作二要和原来反过来，即操作一时要用 erase，操作二时要用 insert。操作三原来怎么查询现在就怎么查询。

AC CODE

#include <bits/stdc++.h>
#define el "\n"
#define sp " "
#define fi first
#define se second
#define inf 1e18
#define r0 return 0
#define int long long
#define F(i, a, b, c) for (int i = a; i <= b; i += c)
#define debug printf ("bug is in here\n")
#define TheEnd continue
#define base(s) s = sp + s
#define lcm(a, b) a * b / __gcd(a, b)
#define setp(x) fixed << setprecision(x)

using namespace std;

typedef long long ll;
typedef string str;
using ull = unsigned ll;

int n, q;
struct Info {
    int cnt[110000];
    std::set<int> s;
    inline bool insert(int x) {
        cnt[x]++;
        if (cnt[x] == 1) {
            s.insert(x);
        }
        r0;
    }
    inline bool erase(int x) {
        cnt[x]--;
        if (!cnt[x]) {
            s.erase(x);
        }
        r0;
    }
    inline bool query(int l, int r) {
        auto x = s.lower_bound(l);
        return *x > r;
    }
} r, c;

signed main(void) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin >> n >> q;
    F(i, 1, n + 1, 1) {
        r.insert(i);
        c.insert(i);
    }
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            cin >> x >> y;
            r.erase(x);
            c.erase(y);
        } else {
            if (op == 2) {
                int x, y;
                cin >> x >> y;
                r.insert(x);
                c.insert(y);
            } else {
                int x, y, x2, y2;
                cin >> x >> y >> x2 >> y2;
                if (r.query(x, x2) || c.query(y, y2)) {
                    cout << "Yes" << el;
                } else {
                    cout << "No" << el;
                }
            }
        }
    }
    r0;
}

AC 记录

完结不散花。