#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_contatiner.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> ii;
const int N = 3e5;
const int INF = 1e9;
int n, q;
int a[N+2];
gp_hash_table<int,int> bit[N+2];
void update(int r1, int r2, int c1, int c2, int v) {
for (int i = r1; i <= n+1; i += i&-i) {
for (int j = c1; j <= n+1; j += j&-j) {
bit[i][j] += v;
}
}
for (int i = r1; i <= n+1; i += i&-i) {
for (int j = c2+1; j <= n+1; j += j&-j) {
bit[i][j] -= v;
}
}
for (int i = r2+1; i <= n+1; i += i&-i) {
for (int j = c1; j <= n+1; j += j&-j) {
bit[i][j] -= v;
}
}
for (int i = r2+1; i <= n+1; i += i&-i) {
for (int j = c2+1; j <= n+1; j += j&-j) {
bit[i][j] += v;
}
}
}
int query(int r, int c) {
int ret = 0;
for (int i = r; i; i -= i&-i) {
for (int j = c; j; j -= j&-j) {
if (bit[i].find(j) != bit[i].end()) ret += bit[i][j];
}
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
set<ii> st;
for (int i = 1; i <= n; i++) {
char x; cin >> x;
a[i] = x-'0';
if (a[i]) {
if (i == 1 || !a[i-1]) st.insert(ii(i,i));
else {
auto it = st.end(); it--;
int l = it->fi;
st.erase(it);
st.insert(ii(l,i));
}
}
}
for (int i = 1; i <= q; i++) {
string s; cin >> s;
if (s == "toggle") {
int x; cin >> x;
if (a[x]) {
auto it = st.upper_bound(ii(x,INF)); it--;
int l = it->fi, r = it->se;
st.erase(it);
if (l <= x-1) st.insert(ii(l,x-1));
if (x+1 <= r) st.insert(ii(x+1,r));
update(l,x,x+1,r,i);
}
else {
vector<set<ii>::iterator> del;
auto it = st.upper_bound(ii(x,INF));
int l, r;
if (it != st.end() && it->fi == x+1) {
r = it->se+1;
del.push_back(it);
}
if (it != st.begin()) {
it--;
if (it->se == x-1) {
l = it->fi;
del.push_back(it);
}
else l = x;
}
for (auto i : del) st.erase(i);
st.insert(ii(l,r-1));
update(l,x,x+1,r,-i);
}
a[x] ^= 1;
}
else {
int a, b; cin >> a >> b;
int ans = query(a,b);
auto it = st.upper_bound(ii(a,INF));
if (it != st.begin()) {
it--;
if (it->se+1 >= b) ans += i;
}
cout << ans << '\n';
}
}
return 0;
}
Compilation message
street_lamps.cpp:2:10: fatal error: ext/pb_ds/assoc_contatiner.hpp: No such file or directory
2 | #include <ext/pb_ds/assoc_contatiner.hpp>
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.
