CF1849C Binary String Copying

Link

我们想一下，什么时候两种变换是相同的
或者说，这意味着什么。
本题目有特殊性，特殊性就在于只有0和1
对于每一个被改变的区间\([L_i,r_I]\)，从\(l_i\)开始的那一堆0，和从\(r_i\)开始的那一堆1都没变。
所以变化的部分就要从从左往右第一个1，和从右往左第一个0开始算。
这个东西可以预处理出来，然后用set去重就可以了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<bitset>
using namespace std;
int t;
int n,m;
string ss;
set<pair<int,int> > s;
int l[200005];
int r[200005];
int x,y;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		cin>>ss;
		s.clear();
		l[0]=-1;
		r[n-1]=n;
		for(int i=1;i<n;++i){
			l[i]=(ss[i]=='0'?i:l[i-1]);
		}
		for(int i=n-2;i>=0;--i){
			r[i]=(ss[i]=='1'?i:r[i+1]);
		}
		while(m--){
			scanf("%d%d",&x,&y);
			int ll=l[y-1];
			int rr=r[x-1];
			if(ll<rr)
			s.insert({-1,-1});
			else{
				s.insert({ll,rr});
			}
		}
		cout<<s.size()<<endl;
	}
	return 0;
}