Codeforces Round 791 (Div. 2)

Through_The_Night（蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒻） / 2024-02-26 / 原文

C - Rooks Defenders

线段树模板，维护：1）v：个数， 2）sum：v的个数是否大于0.

// #include"bits/stdc++.h"
#include"iostream"
using namespace std;
const int N = 2e5;
struct Node{
    int l, r, v, sum;
}tr1[N*4], tr2[N*4];
int n, q;


void build(Node tr[], int u, int l, int r){
    // cout<<"||| build :"<<u << ' '<<l<<" "<<r<<endl;
    // tr[u] = {l, r, 0, 0};
    tr[u].l = l;  tr[u].r = r;
    if (l == r)return ;
    int mid = l+r>>1;
    build(tr, u*2, l, mid);
    build(tr, u*2+1, mid+1, r);
}

void modify(Node tr[], int u, int x, int v){
    // cout<<u <<' '<<   << endl;
    if (tr[u].l == tr[u].r){
        tr[u].v += v;
        tr[u].sum = (tr[u].v > 0);
        return ;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (x<=mid)
        modify(tr, u*2, x, v);
    else 
        modify(tr, u*2+1, x, v);

    //  pushup
    tr[u].sum = tr[u*2].sum + tr[u*2+1].sum;
}

int query(Node tr[], int u, int l, int r){
    // cout<<u<<' '<<tr[u].l<<' '<<tr[u].r<<endl;
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    int mid = (tr[u].l + tr[u].r)/2;
    int sum = 0;
    if (l <= mid)
        sum += query(tr, u*2, l, r);
    if (r > mid)
        sum += query(tr, u*2+1, l, r);
    return sum;
}

int main(){   
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> n >> q;
    build(tr1, 1, 1, n), build(tr2, 1, 1, n);
    while(q--){
        int op; 
        cin>>op;
        if (op == 1){
            int x, y;
            cin>>x>>y;
            modify(tr1, 1, x, 1);
            modify(tr2, 1, y, 1);
        }
        else if(op == 2){
            int x, y;
            cin>>x>>y;
            modify(tr1, 1, x, -1);
            modify(tr2, 1, y, -1);

        }
        else{
            int x0, y0, x1, y1;
            cin >> x0 >> y0 >> x1 >> y1;
            if (query(tr1, 1, x0, x1) == x1 - x0 + 1 || query(tr2, 1, y0, y1) == y1 - y0 + 1)
                cout << "Yes" << '\n';
            else cout << "No" << '\n';
        }
    }

    return 0;
}