#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<cassert>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second
const int MAXN=300010;
int n, m;
string str;
ll sum(vector<ll>& bit, int r){
ll ret=0;
for(; r>=0; r=(r&(r+1))-1) ret+=bit[r];
return ret;
}
void add(vector<ll>& bit, int r, int delta){
for(; r<(int)bit.size(); r=r|(r+1)) bit[r]+=delta;
}
void add(vector<ll>& bit, int l, int r, int delta){
add(bit, l, delta);
add(bit, r, -delta);
}
struct fen{
vector<int> nd;
vector<ll> e, t;
void su(bool mode, int bl, int br, int delta){
int l = lower_bound(nd.begin(), nd.end(), bl) - nd.begin();
int r = lower_bound(nd.begin(), nd.end(), br) - nd.begin();
if(mode) add(e, l, r, delta);
else add(t, l, r, delta);
}
};
set<int> tur;
bool sw[MAXN];
fen tr[MAXN];
fen combine(fen a, fen b){
fen ret;
int sz=a.nd.size()+b.nd.size();
ret.nd.resize(sz), ret.e.resize(sz), ret.t.resize(sz);
merge(a.nd.begin(), a.nd.end(), b.nd.begin(), b.nd.end(), ret.nd.begin());
return ret;
}
void update(int l, int r, bool mode, int bl, int br, int tm){
for(l+=n, r+=n; l<r; l>>=1, r>>=1){
if(l&1) tr[l++].su(mode, bl, br, tm);
if(r&1) tr[--r].su(mode, bl, br, tm);
}
}
void toggle(int ind, int tm){
if(sw[ind]){
sw[ind]=false;
auto itr=tur.find(ind), nx=next(itr);
int start = itr==tur.begin()? 0 : ((*prev(itr))+1);
int en = ind+1;
int bnd = nx==tur.end()? n : ((*nx)+1);
tur.erase(itr);
update(start, en, 0, en, bnd, tm);
}
else{
sw[ind]=true;
}
}
ll query(int l, int r, int tm){
ll ret=0;
int l0=l;
l+=n;
while(l>0){
auto itr=lower_bound(tr[l].nd.begin(), tr[l].nd.end(), r);
assert(itr!=tr[l].nd.end() && *itr==r);
int pos=itr-tr[l].nd.begin();
ret+=sum(tr[l].e, pos);
ret-=sum(tr[l].t, pos);
l>>=1;
}
auto itr=tur.lower_bound(l0);
if(itr==tur.end() || *itr>=r){
ret+=tm;
}
return ret;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> str;
++n;
vector<pii> qrs(m);
forn(i, m){
string type;
cin >> type;
if(type[0]=='q'){
int a, b; cin >> a >> b; --a, --b;
qrs[i]={a, b};
tr[n+a].nd.PB(b);
}
else{
int a; cin >> a; --a;
qrs[i]={a, -1};
}
}
forn(i, n){
sort(tr[n+i].nd.begin(), tr[n+i].nd.end());
tr[n+i].e.resize(tr[n+i].nd.size());
tr[n+i].t.resize(tr[n+i].nd.size());
}
for(int i=n-1; i>0; --i) tr[i]=combine(tr[i<<1], tr[i<<1|1]);
forn(i, n-1) tur.insert(i), sw[i]=true;
forn(i, n-1) if(str[i]=='1') toggle(i, -1);
forn(i, m){
if(qrs[i].S==-1){
toggle(qrs[i].F, i);
}
else{
ll ans = query(qrs[i].F, qrs[i].S, i);
cout << ans << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
37 ms |
43256 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
122 ms |
98848 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
21460 KB |
Output is correct |
| 2 |
Correct |
13 ms |
21588 KB |
Output is correct |
| 3 |
Correct |
16 ms |
21728 KB |
Output is correct |
| 4 |
Correct |
15 ms |
21844 KB |
Output is correct |
| 5 |
Runtime error |
37 ms |
49328 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
21836 KB |
Output is correct |
| 2 |
Runtime error |
35 ms |
43944 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
37 ms |
43256 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
