#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
struct node {
int pref, suf;
vector<pair<int, int>> left_events;
vector<pair<int, int>> right_events;
vector<pair<int, pair<int, int>>> queries;
};
const int inf = 1e9 + 20;
const int maxN = 3e5 + 20;
int a[maxN];
int res[maxN];
node tr[maxN * 4];
int sum_single[maxN];
int prv_single[maxN];
void add_event(int id, int T) {
if (tr[id].left_events.empty() || tr[id * 2].suf != tr[id].left_events.back().second) {
tr[id].left_events.push_back({T, tr[id * 2].suf});
}
if (tr[id].right_events.empty() || tr[id * 2 + 1].pref != tr[id].right_events.back().second) {
tr[id].right_events.push_back({T, tr[id * 2 + 1].pref});
}
}
void merge(int id, int lt, int rt, int mt, int T) {
tr[id].pref = tr[id * 2].pref + (tr[id * 2].pref == mt - lt + 1 ? tr[id * 2 + 1].pref : 0);
tr[id].suf = tr[id * 2 + 1].suf + (tr[id * 2 + 1].suf == rt - mt ? tr[id * 2].suf : 0);
add_event(id, T);
}
void build(int id, int lt, int rt) {
if (lt == rt) {
tr[id].pref = a[lt];
tr[id].suf = a[lt];
return;
}
int mt = (lt + rt) / 2;
build(id * 2, lt, mt);
build(id * 2 + 1, mt + 1, rt);
merge(id, lt, rt, mt, 0);
}
void update(int id, int lt, int rt, int pos, int T) {
if (lt == rt) {
if (a[lt] == 1) {
sum_single[lt] += T - prv_single[lt];
}
prv_single[lt] = T;
a[lt] ^= 1;
tr[id].pref = a[lt];
tr[id].suf = a[lt];
return;
}
int mt = (lt + rt) / 2;
if (pos <= mt) {
update(id * 2, lt, mt, pos, T);
}
else {
update(id * 2 + 1, mt + 1, rt, pos, T);
}
merge(id, lt, rt, mt, T);
}
void add(int id, int lt, int rt, int ql, int qr, int T) {
if (lt == rt) {
res[T] = sum_single[lt];
if (a[lt] == 1) {
res[T] += T - prv_single[lt];
}
return;
}
int mt = (lt + rt) / 2;
if (qr <= mt) {
add(id * 2, lt, mt, ql, qr, T);
}
else if (ql >= mt + 1) {
add(id * 2 + 1, mt + 1, rt, ql, qr, T);
}
else {
tr[id].queries.push_back({T, {mt - ql + 1, qr - mt}});
}
}
struct BIT {
vector<pair<pair<int, int>, int>> a;
int n;
void init(int _n) {
a.clear();
n = _n;
}
void add(int x, int y, int val) {
assert(x >= 1 && x <= n);
a.push_back({{x, y}, val});
}
int get(int x, int y) {
assert(x >= 1 && x <= n);
int res = 0;
for (auto p: a) {
if (p.first.first <= x && p.first.second <= y) {
res += p.second;
}
}
return res;
}
} bit;
void solve(int id) {
vector<pair<int, pair<int, int>>> &queries = tr[id].queries;
vector<pair<int, int>> &left_events = tr[id].left_events;
vector<pair<int, int>> &right_events = tr[id].right_events;
if (queries.empty()) {
return;
}
left_events.push_back({inf, -1});
right_events.push_back({inf, -1});
vector<pair<int, pair<int, int>>> events;
int sz_left = left_events.size();
int sz_right = right_events.size();
int sz_queries = queries.size();
vector<int> left_pos(sz_left);
vector<int> right_pos(sz_right);
vector<int> query_pos(sz_queries);
for (int i = 0; i < sz_left; i++) {
events.push_back({left_events[i].first, {0, i}});
}
for (int i = 0; i < sz_right; i++) {
events.push_back({right_events[i].first, {1, i}});
}
for (int i = 0; i < sz_queries; i++) {
events.push_back({queries[i].first, {2, i}});
}
sort(events.begin(), events.end());
int n = 0;
vector<int> len;
for (int i = 0; i < (int)events.size(); i++) {
if (i > 0 && events[i].first != events[i - 1].first) {
len.push_back(events[i].first - events[i - 1].first);
n++;
}
if (events[i].second.first == 0) {
left_pos[events[i].second.second] = n;
}
if (events[i].second.first == 1) {
right_pos[events[i].second.second] = n;
}
if (events[i].second.first == 2) {
query_pos[events[i].second.second] = n - 1;
}
}
vector<int> left_val(n);
vector<int> right_val(n);
for (int i = 0; i < sz_left - 1; i++) {
for (int j = left_pos[i]; j < left_pos[i + 1]; j++) {
left_val[j] = left_events[i].second;
}
}
for (int i = 0; i < sz_right - 1; i++) {
for (int j = right_pos[i]; j < right_pos[i + 1]; j++) {
right_val[j] = right_events[i].second;
}
}
vector<pair<int, pair<int, int>>> left_query_events;
vector<pair<int, int>> right_vals;
for (int i = 0; i < n; i++) {
left_query_events.push_back({left_val[i], {1, i}});
right_vals.push_back({-right_val[i], i});
}
sort(right_vals.begin(), right_vals.end());
int cnt = 0;
vector<int> right_diff;
for (int i = 0; i < n; i++) {
if (i == 0 || right_vals[i].first != right_vals[i - 1].first) {
right_diff.push_back(right_vals[i].first);
cnt++;
}
right_val[right_vals[i].second] = cnt;
}
for (int i = 0; i < sz_queries; i++) {
queries[i].second.second = upper_bound(right_diff.begin(), right_diff.end(), -queries[id].second.second) - right_diff.begin();
}
for (int i = 0; i < sz_queries; i++) {
left_query_events.push_back({queries[i].second.first, {0, i}});
}
sort(left_query_events.begin(), left_query_events.end(), greater<>());
bit.init(n);
for (auto e: left_query_events) {
if (e.second.first == 1) {
int pos = e.second.second;
bit.add(pos + 1, right_val[pos], len[pos]);
}
else {
int id = e.second.second;
int T = queries[id].first;
int Y = queries[id].second.second;
int pos = query_pos[id];
res[T] = bit.get(pos + 1, Y);
}
}
}
void solve(int id, int lt, int rt) {
if (lt == rt) {
return;
}
solve(id);
int mt = (lt + rt) / 2;
solve(id * 2, lt, mt);
solve(id * 2 + 1, mt + 1, rt);
}
void just_do_it() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
char c;
cin >> c;
a[i] = c - '0';
}
build(1, 1, n);
for (int T = 1; T <= q; T++) {
res[T] = -1;
string s;
cin >> s;
if (s == "toggle") {
int pos;
cin >> pos;
update(1, 1, n, pos, T);
}
if (s == "query") {
int ql, qr;
cin >> ql >> qr;
qr--;
add(1, 1, n, ql, qr, T);
}
}
solve(1, 1, n);
for (int i = 1; i <= q; i++) {
if (res[i] != -1) {
cout << res[i] << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
94156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
101244 KB |
Output is correct |
| 2 |
Correct |
138 ms |
100916 KB |
Output is correct |
| 3 |
Correct |
191 ms |
101680 KB |
Output is correct |
| 4 |
Correct |
426 ms |
122188 KB |
Output is correct |
| 5 |
Correct |
483 ms |
121512 KB |
Output is correct |
| 6 |
Correct |
539 ms |
123492 KB |
Output is correct |
| 7 |
Correct |
311 ms |
115904 KB |
Output is correct |
| 8 |
Correct |
284 ms |
117384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
94284 KB |
Output is correct |
| 2 |
Incorrect |
51 ms |
94360 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
94376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
94156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
