#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const int N = 3e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7 , P = 6547;
int a[N];
int f[N];
int n , q;
int getS(int x) {
int res = 0;
while(x > 0) {
res += f[x];
x &= x+1;
x --;
}
return res;
}
int upd(int pos , int op = 1) {
for(; pos < N; pos |= pos+1) {
f[pos] += op;
}
}
int getl(int i) {
int res = i;
int l = 1 , r = i-1;
while(l <= r) {
int md = l+r >> 1;
if(getS(i-1) - getS(md-1) == i-md) {
res = md;
r = md-1;
}
else {
l = md+1;
}
}
return res;
}
int getr(int i) {
int res = i;
int l = i+1 , r = n+1;
while(l <= r) {
int md = l+r >> 1;
if(getS(md-1) - getS(i-1) == md-i) {
res = md;
l = md+1;
}
else {
r = md-1;
}
}
return res;
}
struct DO2D{
int l , r , d1;
int y1 , y2 , op = 0;
}t[20*N];
int sz2D = 1 , sz1D = 0;
struct DO1D{
int l , r;
int val = 0 , op = 0;
}t1[20*N];
void push1(int u) {
if(t1[u].op != 0) {
int l = t1[u].l , r = t1[u].r;
t1[l].val += t1[u].op;
t1[r].val += t1[u].op;
t1[l].op += t1[u].op;
t1[r].op += t1[u].op;
t1[u].op = 0;
}
}
void UPD1(int l, int r , int op , int u , int ul = 1, int ur = n+1) {
if(t1[u].l == 0) t1[u].l = ++sz1D;
if(t1[u].r == 0) t1[u].r = ++sz1D;
if(l <= ul && ur <= r) {
t1[u].val += op;
t1[u].op = op;
///cout <<"FLOW "<< t1[u].val << '\n';
return;
}
if(r < ul || ur < l) return;
push1(u);
int um = ul+ur >> 1;
UPD1(l , r , op , t1[u].l , ul , um);
UPD1(l , r , op , t1[u].r , um+1 , ur);
}
void push(int u) {
if(t[u].op != 0) {
int y1 = t[u].y1 , y2 = t[u].y2 , op = t[u].op , l = t[u].l , r = t[u].r;
if(t[l].d1 == 0) t[l].d1 = ++sz1D;
if(t[r].d1 == 0) t[r].d1 = ++sz1D;
UPD1(y1 , y2 , op , t[l].d1);
UPD1(y1 , y2 , op , t[r].d1);
t[l].y1 = y1;
t[l].y2 = y2;
t[l].op += op;
t[r].y1 = y1;
t[r].y2 = y2;
t[r].op += op;
t[u].op = 0;
}
}
void UPD(int x1 , int x2 , int y1 , int y2 , int op , int u = 1, int ul = 1, int ur = n+1) {
if(t[u].l == 0) t[u].l = ++sz2D;
if(t[u].r == 0) t[u].r = ++sz2D;
if(x1 <= ul && ur <= x2) {
if(t[u].d1 == 0) t[u].d1 = ++sz1D;
UPD1(y1 , y2 , op , t[u].d1);
t[u].y1 = y1;
t[u].y2 = y2;
t[u].op += op;
return;
}
if(ur < x1 || x2 < ul) return;
push(u);
int um = ul+ur >> 1;
UPD(x1 , x2 , y1 , y2 , op, t[u].l , ul , um);
UPD(x1 , x2 , y1 , y2 , op , t[u].r , um+1 , ur);
}
int get1(int pos , int u , int ul = 1, int ur = n+1) {
if(t1[u].l == 0) t1[u].l = ++sz1D;
if(t1[u].r == 0) t1[u].r = ++sz1D;
if(ur == ul) {
return t1[u].val;
}
push1(u);
int um = ul+ur >> 1;
if(pos <= um) {
return get1(pos , t1[u].l , ul , um);
}
else {
return get1(pos , t1[u].r , um+1 , ur);
}
}
int get(int x , int y , int u = 1, int ul = 1, int ur = n+1) {
if(t[u].l == 0) t[u].l = ++sz2D;
if(t[u].r == 0) t[u].r = ++sz2D;
if(ur == ul) {
if(t[u].d1 == 0) t[u].d1 = ++sz1D;
return get1(y , t[u].d1);
}
push(u);
int um = ul+ur >> 1;
if(x <= um) {
return get(x , y , t[u].l , ul , um);
}
else {
return get(x , y , t[u].r , um+1 , ur);
}
}
void solve() {
cin >> n >> q;
for(int i = 1; i <= n; i ++) {
char c;cin>>c;
if(c-48) {
int op;
if(a[i] == 1) {
upd(i , -1);
op = 1;
}
else {
upd(i , 1);
op = -1;
}
a[i] = 1-a[i];
int l = getl(i);
int r = getr(i+1);
UPD(l , i , i+1 , r , op);
}
}
int curtime = 1;
while(q --) {
curtime ++;
string type;
cin >> type;
if(type == "query") {
int a , b;
cin >> a >> b;
int g = get(a , b);
// cout << g << ' ';
cout << g + (g < 0) * curtime << '\n';
}
else {
int i , op;
cin >> i;
if(a[i] == 1) {
upd(i , -1);
op = curtime;
}
else {
upd(i , 1);
op = -curtime;
}
a[i] = 1-a[i];
int l = getl(i);
int r = getr(i+1);
// cout << "TOG " << l << ' ' << i << ' ' << i+1 << ' ' << r << " " << op<< '\n';
UPD(l , i , i+1 , r , op);
}
}
}
/*
10 20
1111010011
toggle 3
toggle 1
toggle 5
toggle 5
toggle 7
query 7 10
query 6 8
query 6 8
toggle 7
toggle 4
toggle 4
toggle 3
toggle 8
toggle 8
toggle 3
query 4 6
*/
main() {
ios;
int tt = 1;
//cin >> tt;
while(tt --) {
solve();
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'int upd(int, int)':
street_lamps.cpp:33:1: warning: no return statement in function returning non-void [-Wreturn-type]
33 | }
| ^
street_lamps.cpp: In function 'int getl(int)':
street_lamps.cpp:39:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int md = l+r >> 1;
| ~^~
street_lamps.cpp: In function 'int getr(int)':
street_lamps.cpp:55:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int md = l+r >> 1;
| ~^~
street_lamps.cpp: In function 'void UPD1(int, int, int, int, int, int)':
street_lamps.cpp:101:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
101 | int um = ul+ur >> 1;
| ~~^~~
street_lamps.cpp: In function 'void UPD(int, int, int, int, int, int, int, int)':
street_lamps.cpp:137:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
137 | int um = ul+ur >> 1;
| ~~^~~
street_lamps.cpp: In function 'int get1(int, int, int, int)':
street_lamps.cpp:151:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
151 | int um = ul+ur >> 1;
| ~~^~~
street_lamps.cpp: In function 'int get(int, int, int, int, int)':
street_lamps.cpp:170:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
170 | int um = ul+ur >> 1;
| ~~^~~
street_lamps.cpp: At global scope:
street_lamps.cpp:250:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
250 | main() {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
422 ms |
476148 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
478 ms |
476396 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
451 ms |
476396 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
435 ms |
476496 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
422 ms |
476148 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
