| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1314377 | thuhienne | Street Lamps (APIO19_street_lamps) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define thuhien ""
#define re exit(0);
int n,q;
string s;
bool state[maxn];
struct Fenwick2D {
vector <int> index,value;
} fenwick;
set <pair <int,int>> segment;
struct qu {
char op;int a,b;
} query[maxn];
int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(nullptr);
if (fopen(thuhien".inp","r")) {
freopen(thuhien".inp","r",stdin);
freopen(thuhien".out","w",stdout);
}
cin >> n >> q >> s;
s = " " + s;
int last = -1;
for (int i = 1;i <= n;i++) {
state[i] = s[i] - '0';
if (s[i] == '0') {
if (last != -1) segment.insert(make_pair(last,i - 1));
last = -1;
} else {
if (last == -1) last = i;
}
}
if (last != -1) segment.insert(make_pair(last,i - 1));
for (int i = 1;i <= q;i++) {
string TMP;cin >> TMP >> query[i].a;
query[i].op = TMP[0];
if (query[i].op == 'q') {
cin >> query[i].b;
query[i].b--;
} else {
int pos = query[i].a;
if (state[pos]) {
auto it = segment.upper_bound(make_pair(pos,1e9));
it--;
int l = it -> first,r = it -> second;
fenwick.event(l,pos,pos,r);
segment.erase(it);
if (l < pos) segment.insert(make_pair(l,pos - 1));
if (r > pos) segment.insert(make_pair(pos + 1,r));
} else {
int l = pos,r = pos;
if (state[pos - 1]) {
auto it = segment.upper_bound(make_pair(pos,-1));
it--;
l = it -> first;
}
if (state[pos + 1]) {
auto it = segment.lower_bound(make_pair(pos + 1,-1));
r = it -> second;
}
fenwick.event(l,pos,pos,r);
}
state[pos] ^= 1;
}
}
fen.build();
segment.clear();
last = -1;
for (int i = 1;i <= n;i++) {
state[i] = s[i] - '0';
if (s[i] == '0') {
if (last != -1) segment.insert(make_pair(last,i - 1));
last = -1;
} else {
if (last == -1) last = i;
}
}
if (last != -1) segment.insert(make_pair(last,i - 1));
for (int i = 1;i <= q;i++) {
if (query[i].op == 'q') {
cout << fenwick.get(query[i].a,query[i].b) << '\n';
} else {
int pos = query[i].a;
if (state[pos]) {
auto it = segment.upper_bound(make_pair(pos,1e9));
it--;
int l = it -> first,r = it -> second;
fenwick.update(l,pos,pos,r,i);
segment.erase(it);
if (l < pos) segment.insert(make_pair(l,pos - 1));
if (r > pos) segment.insert(make_pair(pos + 1,r));
} else {
int l = pos,r = pos;
if (state[pos - 1]) {
auto it = segment.upper_bound(make_pair(pos,-1));
it--;
l = it -> first;
}
if (state[pos + 1]) {
auto it = segment.lower_bound(make_pair(pos + 1,-1));
r = it -> second;
}
fenwick.update(l,pos,pos,r,-i);
}
state[pos] ^= 1;
}
}
}