CF1214G Feeling Good

一、题目

点此看题

二、解法

高维问题首先考虑拆分，本题其实是能拆开的。也就是每一行开一个 ( t bitset)，然后对于两行我们找到位置上的 (01) 对和 (10) 对就可以组成答案。

再翻译一下就是两行 ( t bitset) 都有 (1) 并且出现位置不包含，那么每次修改一行我们考虑它和其它所有行的变化，那么时间复杂度 (O(ncdot mcdot qcdotfrac{1}{w}))

无法优化？注意到本题并不需要求出对数，而只需要找出一个，相当于判断有没有解。可以寻找性质使我们判断的对象变少，注意到我们将所有行按 (1) 的个数排序之后，如果全局有解，那么相邻两行必定会产生解：

证明：直接反证法，如果相邻两行都无解，根据包含关系的传递性两两都应该无解，与全局有解这个条件矛盾。

那么搞一个 ( t set)，每次只需要判断和前驱后继的 ( t bitset) 做一次即可，时间复杂度 (O(frac{nq}{w}))

三、总结

当遇到存在性询问而不是统计性询问的时候需要注意，可能存在结论使得不需要判断全部情况。

本题的逻辑是如果全局存在答案，那么...必定存在答案，我认为这个思路比...更可能得到答案更高级。

#include <cstdio>
#include <bitset>
#include <iostream>
#include <set>
using namespace std;
const int M = 2005;
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,cnt[M];set<pii> s,t;bitset<M> b[M];
int pd(int x,int y)
{
	return (b[x]&b[y])!=b[x];
}
void add(int x)
{
	s.insert(mp(cnt[x],x));
	auto i=s.lower_bound(mp(cnt[x],x)),j=i;i--;j++;
	if(cnt[i->se] && j!=s.end() && pd(i->se,j->se))
		t.erase(mp(i->se,j->se));
	if(cnt[i->se] && pd(i->se,x))
		t.insert(mp(i->se,x));
	if(cnt[x] && j!=s.end() && pd(x,j->se))
		t.insert(mp(x,j->se));
}
void del(int x)
{
	s.erase(mp(cnt[x],x));
	auto j=s.lower_bound(mp(cnt[x],x)),i=j;i--;
	if(cnt[i->se] && pd(i->se,x))
		t.erase(mp(i->se,x));
	if(cnt[x] && j!=s.end() && pd(x,j->se))
		t.erase(mp(x,j->se));
	if(cnt[i->se] && j!=s.end() && pd(i->se,j->se))
		t.insert(mp(i->se,j->se));
}
signed main()
{
	n=read();m=read();k=read();
	for(int i=0;i<=n;i++) s.insert(mp(0,i));
	for(int i=1;i<=k;i++)
	{
		int a=read(),l=read(),r=read();
		bitset<M> tmp;tmp.set();
		tmp>>=(M-(r-l+1));tmp<<=l;
		del(a);b[a]=b[a]^tmp;
		cnt[a]=b[a].count();add(a);
		if(t.empty()) puts("-1");
		else
		{
			int xl=t.begin()->fi,xr=t.begin()->se;
			bitset<M> tmp;tmp=b[xl]^b[xr];
			int yl=(tmp&b[xl])._Find_first();
			int yr=(tmp&b[xr])._Find_first();
			if(xl>xr) swap(xl,xr);
			if(yl>yr) swap(yl,yr);
			printf("%d %d %d %d
",xl,yl,xr,yr);
		}
	}
}