#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define maxn 5
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
int n, m;
string s;
int mtree[maxn*4], xtree[maxn*4], a[maxn];
void bt(int v, int tl, int tr){
if(tl==tr){
if(s[tl]=='1'){
mtree[v]=INT_MAX;
xtree[v]=0;
}else{
mtree[v]=0;
xtree[v]=-1;
}
return;
}
int tm=(tr+ tl)/2;
bt(v*2, tl, tm);
bt(v*2+1, tm+1, tr);
mtree[v]=min(mtree[v*2], mtree[v*2+1]);
xtree[v]=max(xtree[v*2], xtree[v*2+1]);
}
void upd(int v, int l, int tl, int tr, int j){
if(tl==tr){
if(s[tl]=='1'){
s[tl]='0';
mtree[v]=j-xtree[v]+1;
xtree[v]=-1;
}else{
s[tl]='1';
xtree[v]=j-mtree[v]+1;
mtree[v]=INT_MAX;
}
return;
}
int tm=(tl+tr)/2;
if(tm<l){
upd(v*2+1, l, tm+1, tr, j);
}else{
upd(v*2, l, tl, tm, j);
}
mtree[v]=min(mtree[v*2], mtree[v*2+1]);
xtree[v]=max(xtree[v*2], xtree[v*2+1]);
}
pair<int,int> res(int v, int l, int r, int tl, int tr){
if(tl>r||l>tr){
return {INT_MAX, -1};
}
if(l<=tl&&tr<=r){
return {mtree[v], xtree[v]};
}
pair<int, int> a=res(v*2, l, r, tl, (tl+tr)/2), b=res(v*2+1, l, r,(tl+tr)/2+1, tr);
return {min(a.f,b.f), max(a.s, b.s)};
}
void solve(){
cin >> n >> m;
cin >> s;
string s1;
bt(1, 0, n-1);
for(int i=0; i<m; i++){
cin >> s1;
if(s1[0]=='q'){
int l, r;
cin >> l >> r;
l--; r-=2;
pair<int, int> a=res(1, l, r, 0, n-1);
cout << min(a.f, i+1-a.s);
cout << "\n";
}else{
int x;
cin >> x;
upd(1, x-1, 0, n-1, i);
}
}
}
int main(){
cin.tie(nullptr)->sync_with_stdio(0);
int t=1;
//cin >> t;
while(t--){
solve();
cout << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |