#include <bits/stdc++.h>
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
using namespace std;
const int N = 3e5 + 5;
struct ST {
vector<int> vec, t;
void resize() {
t.resize(vec.size() * 4);
}
void upd(int l, int r, int x, int v, int L, int R) {
if (r < vec[L] || l > vec[R])
return;
if (l <= vec[L] && vec[R] <= r) {
t[v] += x;
}
else {
int m = (L + R) >> 1;
upd(l, r, x, v * 2, L, m);
upd(l, r, x, v * 2 + 1, m + 1, R);
}
}
int que(int x, int v, int L, int R) {
if (L == R)
return t[v];
int m = (L + R) >> 1;
if (x <= vec[m])
return que(x, v * 2, L, m) + t[v];
return que(x, v * 2 + 1, m + 1, R) + t[v];
}
} t[N * 4];
struct Q {
int type, x, y;
};
int n, q;
string s;
vector<pair<int, int>> pts;
void build(int v, int L, int R) {
if (L == R) {
t[v].vec = {pts[L].second};
}
else {
int m = (L + R) >> 1;
build(v * 2, L, m);
build(v * 2 + 1, m + 1, R);
set_union(all(t[v * 2].vec),
all(t[v * 2 + 1].vec),
back_inserter(t[v].vec));
}
t[v].resize();
}
void upd(int lx, int rx, int ly, int ry, int add, int v, int L, int R) {
if (rx < pts[L].first || lx > pts[R].first)
return;
if (lx <= pts[L].first && pts[R].first <= rx) {
t[v].upd(ly, ry, add, 1, 0, t[v].vec.size() - 1);
}
else {
int m = (L + R) >> 1;
upd(lx, rx, ly, ry, add, v * 2, L, m);
upd(lx, rx, ly, ry, add, v * 2 + 1, m + 1, R);
}
}
int que(int x, int y, int v, int L, int R) {
int ans = t[v].que(y, 1, 0, t[v].vec.size() - 1);
if (L != R) {
int m = (L + R) >> 1;
if (pts[m].first <= x)
ans += que(x, y, v * 2, L, m);
else
ans += que(x, y, v * 2 + 1, m + 1, R);
}
return ans;
}
set<pair<int, int>> st;
int curt = 0;
void insSeg(int x, int y) {
if (x <= y) {
st.insert({x, y});
upd(x, y, x, y, -curt, 1, 0, pts.size() - 1);
}
}
void delSeg(int x, int y) {
st.erase({x, y});
upd(x, y, x, y, curt, 1, 0, pts.size() - 1);
}
void toggle(int x) {
if (s[x] == '1') {
auto it = prev(st.lower_bound({x + 1, -1}));
insSeg(it->first, x - 1);
insSeg(x + 1, it->second);
delSeg(it->first, it->second);
s[x] = '0';
}
else {
auto nt = st.lower_bound({x + 1, -1}),
pr = (nt == st.begin() ? st.end() : prev(nt));
int l, r;
if (nt != st.end() && nt->first == x + 1) {
r = nt->second;
delSeg(nt->first, nt->second);
}
else {
r = x;
}
if (pr != st.end() && pr->second == x - 1) {
l = pr->first;
delSeg(pr->first, pr->second);
}
else {
l = x;
}
insSeg(l, r);
}
}
int countAnswer(int x, int y) {
int ans = que(x, y, 1, 0, pts.size() - 1);
auto it = st.lower_bound({x + 1, -1});
if (it != st.begin() && prev(it)->second >= y)
ans += curt;
return ans;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> q >> s;
vector<Q> qr;
for (int i = 0; i < q; i++) {
string t;
cin >> t;
if (t[0] == 'q') {
int x, y;
cin >> x >> y;
x--;
y -= 2;
qr.push_back({0, x, y});
pts.push_back({x, y});
}
else {
int x;
cin >> x;
x--;
qr.push_back({1, x});
}
}
sort(all(pts));
build(1, 0, pts.size() - 1);
for (int i = 0, j = 0; i < n; i++) {
if (s[i] == '0') {
j = i + 1;
}
else if (i == n - 1 || s[i + 1] == '0') {
insSeg(j, i);
}
}
for (Q z : qr) {
curt++;
if (z.type == 0) {
cout << countAnswer(z.x, z.y) << "\n";
}
else {
toggle(z.x);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
56824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
527 ms |
85212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
56696 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
56812 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
56952 KB |
Output is correct |
| 2 |
Incorrect |
58 ms |
56888 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
56824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
