题解
假如两个区间经过操作之后得到的字符串一样,说明不规则仅出现在两个区间的重合处
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int l0[200005]={0};
int r1[200005]={0};
void solve()
{
int n,m;
cin>>n>>m;
string s;
cin>>s;
s=' '+s;
for(int i=1;i<=n;i++)
{
l0[i]=l0[i-1];
if(s[i]=='0') l0[i]=i;
}
r1[n+1]=n+1;
for(int i=n;i>=1;i--)
{
r1[i]=r1[i+1];
if(s[i]=='1') r1[i]=i;
}
set<pair<int,int>> st;
while(m--)
{
int x,y;
cin>>x>>y;
if(l0[y]>=r1[x])
{
st.insert({r1[x],l0[y]});
}
else st.insert({-1,-1});
}
cout<<st.size()<<'\n';
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
标签:Binary,String,int,cin,st,--,Copying,l0,r1
From: https://www.cnblogs.com/pure4knowledge/p/18309136