解析
很神奇的一道题
关键在于把22的正方形看成一个单位的转化
由于每个22最多有一个国王
因此每个2*2都一定有一个国王
这是本题的关键
个人感觉这个思想很像鸽笼原理
至于后面的线段树就水到渠成了
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const int N=2e5+100;
ll read() {
ll x=0,f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}
while(isdigit(c)) {x=x*10+(c^48);c=getchar();}
return x*f;
}
int n,m,q;
#define mid ((l+r)>>1)
#define ls (k<<1)
#define rs (k<<1|1)
int mn[N<<2],mx[N<<2];
void build(int k,int l,int r){
mn[k]=2e9;mx[k]=-2e9;
if(l==r) return;
build(ls,l,mid);build(rs,mid+1,r);
return;
}
inline void pushup(int k){
mn[k]=min(mn[ls],mn[rs]);
mx[k]=max(mx[ls],mx[rs]);
return;
}
void changemx(int k,int l,int r,int p,int v){
if(l==r){
mx[k]=max(mx[k],v);return;
}
if(p<=mid) changemx(ls,l,mid,p,v);
else changemx(rs,mid+1,r,p,v);
pushup(k);
}
int askmx(int k,int l,int r,int x,int y){
if(x<=l&&r<=y) return mx[k];
int res=-2e9;
if(x<=mid) res=max(res,askmx(ls,l,mid,x,y));
if(y>mid) res=max(res,askmx(rs,mid+1,r,x,y));
return res;
}
void changemn(int k,int l,int r,int p,int v){
if(l==r){
mn[k]=min(mn[k],v);return;
}
if(p<=mid) changemn(ls,l,mid,p,v);
else changemn(rs,mid+1,r,p,v);
pushup(k);
}
int askmn(int k,int l,int r,int x,int y){
if(x<=l&&r<=y) return mn[k];
int res=2e9;
if(x<=mid) res=min(res,askmn(ls,l,mid,x,y));
if(y>mid) res=min(res,askmn(rs,mid+1,r,x,y));
return res;
}
int main(){
n=read();m=read();q=read();
build(1,1,m);
for(int i=1;i<=q;i++){
int x=read(),y=read();
int a=(x+1)/2,b=(y+1)/2;
if(x&1){
if(askmx(1,1,m,b,m)>=a){
for(int j=i;j<=q;j++) printf("NO\n");
return 0;
}
changemn(1,1,m,b,a);
}
else{
if(askmn(1,1,m,1,b)<=a){
for(int j=i;j<=q;j++) printf("NO\n");
return 0;
}
changemx(1,1,m,b,a);
}
printf("YES\n");
}
return 0;
}
/*
*/