#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;
template<class T>
istream &operator>>(istream &is, vector<T> &a) {
for (auto &i : a) {
is >> i;
}
return is;
}
#ifdef __APPLE__
#include "../../debug.h"
#else
#define debug(...) 42
#endif
template<typename T>
void unique(vector<T> &a) {
sort(a.begin(), a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
}
struct Fenwick {
vector<int> t;
int n;
Fenwick() {}
Fenwick(int n) : n(n) {
t.resize(n + 1);
}
void add(int i, int x) {
for (++i; i <= n; i += i & (-i)) {
t[i] += x;
}
}
void add(int l, int r, int x) { // add on [l, r)
add(l, x);
add(r, -x);
}
int get(int i) {
int ans = 0;
for (; i > 0; i -= i & (-i)) {
ans += t[i];
}
return ans;
}
int get(int l, int r) {
return get(r) - get(l);
}
};
struct SegTree { // merge sort tree szhatih fenwickov
struct Node {
Fenwick st;
vector<int> coords;
};
vector<Node> tree;
int n;
SegTree(int n) : n(n) {
tree.resize(4 * n);
}
void insert(int v, int l, int r, int i, int x) {
tree[v].coords.push_back(x);
if (l + 1 == r) {
return;
}
int m = (l + r) / 2;
if (i < m) {
insert(2 * v + 1, l, m, i, x);
} else {
insert(2 * v + 2, m, r, i, x);
}
}
void insert(int i, int x) {
insert(0, 0, n, i, x);
}
void init(int v, int l, int r) {
unique(tree[v].coords);
tree[v].st = Fenwick(tree[v].coords.size());
if (l + 1 == r) {
return;
}
int m = (l + r) / 2;
init(2 * v + 1, l, m);
init(2 * v + 2, m, r);
}
void init() {
init(0, 0, n);
}
void update(int v, int l, int r, int li, int ri, int ly, int ry, int x) {
if (li >= r || l >= ri) {
return;
}
if (li <= l && r <= ri) {
int itl = lower_bound(tree[v].coords.begin(), tree[v].coords.end(), ly) - tree[v].coords.begin();
int itr = lower_bound(tree[v].coords.begin(), tree[v].coords.end(), ry) - tree[v].coords.begin();
debug(tree[v].coords, ly, ry, itl, itr);
tree[v].st.add(itl, itr, x);
return;
}
int m = (l + r) / 2;
update(2 * v + 1, l, m, li, ri, ly, ry, x);
update(2 * v + 2, m, r, li, ri, ly, ry, x);
}
void update(int lx, int rx, int ly, int ry, int x) {
update(0, 0, n, lx, rx, ly, ry, x);
}
int get(int v, int l, int r, int i, int j) {
int it = lower_bound(tree[v].coords.begin(), tree[v].coords.end(), j) - tree[v].coords.begin();
int ans = tree[v].st.get(it + 1);
if (l + 1 == r) {
return ans;
}
int m = (l + r) / 2;
if (i < m) {
return ans + get(2 * v + 1, l, m, i, j);
} else {
return ans + get(2 * v + 2, m, r, i, j);
}
}
int get(int i, int j) {
return get(0, 0, n, i, j);
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
freopen("input.txt", "r", stdin);
#endif
int n, q;
cin >> n >> q;
string s;
cin >> s;
set<int> zero;
vector<pair<int, int>> lr, qq;
for (int i = 0; i < q; ++i) {
string s;
cin >> s;
if (s == "toggle") {
int j;
cin >> j;
--j;
qq.push_back({0, j});
} else {
int a, b;
cin >> a >> b;
a -= 1;
b -= 2;
lr.push_back({a, b});
qq.push_back({1, (int) lr.size() - 1});
}
}
vector<int> ans(lr.size());
for (int i = -1; i <= n; ++i) {
zero.insert(i);
}
SegTree mst(n);
for (auto [l, r] : lr) {
mst.insert(l, r);
}
mst.init();
auto upd = [&](int pos, int t) {
auto itr = zero.upper_bound(pos);
auto itl = zero.lower_bound(pos);
int r = *itr;
int l = *prev(itl) + 1;
// += t on [l, pos] [pos, r)
mst.update(l, pos + 1, pos, r, t);
// for (int i = 0; i < (int) lr.size(); ++i) {
// auto [li, ri] = lr[i];
// if (l <= li && li <= pos && pos <= ri && ri < r) {
// debug(li + 1, ri + 1, t);
// ans[i] += t;
// }
// }
if (!zero.contains(pos)) {
zero.insert(pos);
} else {
zero.erase(pos);
}
};
Fenwick bebra(n);
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
upd(i, 0);
bebra.add(i, 1);
}
}
for (int i = 1; i <= q; ++i) {
auto [t, j] = qq[i - 1];
if (t == 0) {
if (s[j] == '0') {
s[j] = '1';
upd(j, -i);
bebra.add(j, 1);
} else {
s[j] = '0';
upd(j, i);
bebra.add(j, -1);
}
} else {
auto [l, r] = lr[j];
int cur = mst.get(l, r);
// debug(ans[j], cur);
if (bebra.get(l, r + 1) != r - l + 1) {
cout << cur << "\n";
} else {
cout << i + cur << "\n";
}
}
}
}
Compilation message
street_lamps.cpp: In member function 'void SegTree::update(int, int, int, int, int, int, int, int)':
street_lamps.cpp:19:20: warning: statement has no effect [-Wunused-value]
19 | #define debug(...) 42
| ^~
street_lamps.cpp:113:13: note: in expansion of macro 'debug'
113 | debug(tree[v].coords, ly, ry, itl, itr);
| ^~~~~
street_lamps.cpp: In lambda function:
street_lamps.cpp:196:19: error: 'class std::set<int>' has no member named 'contains'
196 | if (!zero.contains(pos)) {
| ^~~~~~~~
