题解 CF1214G 【Feeling Good】
skydogli
2020-10-09 17:44:39
题意：一个 $n\times m$ 的 $01$ 矩阵，每次操作为对一行的一段区间取反，每次输出一个矩阵，要求对角值不同,无解输出 $-1$ 。
关键性质：如果存在两行满足这两行的 $1$ 的位置集合没有包含关系，则这两行肯定可以构造出合法的矩阵，构造方法是左右端点分别为两行的第一次单独出现 $1$ 的位置，这个比较显然。
同时，按 $1$ 的个数从小到大排序，如果全局存在满足条件的两行，那么必有相邻两行满足条件。
证明：假设 $i<j<k$ 且 $S_i \cap S_k\neq S_i$ ，如果 $S_i\subset S_j$，则必有 $S_j\cap S_k\neq S_j$，否则 $S_i\cap S_j\ne S_i$。
于是用 ```set``` 维护 $1$ 的个数的大小关系以及 ```bitset``` 判断两行间的包含关系即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
int read(){
int a=0;char c=getchar();
while(c>'9'||c<'0')c=getchar();
while('0'<=c&&c<='9'){
a=a*10+c-48;
c=getchar();
}
return a;
}
#define MN 2005
#define pii pair<int,int>
#define mp make_pair
#define x first
#define y second
bitset<MN>tmp,qwq,bit[MN];
int n,m,q,cnt[MN];
struct cmp{
bool operator () (const int &a,const int &b){
if(cnt[a]==cnt[b])return a<b;
return cnt[a]<cnt[b];
}
};
set<int,cmp>S;
#define itset set<int,cmp>::iterator
int now;
set<pii >mat;
void INS(int a){
S.insert(a);
itset it=S.find(a),il=it,ir=it;
il--;ir++;
if(cnt[*il]&&ir!=S.end()&&((bit[*il]&bit[*ir])!=bit[*il]))
mat.erase(mp(*il,*ir));
if(cnt[*il]&&((bit[*il]&bit[*it])!=bit[*il])){
mat.insert(mp((*il),(*it)));
}
if(ir!=S.end()&&((bit[*it]&bit[*ir])!=bit[*it])){
mat.insert(mp(*it,*ir));
}
}
void DEL(int a){
itset it=S.find(a),il=it,ir=it;
il--;ir++;
if(cnt[*il]&&ir!=S.end()&&((bit[*il]&bit[*ir])!=bit[*il]))
mat.insert(mp(*il,*ir));
if(cnt[*il]&&((bit[*il]&bit[*it])!=bit[*il]))mat.erase(mp((*il),(*it)));
if(ir!=S.end()&&((bit[*it]&bit[*ir])!=bit[*it]))mat.erase(mp(*it,*ir));
S.erase(a);
}
int main(){
n=read();m=read();q=read();
for(int i=0;i<=n;++i)S.insert(i);
for(int i=1;i<=q;++i){
int a=read(),l=read(),r=read();
tmp.set();tmp>>=(MN-(r-l+1));tmp<<=l;
DEL(a);
bit[a]^=tmp;
cnt[a]=bit[a].count();
INS(a);
if(!mat.size())puts("-1");
else{
pii w=*mat.begin();
int x1=w.x,x2=w.y;
qwq=bit[w.x]^bit[w.y];
int y1=(qwq&bit[w.x])._Find_first();
int y2=(qwq&bit[w.y])._Find_first();
if(x1>x2)swap(x1,x2);
if(y1>y2)swap(y1,y2);
printf("%d %d %d %d\n",x1,y1,x2,y2);
}
}
return 0;
}
```