【CF1214G】Feeling Good 题解

题目大意

  有一个 $n\times m$ 的黑白棋盘，初始时候每个格子都是白色。
  接下来 $q$ 次操作，每次把第 $a_i$ 行的 $[l_i,r_i]$ 这个区间反色。
  每次操作结束就会问你，是否存在 $x_1,y_1,x_2,y_2$，满足

• $1 \leq x_1 < x_2 \leq n$
• $1 \leq y_1 < y_2 \leq m$
• $(x_1,y_1)$ 与 $(x_2,y_2)$ 同色
• $(x_1,y_2)$ 与 $(x_2,y_1)$ 同色
• $(x_1,y_1)$ 与 $(x_2,y_1)$ 异色（即：对于矩形的四个角，对角同色，同侧异色）

  若存在，则输出其中一组解。

  $n,m \leq 2000,~q \leq 5\times 10^5$

题解

  为什么我想到每一列建一个 bitset 然后搞不出来，结果最后是每一行建一个 bitset 就特 tm 方便

  给每一行维护一个 bitset，表示这一行的染色情况。
  维护很好维护，每次就第 $a_i$ 行异或一段全 $1$ 的东西就好了。

  然后看怎么找答案。如果某两行的 bitset 不是互相包含的关系（假设是第 $x_1$ 行和第 $x_2$ 行），那么存在 $y_1$，它在 $x_1$ 那里为 $1$ 而在 $x_2$ 那里为 $0$，也存在 $y_2$，它在 $x_1$ 那里为 $0$ 而在 $x_2$ 那里为 $1$。那这个 $(x_1,y_1,x_2,y_2)$ 就是答案。

  所以现在是要判断是否存在两行，它们不是互相包含的关系。然后题解给了一个很 nice 的方法，把所有的 bitset 按 size 排序，那么只需判断相邻的是否全都是包含关系即可。若相邻的全是包含关系，则任选两个都是包含关系（因为这形成了一条链），就会无解，否则把不是包含关系的那个相邻对拿出来算答案就行了。
  这个就用两个 set 维护一下，一个维护排序的 bitset，一个维护答案。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxn=2005;

struct BST{
	int i,cnt;
};
bool operator < (const BST &a,const BST &b) {return a.cnt<b.cnt || a.cnt==b.cnt && a.i<b.i;}

int n,m,q;
bitset<maxn> B[maxn],flp[maxn];
set<BST> S;
set<pair<int,int>> Ans;

bitset<maxn> common;
bool cmp(int x,int y)
{
	common=B[x]&B[y];
	return (common!=B[x] && common!=B[y]);
}

void modify(int i,int cnt,int ty)
{
	set<BST>::iterator it=S.find((BST){i,cnt}), mae, tsugi=it;   // 最近好像学日语学疯了
	tsugi++;
	if (it!=S.begin())
	{
		mae=it; mae--;
		int x=mae->i, y=it->i;
		if (ty==-1) Ans.erase(make_pair(x,y));
			else if (cmp(x,y)) Ans.insert(make_pair(x,y));
	}
	if (tsugi!=S.end())
	{
		int x=it->i, y=tsugi->i;
		if (ty==-1) Ans.erase(make_pair(x,y));
			else if (cmp(x,y)) Ans.insert(make_pair(x,y));
	}
	if (it!=S.begin() && tsugi!=S.end())
	{
		int x=mae->i, y=tsugi->i;
		if (ty==1) Ans.erase(make_pair(x,y));
			else if (cmp(x,y)) Ans.insert(make_pair(x,y));
	}
}

bitset<maxn> b1,b2;
int main()
{
	scanf("%d %d %d",&n,&m,&q);
	
	fo(i,1,n) S.insert((BST){i,0});
	fo(i,1,m) flp[i]=flp[i-1], flp[i][i]=1;
	
	while (q--)
	{
		int a,l,r;
		scanf("%d %d %d",&a,&l,&r);
		
		int cnt=B[a].count();
		modify(a,cnt,-1);
		S.erase((BST){a,cnt});
		B[a]^=((flp[r]>>l)<<l);
		cnt=B[a].count();
		S.insert((BST){a,cnt});
		modify(a,cnt,1);
		
		if (Ans.empty()) puts("-1"); else
		{
			set<pair<int,int>>::iterator it=Ans.begin();
			int x1=it->first, x2=it->second;
			common=B[x1]&B[x2];
			b1=B[x1]^common, b2=B[x2]^common;
			int y1=b1._Find_first(), y2=b2._Find_first();
			if (x1>x2) swap(x1,x2);
			if (y1>y2) swap(y1,y2);
			printf("%d %d %d %d\n",x1,y1,x2,y2);
		}
	}
}