线段树模板,维护: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; }
标签:791,int,tr,Codeforces,cin,build,tr1,Div,tr2 From: https://www.cnblogs.com/zhangbuang/p/18033243