#include <bits/stdc++.h>
using namespace std;
struct segTree{
int *st;
int n;
segTree(int siz){
int x = ceil(log2(siz));
x++;
st=new int[(1<<x)];
fill(st,st+(1<<x),1e9);
n=siz-1;
}
void rupdate(int l, int r, int ind, int i, int val){
if(i<l||i>r){
return;
}
if(l==r){
st[ind]=val;
return;
}
int mid = (l+r)/2;
rupdate(l,mid,ind*2+1,i,val);
rupdate(mid+1,r,ind*2+2,i,val);
st[ind]=max(st[ind*2+1],st[ind*2+2]);
}
void update(int i, int val){
rupdate(0,n,0,i,val);
}
int rquery(int l, int r, int ind, int s, int e){
if(e<l||s>r){
return -1;
}
if(s<=l&&r<=e){
return st[ind];
}
int mid = (l+r)/2;
return max(rquery(l,mid,ind*2+1,s,e),rquery(mid+1,r,ind*2+2,s,e));
}
int query(int l, int r){
return rquery(0,n,0,l,r);
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,q;
cin >> n >> q;
string s;
cin >> s;
segTree st(n);
for(int i = 0;i<n;i++){
if(s[i]=='1'){
st.update(i,0);
}
}
int tim = 0;
while(q--){
tim++;
string quer;
cin >> quer;
if(quer[0]=='q'){
int a,b;
cin >> a >> b;
a--;b-=2;
int mx = st.query(a,b);
cout << max(0,tim-mx) << "\n";
}
else{
int i;
cin >> i;
i--;
st.update(i,tim);
}
}
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... |