#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int INF = 1e9 + 7;
const int MAXN = 3e5 + 5;
const int BLOCK = 4000;
char str[MAXN], tmp[20];
int sm[MAXN], a[MAXN], ans[MAXN];
int nx[MAXN], val[MAXN];
int seg[MAXN*4];
struct query {
int t, a, b;
} qry[MAXN];
struct sweep {
int t, a, b, val;
bool operator<(const sweep rhs) const {
if (rhs.b == b) {
if (t == rhs.t) {
if (a == rhs.a)
return val < rhs.val;
return a < rhs.a;
}
return t < rhs.t;
}
return b > rhs.b;
}
};
map<sweep,int> cparr;
map<pii,int> act;
int f(int ind) {
ind++;
int ret = 0;
while (ind) {
ret += sm[ind];
ind -= ind & -ind;
}
return ret;
}
void g(int ind, int v) {
ind++;
while (ind < MAXN) {
sm[ind] += v;
ind += ind & -ind;
}
}
void build(int l, int r, int k) {
seg[k] = 0;
if (l == r) return;
int m = (l+r) / 2;
build(l,m,k*2);
build(m+1,r,k*2+1);
}
void upd(int l, int r, int k, int x, int y, int v) {
if (x <= l && r <= y) { seg[k] += v; return; }
int m = (l+r) / 2;
if (x <= m) upd(l,m,k*2,x,y,v);
if (m < y) upd(m+1,r,k*2+1,x,y,v);
}
int segqry(int l, int r, int k, int x) {
if (x <= l && r <= x) return seg[k];
int m = (l+r) / 2;
return seg[k] + (x <= m ? segqry(l,m,k*2,x) : segqry(m+1,r,k*2+1,x));
}
int main() {
clock_t tim = clock();
sm[0] = 0;
int n, q; scanf("%d %d", &n, &q);
scanf("%s", str+1);
for (int i = 1; i <= n; i++) {
a[i] = str[i]-'0', val[i] = a[i];
g(i,a[i]);
}
for (int j = 1; j <= q; j++) {
scanf("%s", tmp);
if (tmp[0] == 't') {
qry[j].t = 1;
scanf("%d", &qry[j].a);
} else {
qry[j].t = 2;
scanf("%d %d", &qry[j].a, &qry[j].b);
}
}
for (int j = 1; j <= n; j++) {
if (a[j] == 0) continue;
int k = j;
for (; k <= n && a[k] == 1; k++);
act[mp(j,k-1)] = 1;
nx[j] = k-1;
nx[k-1] = j;
j = k-1;
}
int curm = 0;
for (int i = 1; i <= q; i += BLOCK) {
for (int j = max(1,i-BLOCK); j < i; j++) {
if (qry[j].t == 2) continue;
int ind = qry[j].a;
if (!val[ind]) {
int lo = ind, hi = ind;
if (val[ind-1]) {
lo = nx[ind-1];
auto it = act.find(mp(lo,ind-1));
cparr[{1, lo, ind-1, 0}] += j-it->se+1;
act.erase(it);
nx[ind-1] = 0;
}
if (val[ind+1]) {
hi = nx[ind+1];
auto it = act.find(mp(ind+1,hi));
cparr[{1, ind+1, hi, 0}] += j-it->se+1;
act.erase(it);
nx[ind+1] = 0;
}
act[mp(lo,hi)] = j+1;
nx[lo] = hi;
nx[hi] = lo;
} else {
auto it = prev(act.upper_bound(mp(ind,INF)));
int lo = it->fi.fi, hi = it->fi.se;
cparr[{1, lo, hi, 0}] += j-it->se+1;
act.erase(it);
nx[lo] = nx[hi] = 0;
if (lo < ind) {
act[mp(lo,ind-1)] = j+1;
nx[lo] = ind-1;
nx[ind-1] = lo;
}
if (ind < hi) {
act[mp(ind+1,hi)] = j+1;
nx[ind+1] = hi;
nx[hi] = ind+1;
}
}
val[ind] ^= 1;
}
//for (int j = 1; j <= n; j++) sm[j] = sm[j-1] + a[j];
for (int j = i; j <= min(q,i+BLOCK-1); j++) {
if (qry[j].t == 1) continue;
cparr[{2, qry[j].a, qry[j].b-1, j}] = 0;
//int cur = sm[qry[j].b-1] - sm[qry[j].a-1];
int cur = f(qry[j].b-1)-f(qry[j].a-1);
int ind = cur == qry[j].b-qry[j].a ? i : j;
if (!act.empty()) {
auto it = act.upper_bound(mp(qry[j].a,INF));
if (it != act.begin()) {
it = prev(it);
if (it->fi.fi <= qry[j].a && qry[j].b-1 <= it->fi.se)
ans[j] += ind-it->se+1;
}
}
vector<int> x;
for (int k = i; k < j; k++) {
if (qry[k].t == 1 && qry[j].a <= qry[k].a && qry[k].a < qry[j].b) {
x.pb(qry[k].a);
a[qry[k].a] ^= 1;
cur += 2*a[qry[k].a]-1;
}
ans[j] += (int)(cur == qry[j].b-qry[j].a);
}
for (auto j: x) a[j] ^= 1;
}
build(1,n,1);
for (auto it: cparr) {
sweep cur = it.fi;
if (cur.t == 1)
upd(1,n,1,cur.a,cur.b,it.se);
else
ans[cur.val] += segqry(1,n,1,cur.a);
}
for (int j = i; j <= min(q,i+BLOCK-1); j++)
if (qry[j].t == 1) {
g(qry[j].a,(1^a[qry[j].a])-a[qry[j].a]);
a[qry[j].a] ^= 1;
} else {
cparr.erase({2, qry[j].a, qry[j].b-1, j});
printf("%d\n", ans[j]);
}
}
cerr << clock() - tim << "\n";;
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:107:6: warning: unused variable 'curm' [-Wunused-variable]
int curm = 0;
^~~~
street_lamps.cpp:82:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, q; scanf("%d %d", &n, &q);
~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", str+1);
~~~~~^~~~~~~~~~~~~
street_lamps.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", tmp);
~~~~~^~~~~~~~~~~
street_lamps.cpp:92:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &qry[j].a);
~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:95:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &qry[j].a, &qry[j].b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2409 ms |
6552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
