#include<bits/stdc++.h>
using namespace std;
struct Node{
int x, y;
int lx, ly;
Node (int _x=0, int _y=0, int _lx=0, int _ly=0){
x=_x, y=_y, lx=_lx, ly=_ly;
}
Node operator+(const Node &b){
return Node(x+b.x, y+b.y);
}
};
struct SegmentTree{
int n;
vector<Node> t;
void init(int _n){
n=_n;
t.assign(4*n+1, Node());
}
void apply(int k, int l, int r, int x, int y){
t[k].x+=(r-l+1)*x;
t[k].y+=(r-l+1)*y;
t[k].lx+=x;
t[k].ly+=y;
}
void push(int k, int l, int r){
if (t[k].lx || t[k].ly){
int mid=(l+r)>>1;
apply(k<<1, l, mid, t[k].lx, t[k].ly);
apply(k<<1|1, mid+1, r, t[k].lx, t[k].ly);
t[k].lx=t[k].ly=0;
}
}
void add(int k, int l, int r, int L, int R, int x, int y){
if (r<L || R<l) return;
if (L<=l && r<=R){
apply(k, l, r, x, y);
return;
}
push(k, l, r);
int mid=(l+r)>>1;
add(k<<1, l, mid, L, R, x, y);
add(k<<1|1, mid+1, r, L, R, x, y);
t[k]=t[k<<1]+t[k<<1|1];
}
Node get(int k, int l, int r, int L, int R){
if (r<L || R<l) return t[0];
if (L<=l && r<=R) return t[k];
push(k, l, r);
int mid=(l+r)>>1;
return get(k<<1, l, mid, L, R)+get(k<<1|1, mid+1, r, L, R);
}
} seg;
struct Event{
int x;
int ly, ry;
int tx, ty;
Event (int _x=0, int _ly=0, int _ry=0, int _tx=0, int _ty=0){
x=_x, ly=_ly, ry=_ry, tx=_tx, ty=_ty;
}
bool operator<(const Event &b){
if (x==b.x){
if (abs(tx+ty)==abs(b.tx+b.ty)) return ly<b.ly;
return abs(tx+ty)>abs(b.tx+b.ty);
}
return x<b.x;
}
};
const int N=3e5+10;
int n, q, ans[N], is_query[N];
string s;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
vector<Event> v;
set<pair<int, int>> st;
map<pair<int, int>, int> mp;
cin >> n >> q >> s;
auto insert=[&](int t, int l, int r){
mp[{l, r}]=t;
st.emplace(l, r);
};
auto erase=[&](int t, int l, int r){
int tt=mp[{l, r}];
v.emplace_back(l, tt, t, 1, 0);
v.emplace_back(r+1, tt, t, 0, -1);
st.erase({l, r});
mp.erase({l, r});
};
s=" "+s;
for (int i=1; i<=n; ++i) if (s[i]=='1'){
int j=i;
while (j<n && s[j+1]=='1') ++j;
insert(1, i, j);
i=j;
}
for (int i=2; i<=q+1; ++i){
string type; cin >> type;
if (type[0]=='t'){
int x; cin >> x;
if (s[x]=='0'){
if (st.empty()){
insert(i, x, x);
}else{
auto it=st.lower_bound({x, x});
int l=x, r=x;
if (it!=st.end() && x+1==it->first){
r=it->second;
erase(i, it->first, it->second);
it=st.lower_bound({x, x});
}
if (it!=st.begin() && (--it)->second==l-1){
l=it->first;
erase(i, it->first, it->second);
}
insert(i, l, r);
}
}else{
auto it=st.lower_bound({x, (int)1e9}); --it;
int l=it->first, r=it->second;
erase(i, l, r);
if (l!=x) insert(i, l, x-1);
if (r!=x) insert(i, x+1, r);
}
s[x]^=1;
}else{
is_query[i]=1;
int l, r; cin >> l >> r; --r;
v.emplace_back(l, -i, -i, 0, 0);
v.emplace_back(r, i, i, 0, 0);
}
}
vector<pair<int, int>> tmp(st.begin(), st.end());
for (auto &i:tmp) erase(q+2, i.first, i.second);
sort(v.begin(), v.end());
seg.init(q+2);
for (auto &i:v){
if (abs(i.tx+i.ty)){
seg.add(1, 1, seg.n, i.ly, i.ry, i.tx, i.ty);
}else{
if (i.ly<0){
ans[-i.ly]=seg.get(1, 1, seg.n, 1, -i.ly-1).x;
}else{
ans[i.ly]+=seg.get(1, 1, seg.n, 1, i.ly-1).y;
}
}
}
for (int i=2; i<=q+1; ++i) if (is_query[i]) cout << ans[i] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
325 ms |
37600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
