#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], num[N], sum[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 {
sum[x[1]] += fsum.get(x[1]);
num[x[1]] += fnum.get(x[1]);
}
}
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);
//freopen("a.inp", "r", stdin);
//freopen("a.out", "w", stdout);
mem(ans, 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, -1, 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.upper_bound(p);
int r = (*it) - 1, l = (*prev(it)) + 1;
all.pb({l, r, -i, 1});
//cout << "add " << l << " " << r << '\n';
if (p - 1 >= l) {
all.pb({l, p - 1, i, 1});
//cout << "del " << l << " " << p - 1 << '\n';
}
if (p + 1 <= r) {
all.pb({p + 1, r, i, 1});
//cout << "del " << p + 1 << " " << r << '\n';
}
} else {
auto it = st.upper_bound(p);
int r = (*it) - 1, l = (*prev(it)) + 1;
all.pb({l, r, i, 1});
//cout << "del " << l << " " << r << '\n';
if (p - 1 >= l) {
all.pb({l, p - 1, -i, 1});
//cout << "add " << l << " " << p - 1 << '\n';
}
if (p + 1 <= r) {
all.pb({p + 1, r, -i, 1});
//cout << "add " << p + 1 << " " << r << '\n';
}
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 = 1; i <= q + 10; i++) {
if (is[i] == 1) {
ll all = sum[i];
if (num[i] != 0)
all += i;
cout << all << '\n';
}
}
}
/*
3 3
011
toggle 2
toggle 3
query 3 4
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
21084 KB |
Output is correct |
2 |
Correct |
5 ms |
21080 KB |
Output is correct |
3 |
Correct |
4 ms |
21236 KB |
Output is correct |
4 |
Correct |
5 ms |
21080 KB |
Output is correct |
5 |
Correct |
5 ms |
21084 KB |
Output is correct |
6 |
Correct |
4 ms |
21084 KB |
Output is correct |
7 |
Correct |
4 ms |
21084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1150 ms |
64952 KB |
Output is correct |
2 |
Correct |
1179 ms |
67380 KB |
Output is correct |
3 |
Correct |
1204 ms |
66156 KB |
Output is correct |
4 |
Correct |
1586 ms |
81556 KB |
Output is correct |
5 |
Correct |
1798 ms |
87388 KB |
Output is correct |
6 |
Correct |
1696 ms |
90364 KB |
Output is correct |
7 |
Correct |
643 ms |
73812 KB |
Output is correct |
8 |
Correct |
701 ms |
61036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
21336 KB |
Output is correct |
2 |
Correct |
8 ms |
21592 KB |
Output is correct |
3 |
Correct |
7 ms |
21252 KB |
Output is correct |
4 |
Correct |
5 ms |
21340 KB |
Output is correct |
5 |
Correct |
2103 ms |
89580 KB |
Output is correct |
6 |
Correct |
2303 ms |
91472 KB |
Output is correct |
7 |
Correct |
1886 ms |
79424 KB |
Output is correct |
8 |
Correct |
756 ms |
60484 KB |
Output is correct |
9 |
Correct |
380 ms |
46840 KB |
Output is correct |
10 |
Correct |
426 ms |
55804 KB |
Output is correct |
11 |
Correct |
471 ms |
55788 KB |
Output is correct |
12 |
Correct |
749 ms |
74604 KB |
Output is correct |
13 |
Correct |
747 ms |
62840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
21336 KB |
Output is correct |
2 |
Correct |
6 ms |
21340 KB |
Output is correct |
3 |
Correct |
7 ms |
21340 KB |
Output is correct |
4 |
Correct |
8 ms |
21336 KB |
Output is correct |
5 |
Correct |
1104 ms |
71312 KB |
Output is correct |
6 |
Correct |
1357 ms |
74036 KB |
Output is correct |
7 |
Correct |
1629 ms |
81644 KB |
Output is correct |
8 |
Correct |
2062 ms |
93316 KB |
Output is correct |
9 |
Correct |
1481 ms |
66336 KB |
Output is correct |
10 |
Correct |
1641 ms |
79784 KB |
Output is correct |
11 |
Correct |
1415 ms |
66328 KB |
Output is correct |
12 |
Correct |
1667 ms |
79740 KB |
Output is correct |
13 |
Correct |
1383 ms |
66288 KB |
Output is correct |
14 |
Correct |
1720 ms |
80388 KB |
Output is correct |
15 |
Correct |
790 ms |
72320 KB |
Output is correct |
16 |
Correct |
769 ms |
60008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
21084 KB |
Output is correct |
2 |
Correct |
5 ms |
21080 KB |
Output is correct |
3 |
Correct |
4 ms |
21236 KB |
Output is correct |
4 |
Correct |
5 ms |
21080 KB |
Output is correct |
5 |
Correct |
5 ms |
21084 KB |
Output is correct |
6 |
Correct |
4 ms |
21084 KB |
Output is correct |
7 |
Correct |
4 ms |
21084 KB |
Output is correct |
8 |
Correct |
1150 ms |
64952 KB |
Output is correct |
9 |
Correct |
1179 ms |
67380 KB |
Output is correct |
10 |
Correct |
1204 ms |
66156 KB |
Output is correct |
11 |
Correct |
1586 ms |
81556 KB |
Output is correct |
12 |
Correct |
1798 ms |
87388 KB |
Output is correct |
13 |
Correct |
1696 ms |
90364 KB |
Output is correct |
14 |
Correct |
643 ms |
73812 KB |
Output is correct |
15 |
Correct |
701 ms |
61036 KB |
Output is correct |
16 |
Correct |
8 ms |
21336 KB |
Output is correct |
17 |
Correct |
8 ms |
21592 KB |
Output is correct |
18 |
Correct |
7 ms |
21252 KB |
Output is correct |
19 |
Correct |
5 ms |
21340 KB |
Output is correct |
20 |
Correct |
2103 ms |
89580 KB |
Output is correct |
21 |
Correct |
2303 ms |
91472 KB |
Output is correct |
22 |
Correct |
1886 ms |
79424 KB |
Output is correct |
23 |
Correct |
756 ms |
60484 KB |
Output is correct |
24 |
Correct |
380 ms |
46840 KB |
Output is correct |
25 |
Correct |
426 ms |
55804 KB |
Output is correct |
26 |
Correct |
471 ms |
55788 KB |
Output is correct |
27 |
Correct |
749 ms |
74604 KB |
Output is correct |
28 |
Correct |
747 ms |
62840 KB |
Output is correct |
29 |
Correct |
6 ms |
21336 KB |
Output is correct |
30 |
Correct |
6 ms |
21340 KB |
Output is correct |
31 |
Correct |
7 ms |
21340 KB |
Output is correct |
32 |
Correct |
8 ms |
21336 KB |
Output is correct |
33 |
Correct |
1104 ms |
71312 KB |
Output is correct |
34 |
Correct |
1357 ms |
74036 KB |
Output is correct |
35 |
Correct |
1629 ms |
81644 KB |
Output is correct |
36 |
Correct |
2062 ms |
93316 KB |
Output is correct |
37 |
Correct |
1481 ms |
66336 KB |
Output is correct |
38 |
Correct |
1641 ms |
79784 KB |
Output is correct |
39 |
Correct |
1415 ms |
66328 KB |
Output is correct |
40 |
Correct |
1667 ms |
79740 KB |
Output is correct |
41 |
Correct |
1383 ms |
66288 KB |
Output is correct |
42 |
Correct |
1720 ms |
80388 KB |
Output is correct |
43 |
Correct |
790 ms |
72320 KB |
Output is correct |
44 |
Correct |
769 ms |
60008 KB |
Output is correct |
45 |
Correct |
693 ms |
57044 KB |
Output is correct |
46 |
Correct |
718 ms |
49648 KB |
Output is correct |
47 |
Correct |
836 ms |
56448 KB |
Output is correct |
48 |
Correct |
1578 ms |
78284 KB |
Output is correct |
49 |
Correct |
488 ms |
57456 KB |
Output is correct |
50 |
Correct |
497 ms |
56296 KB |
Output is correct |
51 |
Correct |
490 ms |
56564 KB |
Output is correct |
52 |
Correct |
479 ms |
58472 KB |
Output is correct |
53 |
Correct |
487 ms |
57840 KB |
Output is correct |
54 |
Correct |
477 ms |
56880 KB |
Output is correct |