#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define eb emplace_back
#define em emplace
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;typedef long double ld;typedef unsigned long long ul;typedef unsigned int ui;typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 2e18;
const int inf = 2e9;
template<class T>
void pr(T t) {cerr << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cerr << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cerr << endl;}
int n,q,cur[300010];
tiii seg[1200000];
string in;
void gang(int x, int l, int r, int s, int e, int t){
if(s>e||r<s||e<l) return ;
if(s<=l&&r<=e){
seg[x]=tiii(t,s,e);
return ;
}
gang(x*2,l,(l+r)/2,s,e,t);gang(x*2+1,(l+r)/2+1,r,s,e,t);
}
tiii get(int x, int l, int r, int ind){
if(ind<l||r<ind) return tiii(0,0,0);
if(l==r) return seg[x];
return max({seg[x],get(x*2,l,(l+r)/2,ind), get(x*2+1,(l+r)/2+1,r,ind)});
}
struct Node{
int cnt=0, l=0, r=0, lsum=0, dsum=0;
Node(){}
};
struct SEG{
vector<Node> seg;
SEG(){seg.eb(Node());seg.eb(Node());}
void gang(int x, int l, int r, int ind, int t, int bac){
if(l==r){
if(bac==-1){
seg[x].cnt+=1;
seg[x].lsum+=t;
}
else{
seg[x].cnt--;
seg[x].dsum += (t - bac);
seg[x].lsum -=bac;
}
return ;
}
int m = (l+r)/2;
if(ind<=m){
if(!seg[x].l){
seg[x].l = seg.size();seg.eb(Node());
}
gang(seg[x].l,l,(l+r)/2,ind,t,bac);
}
else{
if(!seg[x].r){
seg[x].r = seg.size();seg.eb(Node());
}
gang(seg[x].r,(l+r)/2+1,r,ind,t,bac);
}
seg[x].cnt = seg[seg[x].l].cnt + seg[seg[x].r].cnt;
seg[x].lsum = seg[seg[x].l].lsum + seg[seg[x].r].lsum;
seg[x].dsum = seg[seg[x].l].dsum + seg[seg[x].r].dsum;
}
ll hap(int x, int l, int r, int ind, ll t){
//prl("hap", x, l, r, ind, t);
if(x==0||ind<l) return 0;
if(r<=ind){
return t * seg[x].cnt - seg[x].lsum + seg[x].dsum;
}
return hap(seg[x].l, l, (l+r)/2,ind, t) + hap(seg[x].r,(l+r)/2+1,r,ind,t);
}
}fen[300010];
void add(int x, int y, int t){
//prl("add", "x=",x,"y=",y,"time=",t);
for(;x<=n;x+=x&-x){
fen[x].gang(1,1,n,y,t,-1);
}
}
void del(int x, int y, int t, int bac){
for(;x<=n;x+=x&-x) fen[x].gang(1,1,n-x+(x&-x)+1,y,t,bac);
}
ll hap(int x, int y, int t){
ll ret=0;
for(;x>=1;x-=x&-x) ret += fen[x].hap(1,1,n-x+(x&-x)+1,y,t);
return ret;
}
int main(){
fastio;
cin>>n>>q;
cin>>in;
int bac = 1;
n++;
for(int i=0;i<n-1;i++){
cur[i+1]=in[i]-'0';
if(in[i]=='0') {
gang(1,1,n,bac,i+1,0);
add(bac,n-i,0);
bac = i+2;
}
}
gang(1,1,n,bac,n,0);
add(bac,1,0);
for(int i=1;i<=q;i++){
string c;int a, b;
cin>>c;
if(c[0]=='q'){
cin>>a>>b;
cout<<hap(a,n-b+1,i)<<"\n";
}
else{
cin>>a;
int l,r,x,t;
if(cur[a]){
tie(t,l,r) = get(1,1,n,a);
del(l,n-r+1,i,t);
gang(1,1,n,l,a,i);
gang(1,1,n,a+1,r,i);
add(l,n-a+1,i);
add(a+1,n-r+1,i);
}
else{
tie(t,l,x) = get(1,1,n,a);
del(l,n-x+1,i,t);
tie(t,x,r) = get(1,1,n,a+1);
del(x,n-r+1,i,t);
gang(1,1,n,l,r,i);
add(l,n-r+1,i);
}
cur[a]=!cur[a];
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
21496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
314 ms |
25464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
22780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
22008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
21496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
