#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];
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, 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];
void update_interval(interval cur, int cur_time)
{
if (act[cur.left][cur.right])
{
act[cur.left][cur.right] = 0;
sum[cur.left][cur.right] += cur_time - act_time[cur.left][cur.right];
}
else
{
act_time[cur.left][cur.right] = cur_time;
act[cur.left][cur.right] = 1;
}
}
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));
act[beg][i] = 1;
act_time[beg][i] = 0;
beg = i + 1;
}
}
act[beg][n] = 1;
st.insert(interval(beg, n, 0));
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, cur.right, i);
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
{
ll ans = 0;
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 << 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();
simulate();
}
int main()
{
solve();
return 0;
}
/**
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
724 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
15060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
14948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
