Codeforces #836 : Div2 F. Decent Division

面倒だけど丁寧にやっていく問題。
https://codeforces.com/contest/1758/problem/F

問題

バイナリ文字列Tがある。初期状態で全文字0である。
クエリとして、T中の1文字を指定して0/1反転を行う。
その時、以下の差分を答えよ。

Sは、disjointな区間の集合とする。
各区間[L,R]に対し、T[L],T[L+1],...,T[R]の0/1の個数は等しくなければならない。
また、T中の1はすべてS中の区間のいずれかに含まれなければならない。

解法

0→1になったときは、その分区間を伸ばして0を追加すればよい。
1→0になったときは、区間和を取るSegTreeの二分探索などで区間を縮めればよい。

int N;
int A[1202020];

static ll const def=1<<25;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l || y<=x) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r||y<=x) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+min(ma[k*2],ma[k*2+1]);
		}
	}
};
SegTree_3<int,1<<21> st;

set<pair<int,int>> S;
pair<int,int> inside(int x) {
	auto it=S.lower_bound({x+1,0});
	if(it==S.begin()) return {-1,-1};
	it--;
	if(x<it->second) return *it;
	return {-1,-1};
}

vector<pair<int,int>> addV,delV;

void add(int L,int R) {
	if(L==R) return;
	S.insert({L,R});
	addV.push_back({L,R});
}
void del(int L,int R) {
	S.erase({L,R});
	delV.push_back({L,R});
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,1<<21) st.update(i+1,1<<20,-1);
	
	cin>>N;
	while(N--) {
		cin>>x;
		addV.clear();
		delV.clear();
		if(A[x]==0) {
			auto p=inside(x);
			A[x]^=1;
			st.update(x,1<<20,2);
			int CL,CR;
			if(p.first==-1) {
				auto q=inside(x+1);
				if(q.first==-1) {
					CL=x;
					CR=x+2;
				}
				else {
					del(q.first,q.second);
					CL=x;
					CR=q.second+1;
				}
				q=inside(x-1);
				if(q.first!=-1) {
					del(q.first,q.second);
					CL=q.first;
				}
			}
			else {
				del(p.first,p.second);
				CL=p.first;
				CR=p.second+1;
				auto q=inside(CR);
				if(q.first!=-1) {
					CR=q.second;
					del(q.first,q.second);
				}
				
				CR++;
			}
			auto q=inside(CR);
			if(q.first!=-1) {
				CR=q.second;
				del(q.first,q.second);
			}
			add(CL,CR);
		}
		else {
			auto p=inside(x);
			int CL=p.first;
			int CR=p.second;
			del(CL,CR);
			int cur=st.getval(CL-1,CL);
			int endr=st.getval(CR-1,CR);
			assert(cur==endr);
			A[x]=0;
			st.update(x,1<<20,-2);
			int TR=CR;
			for(i=19;i>=0;i--) if(TR-(1<<i)>CL) {
				if(st.getval(CL-1,TR-(1<<i))<=cur-2) TR-=1<<i;
			}
			add(CL,TR-2);
			add(TR,CR);
		}
		cout<<delV.size()<<endl;
		FORR2(a,b,delV) cout<<a<<" "<<b-1<<endl;
		cout<<addV.size()<<endl;
		FORR2(a,b,addV) cout<<a<<" "<<b-1<<endl;
	}
	
}

まとめ

なんか手間がかかるばかりで面白い印象はないな…。