#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;
const int MX_N = 3e5+5;
const int MX_Q = 3e5+5;
int N, Q;
string S;
vector<array<int,2>> change;
vector<array<int,3>> query;
vector<array<int,4>> itv;
set<array<int,2>> cur;
int ans[MX_Q];
struct FenwickTree {
vector<ll> ft; int n;
void init(int _n) { n = _n; ft.assign(n+1,0); }
void update(int i, int x) { for (; i <= n; i += i&-i) ft[i] += x; }
ll query(int i) { ll s = 0; for (; i; i -= i&-i) s += ft[i]; return s; }
ll query(int i, int j) { return query(j)-query(i-1); }
} ft, ft2;
void cdq(int l, int r, vector<array<int,4>>& a, vector<array<int,3>>& b) {
if (l > r) return;
if (l == r) {
for (auto& x : a) {
ft.update(x[1], (x[3]?1:-1)*x[0]);
ft2.update(x[1], (x[3]?-1:1));
}
for (auto& y : b) {
ans[y[0]] += ft.query(y[1]);
ans[y[0]] += ft2.query(y[1]) * y[0];
}
for (auto& x : a) {
ft.update(x[1], -(x[3]?1:-1)*x[0]);
ft2.update(x[1], -(x[3]?-1:1));
}
return;
}
int m = (l+r) >> 1;
vector<array<int,4>> a1, a2;
for (auto& x : a) (x[0] <= m ? a1 : a2).push_back(x);
vector<array<int,3>> b1, b2;
for (auto& y : b) (y[0] <= m ? b1 : b2).push_back(y);
cdq(l,m,a1,b1);
cdq(m+1,r,a2,b2);
sort(ALL(a1), [](array<int,4> p, array<int,4> q){
return (p[2]>q[2]||(p[2]==q[2]&&(p[1]>q[1]||(p[1]==q[1]&&p[0]>q[0]))));
});
sort(ALL(b2), [](array<int,3> p, array<int,3> q){
return (p[2]>q[2]||(p[2]==q[2]&&(p[1]>q[1]||(p[1]==q[1]&&p[0]>q[0]))));
});
//TRACE(l _ r);
//for (auto& x : a) TRACE(x[0] _ x[1] _ x[2] _ x[3]);
//for (auto& y : b) TRACE(y[0] _ y[1] _ y[2]);
//cout << endl;
int i, j;
for (i = 0, j = 0; i < SZ(a1) || j < SZ(b2); ) {
if (i < SZ(a1) && (j >= SZ(b2) || a1[i][2] >= b2[j][2])) {
ft.update(a1[i][1], (a1[i][3]?1:-1)*a1[i][0]);
ft2.update(a1[i][1], (a1[i][3]?-1:1));
++i;
} else {
ans[b2[j][0]] += ft.query(b2[j][1]);
ans[b2[j][0]] += ft2.query(b2[j][1]) * b2[j][0];
++j;
}
}
for (;j < SZ(b2);) {
ans[b2[j][0]] += ft.query(b2[j][1]);
ans[b2[j][0]] += ft2.query(b2[j][1]) * b2[j][0];
++j;
}
FOR(k,0,i-1){
ft.update(a1[k][1], -(a1[k][3]?1:-1)*a1[k][0]);
ft2.update(a1[k][1], -(a1[k][3]?-1:1));
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> Q >> S; S = '^' + S + '0';
FOR(i,1,Q){
string T; cin >> T;
if (T == "toggle") {
int I; cin >> I;
change.push_back({i,I});
} else {
int A, B; cin >> A >> B;
--B;
query.push_back({i,A,B});
}
}
int len = 0;
FOR(i,1,N+1){
if (S[i] == '0') {
if (len) {
cur.insert({i-len,i-1});
itv.push_back({0,i-len,i-1,0});
}
len = 0;
} else ++len;
}
for (auto& x : change) {
//cout << x[1] << ' ' << x[1] << " vs ";
//for (auto& y : cur) cout << y[0] << ' ' << y[1] << " | ";
//cout << endl;
if (S[x[1]] == '0') {
auto it = cur.upper_bound({x[1],0});
array<int,2> y = {x[1],x[1]};
if (it != cur.end() && y[1]+1 == (*it)[0]) {
auto z = *it; cur.erase(it);
itv.push_back({x[0],z[0],z[1],1});
y[1] = z[1];
it = cur.upper_bound({x[1],0});
}
if (it != cur.begin() && (*(--it))[1]+1 == y[0]) {
auto z = *it; cur.erase(it);
itv.push_back({x[0],z[0],z[1],1});
y[0] = z[0];
}
cur.insert(y);
itv.push_back({x[0],y[0],y[1],0});
S[x[1]] = '1';
} else {
auto it = cur.upper_bound({x[1],0});
assert(it != cur.begin());
auto y = *(--it); cur.erase(it);
assert(y[1] >= x[1]);
itv.push_back({x[0],y[0],y[1],1});
if (y[0] < x[1]) {
cur.insert({y[0],x[1]-1});
itv.push_back({x[0],y[0],x[1]-1,0});
}
if (x[1] < y[1]) {
cur.insert({x[1]+1,y[1]});
itv.push_back({x[0],x[1]+1,y[1],0});
}
S[x[1]] = '0';
}
}
for (auto& x : cur) {
itv.push_back({Q,x[0],x[1],1});
}
//for (auto& x : itv) { TRACE(x[0] _ x[1] _ x[2] _ x[3]); }
memset(ans,0,sizeof ans);
ft.init(N);
ft2.init(N);
cdq(0,Q,itv,query);
for (auto& q : query) {
cout << ans[q[0]] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
71 ms |
7024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1664 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1664 KB |
Output is correct |
| 3 |
Correct |
8 ms |
1664 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1664 KB |
Output is correct |
| 5 |
Correct |
1328 ms |
41916 KB |
Output is correct |
| 6 |
Correct |
1431 ms |
56204 KB |
Output is correct |
| 7 |
Correct |
1200 ms |
56476 KB |
Output is correct |
| 8 |
Correct |
501 ms |
18472 KB |
Output is correct |
| 9 |
Correct |
309 ms |
10208 KB |
Output is correct |
| 10 |
Correct |
337 ms |
12508 KB |
Output is correct |
| 11 |
Correct |
330 ms |
12380 KB |
Output is correct |
| 12 |
Correct |
488 ms |
18600 KB |
Output is correct |
| 13 |
Correct |
494 ms |
18480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
