【Codeforces 1214G】Feeling Good | Mrsrz's blog

bitset

题目大意：

给定一个 01 矩阵，每次会翻转某行的一个子串。翻转完后要求找到一个子矩阵，其左上角为 $(x_1,y_1)$，右下角为 $(x_2,y_2)$，并且其对角相等，同侧不相等。输出任意方案或表示无解。

题解：

妙 bitset 题。

考虑对每行维护 bitset，就可以方便地进行取反操作。

考虑两行 $a,b$ 能够作为矩阵的上、下边界需要满足的条件，必须满足至少有一个位置，前者为 0 后者为 1，并且至少有一个位置，前者为 1 后者为 0。那么必须满足 $a\not\subset b$ 且 $b\not\subset a$。

而对于三个集合 $a,b,c$，如果 $a\subset b$ 且 $b\subset c$ 那么就有 $a\subset c$。

所以我们按照 bitset 中 1 的个数从小到大排序，然后判断一下相邻两个是否不互相包含就好了。

用 set 存 bitset 对应的行数，按照 1 的个数排序，再用一个 set 存哪些行可能作为答案。

然后询问的时候，随便从答案 set 里找两行，然后要查询列。

我们需要找两个位置，一个在 $a$ 里为 1，$b$ 里为 0，另一个反之。

可以通过位运算方便地搞出有哪些位满足条件。

至于要任意找一个是 1 的位的话，bitset 里有个函数叫做_Find_first，查找第一个 1 的位置，复杂度是 $O(\frac{n}{\omega})$ 的。

总时间复杂度 $O(q(\log n+\frac{m}{\omega}))$。

Code：

#include<iostream>
#include<set>
#include<bitset>
using namespace std;
const int N=2002;
typedef bitset<N>bt;
int n,m,q;
bt b[N],pre[N];int ct[N];
set<pair<int,int> >st,ok;
void erase(int cnt,int x){
    auto it=st.find(make_pair(cnt,x));
    auto it2=it;++it2;
    if(it2!=st.end())ok.erase(make_pair(it->second,it2->second));
    it2=it;
    if(it!=st.begin()){
        --it2;
        ok.erase(make_pair(it2->second,it->second));
        st.erase(it);
    }else{
        st.erase(it);
        return;
    }
    it=it2;
    ++it;
    if(it!=st.end()&&(b[it2->second]&b[it->second])!=b[it2->second])
    ok.insert(make_pair(it2->second,it->second));
}
void insert(int cnt,int x){
    auto it=st.lower_bound(make_pair(cnt,x));
    auto it2=it;
    if(it!=st.begin()){
        --it2;
        ok.erase(make_pair(it2->second,it->second));
    }
    it=st.insert(make_pair(cnt,x)).first;
    it2=it;++it2;
    if(it2!=st.end()&&(b[it->second]&b[it2->second])!=b[it->second])ok.insert(make_pair(it->second,it2->second));
    it2=it;
    if(it!=st.begin()){
        --it2;
        if((b[it->second]&b[it2->second])!=b[it2->second])
        ok.insert(make_pair(it2->second,it->second));
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n;++i)st.insert(make_pair(0,i));
    for(int i=1;i<=m;++i)
    pre[i]=pre[i-1],pre[i][i]=1;
    while(q--){
        int p,l,r;
        cin>>p>>l>>r;
        erase(ct[p],p);
        b[p]^=pre[r]^pre[l-1];
        ct[p]=b[p].count();
        insert(ct[p],p);
        if(ok.empty())cout<<"-1\n";else{
            int x1=ok.begin()->first,x2=ok.begin()->second;
            if(x1>x2)x1^=x2^=x1^=x2;
            int y_1=(b[x1]&(b[x1]^b[x2]))._Find_first();
            int y_2=(b[x2]&(b[x1]^b[x2]))._Find_first();
            if(y_1>y_2)y_1^=y_2^=y_1^=y_2;
            cout<<x1<<' '<<y_1<<' '<<x2<<' '<<y_2<<'\n';
        }
    }
    return 0;
}