C. Binary String Copying
Binary String Copying
缩小每次询问的区间，将他变成真正变化的区间，也就是说找到从 L 开始往后看的第一个 1 ，从R开始往前看的第一个 0
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N=2e5+5;
//左边第一个0,右边第一个1
int pre[N],suf[N];
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T=1;cin>>T;
while(T--){
map<pair<int,int>,int>mp;
int n,m;cin>>n>>m;
string s;cin>>s;
s=" "+s;
int pos=0;
for(int i=1;i<=n;i++){
if(s[i]=='0')pos=i;
pre[i]=pos;
}
pos=n+1;
for(int i=n;i>=1;i--){
if(s[i]=='1')pos=i;
suf[i]=pos;
}
int ans=0;
while(m--){
int l,r;cin>>l>>r;
l=suf[l];r=pre[r];
if(l>=r)l=r=0;
if(!mp[{l,r}])ans++,mp[{l,r}]=1;
}
cout<<ans<<endl;
}
return 0;
}