#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pdd pair<ld, ld>
#define ft first
#define sd second
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<class T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N = 300100;
const int M = 2 * N;
const int oo = 2e9;
const ll OO = 1e18;
const int md = 998244353;
const int PW = 233;
set<pii> st;
set<pii>::iterator ite;
vector<pii> qr, pts;
string qu, s;
int q, n;
bool state[N];
struct seg_tree{
vector<int> ys;
vector<ll> st;
seg_tree(): ys(0), st(0) {}
void update(int v, int l, int r, int y, int vl){
if (ys[l] > y) return;
if (ys[r] <= y) {
st[v] += vl;
return;
}
if (l == r) return;
int md = (l + r) >> 1;
update(v + v, l, md, y, vl);
update(v + v + 1, md + 1, r, y, vl);
}
ll get(int v, int l, int r, int y){
ll res = st[v];
if (l == r) return res;
int md = (l + r) >> 1;
if (ys[md + 1] <= y)
res += get(v + v + 1, md + 1, r, y);
else res += get(v + v, l, md, y);
return res;
}
};
seg_tree seg[4 * N];
void build(int v, int l, int r){
if (l == r){
seg[v].ys.PB(pts[l].sd);
seg[v].st.resize(2);
return;
}
int md = (l + r) >> 1;
build(v + v, l, md);
build(v + v + 1, md + 1, r);
merge(all(seg[v + v].ys), all(seg[v + v + 1].ys), back_inserter(seg[v].ys));
seg[v].st.resize(sz(seg[v].ys) * 4 + 3);
}
void update(int v, int l, int r, int min_x, int max_y, int vl){
if (pts[r].ft < min_x) return;
if (pts[l].ft <= min_x) {
seg[v].update(1, 0, sz(seg[v].ys) - 1, max_y, vl);
return;
}
if (l == r) return;
int md = (l + r) >> 1;
update(v + v, l, md, min_x, max_y, vl);
update(v + v + 1, md + 1, r, min_x, max_y, vl);
}
ll get(int v, int l, int r, int min_x, int max_y){
ll res = seg[v].get(1, 0, sz(seg[v].ys) - 1, max_y);
if (l == r) return res;
int md = (l + r) >> 1;
if (MP(min_x, max_y) <= pts[l])
res += get(v + v, l, md, min_x, max_y);
else res += get(v + v + 1, md + 1, r, min_x, max_y);
return res;
}
int main() {
#ifdef _LOCAL
freopen("in.txt","r",stdin); // freopen("output.txt","w",stdout);
#else
// freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
cin >> n >> q >> s;
for (int i = 0; i < n; i++)
state[i] = s[i] - '0';
for (int i = 0; i < q; i++){
cin >> qu;
if (qu[0] == 'q'){
int x, y; cin >> x >> y;
x--; y--;
qr.PB(MP(x, y));
pts.PB(MP(x, y));
} else {
int x; cin >> x;
x--;
qr.PB(MP(x, -228));
}
}
sort(all(pts));
pts.resize(unique(all(pts)) - pts.begin());
build(1, 0, sz(pts) - 1);
for (int i = 0; i < n;){
int j = i;
while (j < n && state[j])
j++;
st.insert(MP(i, j));
i = j + 1;
}
int tim = 1;
for (pii cr : qr) {
// for (auto x : st)
// cerr << x.ft << " " << x.sd << '\n';
// cerr << "\n\n";
if (cr.sd == -228){
int i = cr.ft;
if (!state[i]){
ite = prev(st.upper_bound(MP(i + 1, oo)));
int lf = (*prev(ite)).ft;
int rt = (*ite).sd;
st.erase(MP(lf, i));
st.erase(MP(i + 1, rt));
st.insert(MP(lf, rt));
update(1, 0, sz(pts) - 1, lf, rt, -tim);
update(1, 0, sz(pts) - 1, lf, i, tim);
update(1, 0, sz(pts) - 1, i + 1, rt, tim);
} else {
pii segm = *(prev(st.upper_bound(MP(i + 1, -oo))));
st.erase(segm);
st.insert(MP(segm.ft, i));
st.insert(MP(i + 1, segm.sd));
update(1, 0, sz(pts) - 1, segm.ft, segm.sd, tim);
update(1, 0, sz(pts) - 1, segm.ft, i, -tim);
update(1, 0, sz(pts) - 1, i + 1, segm.sd, -tim);
}
state[i] ^= 1;
} else {
ll res = get(1, 0, sz(pts) - 1, cr.ft, cr.sd);
pii segm = *prev(st.upper_bound(MP(cr.ft, oo)));
if (segm.ft <= cr.ft && segm.sd >= cr.sd)
res += tim;
cout << res << '\n';
}
tim++;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
56696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
249 ms |
63324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
56824 KB |
Output is correct |
| 2 |
Incorrect |
40 ms |
56832 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
57208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
56696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
