#791(Div.2)C 树状数组
作者:
昊子
,
2022-05-15 17:53:05
,
所有人可见
,
阅读 165
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
#define endl '\n'
int n, q;
int tr_row[100005], tr_col[100005];
int st_row[100005], st_col[100005];
int lowbit(int x){
return x & -x;
}
void add_row(int x, int k){
for(int i = x; i <= n; i += lowbit(i))tr_row[i] += k;
}
void add_col(int x, int k){
for(int i = x; i <= n; i += lowbit(i))tr_col[i] += k;
}
int ask_row(int x){
int sum = 0;
for(int i = x; i > 0; i -= lowbit(i))sum += tr_row[i];
return sum;
}
int ask_col(int x){
int sum = 0;
for(int i = x; i > 0; i -= lowbit(i))sum += tr_col[i];
return sum;
}
void solve(){
cin >> n >> q;
int t;
while(q --){
cin >> t;
if(t == 1){
int x, y;
cin >> x >> y;
if(!st_row[x])add_row(x, 1);
if(!st_col[y])add_col(y, 1);
st_row[x] += 1;
st_col[y] += 1;
}
else if(t == 2){
int x, y;
cin >> x >> y;
st_row[x] --;
st_col[y] --;
if(!st_row[x])add_row(x, -1);
if(!st_col[y])add_col(y, -1);
}
else{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int num1 = ask_row(x2) - ask_row(x1 - 1);
int num2 = ask_col(y2) - ask_col(y1 - 1);
if(num1 == (x2 - x1 + 1) || num2 == (y2 - y1 + 1))cout << "YES" << endl;
else cout << "NO" << endl;
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}