#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 3e5 + 100;
struct fen{
const int N = 1e6 + 10;
vector <ll> f;
fen() {
f.assign(N, 0);
}
void upd(int i, ll x) {
for (; i < N; i += i & (-i))
f[i] += x;
}
ll get(int i) {
ll s = 0;
for (; i; i -= i & (-i))
s += f[i];
return s;
}
};
fen fsum, fnum;
vector < vector <int>> all;
ll ans[N];
bool cmp(vector <int>&a, vector <int>&b) {
if (a[0] == b[0]) {
return a.back() > b.back();
}
return a[0] > b[0];
}
void dnc(int l, int r) {
if (l == r)
return;
int m = (l + r) / 2;
dnc(l, m);
dnc(m + 1, r);
vector < vector <int>> save;
for (int i = l; i <= m; i++) {
if (all[i].back() == 1) {
save.pb({all[i][1], all[i][2], all[i][3]});
}
}
for (int i = m + 1; i <= r; i++) {
if (all[i].back() == 0) {
save.pb({all[i][1], all[i][2], all[i][3]});
}
}
sort(all(save), cmp);
for (auto x : save) {
if (x.back() == 1) {
fsum.upd(abs(x[1]), x[1]);
if (x[1] >= 0) {
fnum.upd(abs(x[1]), 1);
} else {
fnum.upd(abs(x[1]), -1);
}
} else {
ll cur = fsum.get(x[1]);
if (fnum.get(x[1]) != 0) {
cur += x[1] + 1;
}
ans[x[1]] += cur;
}
}
for (auto x : save) {
if (x.back() == 1) {
fsum.upd(abs(x[1]), -x[1]);
if (x[1] >= 0) {
fnum.upd(abs(x[1]), -1);
} else {
fnum.upd(abs(x[1]), 1);
}
}
}
}
bool is[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
string s;
cin >> s;
s = "0" + s + "0";
set <int> st;
for (int i = 0; i < len(s); i++) {
if (s[i] == '0') {
if (i) {
int p = *(--st.end()) + 1;
if (p <= i - 1) {
all.pb({p, i - 1, -2, 1});
}
}
st.insert(i);
}
}
for (int i = 2; i <= q + 1; i++) {
string t;
cin >> t;
if (t[0] == 't') {
int p;
cin >> p;
if (s[p] == '0') {
st.erase(p);
s[p] = '1';
auto it = st.lower_bound(p);
int r = (*it) - 1, l = (*prev(it)) + 1;
all.pb({l, r, -i - 1, 1});
if (p - 1 >= l) {
all.pb({l, p - 1, i + 1, 1});
}
if (p + 1 <= r) {
all.pb({p + 1, r, i + 1, 1});
}
} else {
auto it = st.lower_bound(p);
int r = (*it) - 1, l = (*prev(it)) + 1;
all.pb({l, r, i + 1, 1});
if (p - 1 >= l) {
all.pb({l, p - 1, -i - 1, 1});
}
if (p + 1 <= r) {
all.pb({p + 1, r, -i - 1, 1});
}
s[p] = '0';
st.insert(p);
}
} else {
is[i] = 1;
int a, b;
cin >> a >> b;
all.pb({a, b - 1, i, 0});
}
}
sort(all(all), [&](vector <int> &a, vector <int> &b) {return a[0] == b[0] ? a.back() > b.back() : a[0] < b[0];});
dnc(0, sz(all) - 1);
for (int i = 2; i <= q + 1; i++) {
if (is[i] == 1) {
cout << ans[i] << '\n';
}
}
}
/*
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 |
5 ms |
18008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1147 ms |
59892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
18268 KB |
Output is correct |
| 2 |
Correct |
7 ms |
18520 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
18268 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
18268 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
18264 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
18008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
