#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct interval
{
int left, right, in_time;
interval(int _left, int _right, int _in_time)
{
left = _left;
right = _right;
in_time = _in_time;
}
bool operator < (const interval &it) const
{
return left < it.left;
}
};
const int maxn = 3e5 + 10;
struct base_query
{
string type;
int x, a, b;
} base_ask[maxn];
int n, q;
char c[maxn], cs[maxn];
struct fenwick
{
vector < int > fen;
int n;
fenwick(){};
fenwick(int _n)
{
n = _n;
fen.resize(n + 1);
}
void update(int v, int val)
{
v ++;
for (int i = v; i <= n; i += (i&-i))
fen[i] += val;
}
int sum(int v)
{
v ++;
int s = 0;
for (int i = v; i > 0; i -= (i&-i))
s += fen[i];
return s;
}
int query(int left, int right)
{
if (left > right)
return 0;
return sum(right) - sum(left - 1);
}
};
fenwick f[maxn * 4][3];
void input()
{
cin >> n >> q;
n ++;
for (int i = 1; i < n; i ++)
cin >> c[i], cs[i] = c[i];
for (int i = 1; i <= q; i ++)
{
cin >> base_ask[i].type;
if (base_ask[i].type == "query")
{
cin >> base_ask[i].a >> base_ask[i].b;
}
else
{
cin >> base_ask[i].x;
}
}
}
set < pair < int, int > > available;
void create_intervals()
{
set < interval > st;
int beg = 1;
for (int i = 1; i < n; i ++)
{
if (c[i] == '0')
{
///cout << beg << " -- " << i << endl;
st.insert(interval(beg, i, 0));
available.insert({beg, i});
beg = i + 1;
}
}
st.insert(interval(beg, n, 0));
available.insert({beg, n});
for (int i = 1; i <= q; i ++)
{
if (base_ask[i].type == "toggle")
{
int pos = base_ask[i].x;
if (c[pos] == '0')
{
c[pos] = '1';
set < interval > :: iterator aft_it = st.lower_bound(interval(pos + 1, pos + 1, -1));
set < interval > :: iterator bef_it = prev(aft_it);
interval bef = *bef_it;
interval aft = *aft_it;
interval cur(bef.left, aft.right, i);
st.erase(bef);
st.erase(aft);
st.insert(cur);
available.insert({cur.left, cur.right});
}
else
{
c[pos] = '0';
set < interval > :: iterator cur_it = prev(st.lower_bound(interval(pos + 1, pos + 1, -1)));
interval cur = *cur_it;
interval bef(cur.left, pos, i);
interval aft(pos + 1, cur.right, i);
st.erase(cur);
st.insert(bef);
st.insert(aft);
available.insert({bef.left, bef.right});
available.insert({aft.left, aft.right});
}
}
}
//for (pair < int, int > cur : available)
// cout << cur.first << " : " << cur.second << endl;
}
const int smalln = 110;
///int act[smalln][smalln], act_time[smalln][smalln], sum[smalln][smalln];
struct node
{
int act_cnt, sum_act;
node(int _act_cnt = 0, int _sum_act = 0)
{
act_cnt = _act_cnt;
sum_act = _sum_act;
}
};
node merge_node(node bef, node aft)
{
node cur;
cur.act_cnt = bef.act_cnt + aft.act_cnt;
cur.sum_act = bef.sum_act + aft.sum_act;
return cur;
}
struct segment_tree
{
vector < node > tree;
int n;
segment_tree() {};
segment_tree(int _n)
{
n = _n;
tree.resize(4 * n);
}
void update_toggle(int root, int left, int right, int pos, int cur_time)
{
if (left == right)
{
tree[root].act_cnt ++;
tree[root].act_cnt %= 2;
if (tree[root].act_cnt == 0)
tree[root].sum_act = 0;
else
tree[root].sum_act = cur_time;
///cout << "toggle last " << left << " " << cur_time << endl;
return;
}
int mid = (left + right) / 2;
if (pos <= mid)
update_toggle(root * 2, left, mid, pos, cur_time);
else
update_toggle(root * 2 + 1, mid + 1, right, pos, cur_time);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
node query_range(int root, int left, int right, int qleft, int qright)
{
if (left > qright || right < qleft)
return node();
if (left >= qleft && right <= qright)
return tree[root];
int mid = (left + right) / 2;
return merge_node(query_range(root * 2, left, mid, qleft, qright),
query_range(root * 2 + 1, mid + 1, right, qleft, qright));
}
void toggle(int pos, int cur_time)
{
update_toggle(1, 0, n - 1, pos, cur_time);
}
node query(int left, int right)
{
if (left > right)
return node();
return query_range(1, 0, n - 1, left, right);
}
};
segment_tree seg[4 * maxn];
vector < pair < int, int > > tree[4 * maxn], values[maxn];
map < int, int > act_time[maxn], act[maxn];
int lower_bound_simulate(int root, pair < int, int > cur)
{
int lf = 0, rf = (int)(tree[root].size()) - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (tree[root][mf].second < cur.second)
lf = mf + 1;
else if (tree[root][mf].second > cur.second)
rf = mf - 1;
else
{
if (tree[root][mf].first < cur.first)
lf = mf + 1;
else
rf = mf - 1;
}
}
return lf;
}
void toggle_node(int root, pair < int, int > cur, int cur_time)
{
int lf = lower_bound_simulate(root, cur);
seg[root].toggle(lf, cur_time);
if (act[cur.first][cur.second] == 0)
{
f[root][1].update(lf, -1);
///cout << "toggle " << root << " " << cur.first << " " << cur.second << endl;
f[root][0].update(lf, cur_time - act_time[cur.first][cur.second]);
int val = - f[root][2].query(lf, lf);
f[root][2].update(lf, val);
}
else
{
f[root][1].update(lf, 1);
int val = cur_time - f[root][2].query(lf, lf);
f[root][2].update(lf, val);
}
}
void toggle(int root, int left, int right, pair < int, int > cur, int cur_time)
{
toggle_node(root, cur, cur_time);
if (left == right)
return;
int mid = (left + right) / 2;
if (cur.first <= mid)
toggle(root * 2, left, mid, cur, cur_time);
else
toggle(root * 2 + 1, mid + 1, right, cur, cur_time);
}
void update_interval(interval cur, int cur_time)
{
if (act[cur.left][cur.right] == 0)
{
act[cur.left][cur.right] = 1;
}
else
{
act[cur.left][cur.right] = 0;
}
///if (available.find({cur.left, cur.right}) == available.end())
/// while(true);
///cout << "update " << cur.left << " " << cur.right << endl;
toggle(1, 1, n, {cur.left, cur.right}, cur_time);
if (act[cur.left][cur.right] == 1)
act_time[cur.left][cur.right] = cur_time;
}
int query(int root, int left, int right, pair < int, int > val, int cur_time)
{
if (left > val.first)
return 0;
if (right <= val.first)
{
///cout << root << " : " << left << " : " << right << " : " << val.first << " : " << val.second << endl;
int lf = lower_bound_simulate(root, {-1, val.second});
node cur = seg[root].query(lf, (int)(tree[root].size()) - 1);
int ans = f[root][1].query(lf, (int)(tree[root].size()) - 1) * cur_time - f[root][2].query(lf, (int)(tree[root].size()) - 1) + f[root][0].query(lf, (int)(tree[root].size()) - 1);
///cout << "here " << left << " " << right << " " << cur.act_cnt << " " << cur.sum_act << endl;
///cout << "here " << lf << " " << tree[root][lf].second << endl;
return ans;
}
int mid = (left + right) / 2;
return query(root * 2, left, mid, val, cur_time) +
query(root * 2 + 1, mid + 1, right, val, cur_time);
}
void conquer(int root, int lf, int rf)
{
int left = 0, right = 0;
while(left < tree[lf].size() && right < tree[rf].size())
{
if (tree[lf][left].second < tree[rf][right].second)
{
tree[root].push_back(tree[lf][left ++]);
}
else if (tree[lf][left].second > tree[rf][right].second)
{
tree[root].push_back(tree[rf][right ++]);
}
else if (tree[lf][left].first < tree[rf][right].first)
{
tree[root].push_back(tree[lf][left ++]);
}
else
{
tree[root].push_back(tree[rf][right ++]);
}
}
while(left < tree[lf].size())
tree[root].push_back(tree[lf][left ++]);
while(right < tree[rf].size())
tree[root].push_back(tree[rf][right ++]);
seg[root] = segment_tree(tree[root].size());
f[root][1] = fenwick(tree[root].size());
f[root][0] = fenwick(tree[root].size());
f[root][2] = fenwick(tree[root].size());
}
void divide(int root, int left, int right)
{
if (left == right)
{
tree[root] = values[left];
seg[root] = segment_tree(tree[root].size());
f[root][0] = fenwick(tree[root].size());
f[root][1] = fenwick(tree[root].size());
f[root][2] = fenwick(tree[root].size());
return;
}
int mid = (left + right) / 2;
divide(root * 2, left, mid);
divide(root * 2 + 1, mid + 1, right);
conquer(root, root * 2, root * 2 + 1);
}
void build_trees()
{
for (pair < int, int > cur : available)
{
values[cur.first].push_back(cur);
}
divide(1, 1, n);
}
void simulate()
{
set < interval > st;
int beg = 1;
for (int i = 1; i < n; i ++)
{
c[i] = cs[i];
if (c[i] == '0')
{
st.insert(interval(beg, i, 0));
update_interval(interval(beg, i, -1), 0);
beg = i + 1;
}
}
st.insert(interval(beg, n, 0));
update_interval(interval(beg, n, -1), 0);
///cout << "--------------" << endl;
for (int i = 1; i <= q; i ++)
{
if (base_ask[i].type == "toggle")
{
///cout << "toggle" << endl;
int pos = base_ask[i].x;
if (c[pos] == '0')
{
c[pos] = '1';
set < interval > :: iterator aft_it = st.lower_bound(interval(pos + 1, pos + 1, -1));
set < interval > :: iterator bef_it = prev(aft_it);
interval bef = *bef_it;
interval aft = *aft_it;
interval cur(bef.left, aft.right, i);
update_interval(bef, i);
update_interval(aft, i);
update_interval(cur, i);
st.erase(bef);
st.erase(aft);
st.insert(cur);
available.insert({cur.left, cur.right});
}
else
{
c[pos] = '0';
set < interval > :: iterator cur_it = prev(st.lower_bound(interval(pos + 1, pos + 1, -1)));
interval cur = *cur_it;
interval bef(cur.left, pos, i);
interval aft(pos + 1, cur.right, i);
///cout << " ::: " << bef.left << " " << bef.right << endl;
st.erase(cur);
st.insert(bef);
st.insert(aft);
update_interval(bef, i);
update_interval(aft, i);
update_interval(cur, i);
available.insert({bef.left, bef.right});
available.insert({aft.left, aft.right});
}
}
else
{
int ans = query(1, 1, n, {base_ask[i].a, base_ask[i].b}, i);
/**for (int l = 1; l <= base_ask[i].a; l ++)
for (int r = base_ask[i].b; r <= n; r ++)
{
///ans = ans + sum[l][r];
///cout << l << " -- " << r << " " << act[l][r] << endl;
if (act[l][r])
{
///cout << l << " " << r << " " << act_time[l][r] << endl;
ans = ans + i - act_time[l][r];
}
}*/
cout << ans << endl;
}
}
//for (pair < int, int > cur : available)
// cout << cur.first << " : " << cur.second << endl;
}
void solve()
{
input();
create_intervals();
build_trees();
simulate();
}
int main()
{
speed();
solve();
return 0;
}
/**
5 3
11011
toggle 2
toggle 1
query 1 2
*/
Compilation message
street_lamps.cpp: In function 'int query(int, int, int, std::pair<int, int>, int)':
street_lamps.cpp:332:14: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
332 | node cur = seg[root].query(lf, (int)(tree[root].size()) - 1);
| ^~~
street_lamps.cpp: In function 'void conquer(int, int, int)':
street_lamps.cpp:348:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
348 | while(left < tree[lf].size() && right < tree[rf].size())
| ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:348:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
348 | while(left < tree[lf].size() && right < tree[rf].size())
| ~~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:368:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
368 | while(left < tree[lf].size())
| ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:371:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
371 | while(right < tree[rf].size())
| ~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
228116 KB |
Output is correct |
| 2 |
Correct |
112 ms |
228128 KB |
Output is correct |
| 3 |
Correct |
104 ms |
228108 KB |
Output is correct |
| 4 |
Correct |
111 ms |
228348 KB |
Output is correct |
| 5 |
Correct |
107 ms |
228140 KB |
Output is correct |
| 6 |
Correct |
108 ms |
228192 KB |
Output is correct |
| 7 |
Correct |
110 ms |
228140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1136 ms |
232148 KB |
Output is correct |
| 2 |
Correct |
1473 ms |
231460 KB |
Output is correct |
| 3 |
Correct |
3341 ms |
261364 KB |
Output is correct |
| 4 |
Runtime error |
797 ms |
524288 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
229852 KB |
Output is correct |
| 2 |
Correct |
130 ms |
229424 KB |
Output is correct |
| 3 |
Correct |
109 ms |
228836 KB |
Output is correct |
| 4 |
Correct |
103 ms |
228320 KB |
Output is correct |
| 5 |
Runtime error |
1012 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
228748 KB |
Output is correct |
| 2 |
Correct |
111 ms |
228988 KB |
Output is correct |
| 3 |
Correct |
123 ms |
229324 KB |
Output is correct |
| 4 |
Correct |
122 ms |
229532 KB |
Output is correct |
| 5 |
Correct |
1730 ms |
486316 KB |
Output is correct |
| 6 |
Runtime error |
655 ms |
524288 KB |
Execution killed with signal 9 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
228116 KB |
Output is correct |
| 2 |
Correct |
112 ms |
228128 KB |
Output is correct |
| 3 |
Correct |
104 ms |
228108 KB |
Output is correct |
| 4 |
Correct |
111 ms |
228348 KB |
Output is correct |
| 5 |
Correct |
107 ms |
228140 KB |
Output is correct |
| 6 |
Correct |
108 ms |
228192 KB |
Output is correct |
| 7 |
Correct |
110 ms |
228140 KB |
Output is correct |
| 8 |
Correct |
1136 ms |
232148 KB |
Output is correct |
| 9 |
Correct |
1473 ms |
231460 KB |
Output is correct |
| 10 |
Correct |
3341 ms |
261364 KB |
Output is correct |
| 11 |
Runtime error |
797 ms |
524288 KB |
Execution killed with signal 9 |
| 12 |
Halted |
0 ms |
0 KB |
- |
