树状数组
用树状数组维护一下行和列是否有车存在，为了防止同行或同列有多个车的存在，还要开两个数组去维护同行同列有多少个车的数量，然后在删除和添加时，车的数量 0-1 变换的时候才用树状数组维护
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define pii pair const ll maxn = 2e5 + 10; const ll inf = 1e17 + 10; int r[maxn], v[maxn]; int row[maxn], vol[maxn]; int n, m; inline int lowbit(int x) { return x & (-x); } void add(int x, int val, int* way) { for(int i=x; i<=n; i+=lowbit(i)) way[i] += val; } int query(int x, int* way) { int ans = 0; for(int i=x; i; i-=lowbit(i)) ans += way[i]; return ans; } int main() { scanf("%d%d", &n, &m); while(m--) { int t, a, b, c, d; scanf("%d%d%d", &t, &a, &b); if(t == 3) { scanf("%d%d", &c, &d); int x = query(c, r) - query(a - 1, r); int y = query(d, v) - query(b - 1, v); if(x == c - a + 1 || y == d - b + 1) printf("Yes\n"); else printf("No\n"); } else if(t == 1) { if(++row[a] == 1) add(a, 1, r); if(++vol[b] == 1) add(b, 1, v); } else { if(--row[a] == 0) add(a, -1, r); if(--vol[b] == 0) add(b, -1, v); } } return 0; }