[cf1379F]Chess Strikes Back

考虑将$(2i-1,2j-1)$和$(2i,2j)$缩为一个点，记作$(i,j)$

对于每一个点，只能选$(2i-1,2j-1)$或$(2i,2j)$（显然不能都选），而这样恰好为$nm$个，因此必须要至少选择一个

对于每一个点，障碍的状态分为以下几类：

1.无障碍，这类点暂时不考虑

2.都有障碍，若存在此类点必然不合法

3.有一个障碍，分两类讨论：

(1)$(2i-1,2j-1)$上有障碍，即这个点只能选$(2i,2j)$，考虑$(i+1,j)$和$(i,j+1)$，也只能选这个点，因此即对于其右下角的点，都要选$(2i,2j)$；

(2)$(2i,2j)$上有障碍，类似的，对于其左上角的点，都要选$(2i-1,2j-1)$

矛盾在于存在一个点$(i_{1},j_{1})$在$(2i_{1}-1,2j_{1}-1)$上有障碍，$(i_{2},j_{2})$在$(2i_{2},2j_{2})$上有障碍，且满足$i_{1}\le i_{2}$、$j_{1}\le j_{2}$，那么对于$([i_{1},i_{2}],[j_{1},j_{2}])$这个矩形就无解了

（其实第2类也可以看作此类情况，即$i_{1}=i_{2}$且$j_{1}=j_{2}$）

通过set，可以求出对于所有$i$，在$(2i-1,2j-1)$上有障碍的最小的$j$和在$(2i,2j)$上有障碍的最大的$j$

对于插入可以很好的支持，即判断新来的点是否会产生即可（通过线段树维护第一个前缀最小值以及第二个后缀最大值），那么删除通过线段树分治即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 200005

 4 #define L (k<<1)

 5 #define R (L+1)

 6 #define mid (l+r>>1)

 7 #define pii pair<int,int>

 8 #define mp make_pair

 9 #define fi first

10 #define se second

11 map<int,int>mat[N<<1];

12 map<int,int>::iterator it;

13 multiset<int>s1[N],s2[N];

14 vector<pii>v[N<<2];

15 pii f[N<<2];

16 int n,m,q,x,y,ans[N];

17 void add(int k,int l,int r,int x,int y,pii z){

18     if ((l>y)||(x>r))return;

19     if ((x<=l)&&(r<=y)){

20         v[k].push_back(z);

21         return;

22     }

23     add(L,l,mid,x,y,z);

24     add(R,mid+1,r,x,y,z);

25 }

26 pii merge(pii x,pii y){

27     return mp(min(x.fi,y.fi),max(x.se,y.se));

28 }

29 pii get(int k){

30     int x=m+1,y=0;

31     if (s1[k].size())x=(*s1[k].begin());

32     if (s2[k].size())y=(*--s2[k].end());

33     return mp(x,y);

34 }

35 void update(int k,int l,int r,int x){

36     if (l==r){

37         f[k]=get(x);

38         return;

39     }

40     if (x<=mid)update(L,l,mid,x);

41     else update(R,mid+1,r,x);

42     f[k]=merge(f[L],f[R]);

43 }

44 pii query(int k,int l,int r,int x,int y){

45     if ((l>y)||(x>r))return mp(m+1,0);

46     if ((x<=l)&&(r<=y))return f[k];

47     return merge(query(L,l,mid,x,y),query(R,mid+1,r,x,y));

48 }

49 void dfs(int k,int l,int r){

50     if (!ans[0])return;

51     for(int i=0;i<v[k].size();i++){

52         x=v[k][i].fi,y=v[k][i].se;

53         if (y&1){

54             s1[(x+1)/2].insert((y+1)/2);

55             if (query(1,1,n,(x+1)/2,n).se>=(*s1[(x+1)/2].begin()))ans[0]=0;

56         }

57         else{

58             s2[x/2].insert(y/2);

59             if (query(1,1,n,1,x/2).fi<=(*--s2[x/2].end()))ans[0]=0;

60         }

61         update(1,1,n,(x+1)/2);

62     }

63     if (l==r)ans[l]=ans[0];

64     else{

65         dfs(L,l,mid);

66         dfs(R,mid+1,r);

67     }

68     for(int i=0;i<v[k].size();i++){

69         x=v[k][i].fi,y=v[k][i].se;

70         if (y&1)s1[(x+1)/2].erase(s1[(x+1)/2].find((y+1)/2));

71         else s2[x/2].erase(s2[x/2].find(y/2));

72         update(1,1,n,(x+1)/2);

73     }

74     ans[0]=1;

75 }

76 int main(){

77     scanf("%d%d%d",&n,&m,&q);

78     for(int i=1;i<=q;i++){

79         scanf("%d%d",&x,&y);

80         if (!mat[x][y])mat[x][y]=i;

81         else{

82             add(1,1,q,mat[x][y],i-1,mp(x,y));

83             mat[x][y]=0;

84         }

85     }

86     for(int i=1;i<=2*n;i++)

87         for(it=mat[i].begin();it!=mat[i].end();it++)

88             if ((*it).se)add(1,1,q,(*it).se,q,mp(i,(*it).fi));

89     for(int i=1;i<=n;i++)update(1,1,n,i);

90     ans[0]=1;

91     dfs(1,1,q);

92     for(int i=1;i<=q;i++)

93         if (ans[i])printf("YES\n");

94         else printf("NO\n");

95 }

巴特西

[cf1379F]Chess Strikes Back

最新文章

热门文章