This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb emplace_back
#define mt make_tuple
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
#define ops tuple<int,int,int>
const int N = 3e5 + 1;
typedef pair<int,int> ii;
namespace BIT {
vector<int> val[N];
vector<int> bit[N];
void ini() {
for(int i = 1 ; i < N ; ++i) {
sort(all(val[i]));
val[i].resize(unique(all(val[i])) - val[i].begin());
bit[i].resize(sz(val[i]) + 5);
}
}
void add(int x,int y) {
for(; x < N ; x += x & -x)
val[x].push_back(y);
}
void upd(int x,int y,int v) { //v < 0 -> turn on, v > 0 -> turn off
for(; x < N ; x += x & -x) {
int p = lower_bound(all(val[x]),y) - val[x].begin() + 1;
for(; p > 0 ; p -= p & -p)
bit[x][p] += v;
}
}
int get(int x,int y) {
int ans = 0;
for(; x > 0 ; x -= x & -x) {
int p = lower_bound(all(val[x]),y) - val[x].begin() + 1;
int K = sz(bit[x]);
for(; p < K ; p += p & -p)
ans += bit[x][p];
}
return ans;
}
};
bool on[N];
set<ii> S;
vector<ops> Q[N];
int l[N];
int r[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int q; cin >> q; ++q;
S.insert({-1,-1});
for(int i = 1 ; i <= n ; ++i) {
char c; cin >> c;
if (c == '1') {
ii it = (*--S.end());
if (it.Y == i - 1)
S.erase(it);
else it.X = i;
S.insert({it.X,i});
on[i] = 1;
}
}
S.insert({n + 2,n + 2});
for(ii e : S) if (1 <= e.X && e.Y <= n)
Q[1].pb(1,e.X,e.Y);
string t;
for(int i = 2 ; i <= q ; ++i) {
int x, y; cin >> t >> x;
if (t == "query") {
cin >> y;
l[i] = x;
r[i] = y - 1;
continue;
}
if (on[x]) {
ii it = (*--S.upper_bound({x,x}));
if (it.X < x) S.insert({it.X,x - 1}), Q[i].pb(1,it.X,x - 1);
if (it.Y > x) S.insert({x + 1,it.Y}), Q[i].pb(1,x + 1,it.Y);
S.erase(it); Q[i].pb(0,it.X,it.Y);
}
if(!on[x]) {
auto L = S.upper_bound({x,x});
auto R = L--;
int l = x;
int r = x;
if ((*R).X == x + 1) {
r = (*R).Y;
S.erase(R);
Q[i].pb(0,x + 1,r);
}
if ((*L).Y == x - 1) {
l = (*L).X;
S.erase(L);
Q[i].pb(0,l,x - 1);
}
S.insert({l,r});
Q[i].pb(1,l,r);
}
on[x] ^= 1;
}
for(int i = 1 ; i <= q ; ++i)
for(ops _ : Q[i]) {
int v, x, y;
tie(v, x, y) = _;
BIT::add(x,y);
}
BIT::ini(); Q[1].pb(1,N,0);
for(int i = 1 ; i <= q ; ++i) {
if (Q[i].empty()) {
int ans = BIT::get(l[i],r[i]);
if (ans < 0)
ans += i;
cout << ans << "\n";
}
for(ops _ : Q[i]) {
int v, x, y;
tie(v, x, y) = _;
if (v) BIT::upd(x,y,-i);
else BIT::upd(x,y, i);
}
}
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/
# | 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... |