#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#define lb(x,y) lower_bound(all(x),y)-begin(x)
mt19937 rng;
struct HalfCompressedBIT2D {
int N;
bool built = 0;
vector<pair<int, int>> updates;
HalfCompressedBIT2D(int N = 0) : N(N) {}
void addUpdate(int r, int c) {
updates.pb({r, c});
}
vector<vector<int>> compress;
vector<vector<ll>> tree;
static bool cmp(pair<int, int> &a, pair<int, int> &b) {
return a.second < b.second;
}
void build() {
sort(all(updates), cmp);
compress = vector<vector<int>>(N, {0});
for (auto &p : updates)
for (int rr = p.first; rr < sz(compress); rr += rr & -rr)
compress[rr].pb(p.second);
tree = vector<vector<ll>>(sz(compress));
for (int i = 0; i < sz(compress); i++) {
tree[i] = vector<ll>(sz(compress[i]), 0);
}
built = 1;
}
void update(int r, int c, int k) {
if (!built) build();
for (int rr = r; rr < sz(compress); rr += rr & -rr)
for (int cc = lb(compress[rr], c); cc < sz(compress[rr]); cc += cc & -cc)
tree[rr][cc] += k;
}
ll query(int r, int c) {
if (!built) build();
ll res = 0;
for (int rr = r; rr; rr -= rr & -rr)
for (int cc = lb(compress[rr], c + 1) - 1; cc; cc -= cc & -cc)
res += tree[rr][cc];
return res;
}
};
vector<bool> a;
HalfCompressedBIT2D sum;
set<int> off;
vector<int> sum2;
void addToggle(int i) {
if (a[i - 1]) {
int l = *prev(off.lower_bound(i)) + 1, r = *off.lower_bound(i) - 1;
a[i - 1] = 0;
off.insert(i);
sum.addUpdate(l, i);
sum.addUpdate(i + 1, i);
sum.addUpdate(l, r + 1);
sum.addUpdate(i + 1, r + 1);
} else {
off.erase(i);
a[i - 1] = 1;
int l = *prev(off.lower_bound(i)) + 1, r = *off.lower_bound(i) - 1;
sum.addUpdate(l, i);
sum.addUpdate(i + 1, i);
sum.addUpdate(l, r + 1);
sum.addUpdate(i + 1, r + 1);
}
}
void toggle(int i, int t) {
if (a[i - 1]) {
int l = *prev(off.lower_bound(i)) + 1, r = *off.lower_bound(i) - 1;
a[i - 1] = 0;
off.insert(i);
sum.update(l, i, t);
sum.update(i + 1, i, -t);
sum.update(l, r + 1, -t);
sum.update(i + 1, r + 1, t);
for (int j = i; j < sz(sum2); j += j & -j) sum2[j]--;
} else {
off.erase(i);
a[i - 1] = 1;
int l = *prev(off.lower_bound(i)) + 1, r = *off.lower_bound(i) - 1;
sum.update(l, i, -t);
sum.update(i + 1, i, t);
sum.update(l, r + 1, t);
sum.update(i + 1, r + 1, -t);
for (int j = i; j < sz(sum2); j += j & -j) sum2[j]++;
}
}
ll query(int l, int r, int t) {
int n = 0;
for (int i = r; i; i -= i & -i) n += sum2[i];
for (int i = l - 1; i; i -= i & -i) n -= sum2[i];
return sum.query(l, r) + (n == r - l + 1 ? t : 0);
}
void solve() {
int N, Q; cin >> N >> Q;
string s; cin >> s;
a = vector<bool>(N, 0);
sum = HalfCompressedBIT2D(N + 1);
off.insert(0);
off.insert(N + 1);
sum2 = vector<int>(N + 1, 0);
for (int i = 1; i <= N; i++) {
if (s[i - 1] == '1') addToggle(i);
}
vector<vector<int>> queries;
for (int q = 0; q < Q; q++) {
string type; cin >> type;
if (type == "toggle") {
int i; cin >> i;
addToggle(i);
queries.pb({0, i});
} else {
int l, r; cin >> l >> r; r--;
queries.pb({1, l, r});
}
}
off.clear();
off.insert(0);
off.insert(N + 1);
fill(all(a), 0);
for (int i = 1; i <= N; i++) {
if (s[i - 1] == '1') toggle(i, 0);
}
for (int q = 0; q < Q; q++) {
if (!queries[q][0]) {
toggle(queries[q][1], q + 1);
} else {
cout << query(queries[q][1], queries[q][2], q + 1) << "\n";
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
381 ms |
55440 KB |
Output is correct |
| 2 |
Correct |
548 ms |
62652 KB |
Output is correct |
| 3 |
Correct |
826 ms |
79308 KB |
Output is correct |
| 4 |
Correct |
2023 ms |
248248 KB |
Output is correct |
| 5 |
Correct |
2225 ms |
290416 KB |
Output is correct |
| 6 |
Correct |
2077 ms |
262336 KB |
Output is correct |
| 7 |
Correct |
151 ms |
58668 KB |
Output is correct |
| 8 |
Correct |
1488 ms |
290448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
