#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct Seg1{
int tree[1201200], sz;
void init(int i, int l, int r, char s[]){
if (i==1) sz = r;
if (l==r){tree[i] = s[l]-'0'; return;}
int m = (l+r)>>1;
init(i<<1, l, m, s); init(i<<1|1, m+1, r, s);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
int update(int i, int l, int r, int p){
if (r<p || p<l) return 0;
if (l==r) {tree[i] ^= 1; return tree[i];}
int m = (l+r)>>1;
int ret = update(i<<1, l, m, p) + update(i<<1|1, m+1, r, p);
tree[i] = tree[i<<1] + tree[i<<1|1];
return ret;
}
pair<int, int> _search(int i, int l, int r, int p, int x){
if (tree[i]==(r-l+1) * x) return {l, r};
if (l==r) return {-1, -1};
int m = (l+r)>>1;
if (r<p || (m+1 <= p && p <= r)){
auto ret = _search(i<<1|1, m+1, r, p, x);
if (ret.first != m+1) return ret;
auto ret2 = _search(i<<1, l, m, p, x);
if (ret2.second==-1) return ret;
return {ret2.first, ret.second};
}
else{
auto ret = _search(i<<1, l, m, p, x);
if (ret.second != m) return ret;
auto ret2 = _search(i<<1|1, m+1, r, p, x);
if (ret2.first==-1) return ret;
return {ret.first, ret2.second};
}
}
pair<pair<int, int>, int> calc(int p, bool no = 0){
if (no) update(1, 1, sz, p);
int x = update(1, 1, sz, p);
auto ret = _search(1, 1, sz, p, x);
return {ret, x};
}
void toggle(int p){update(1, 1, sz, p);}
}tree1;
struct Seg2{
ll tree[600600], sz;
vector<int> st;
void init(int n){
sz = n;
for (auto &x:st) tree[x] = 0;
st.clear();
}
void update(int l, int r, int x){
++r;
//printf(" update: %d %d %d\n", l, r, x);
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1){
st.push_back(l);
tree[l] += x;
l++;
}
if (r&1){
--r;
st.push_back(r);
tree[r] += x;
}
}
}
ll query(int p){
//printf(" query: %d\n", p);
ll ret = 0;
for (p+=sz;p;p>>=1) ret += tree[p];
return ret;
}
}tree2;
char buf[1010];
struct Query{
int a, b, i, typ;
Query(){}
void input(int _i){
i = _i;
scanf("%s", buf);
if (buf[0]=='q'){
scanf("%d %d", &a, &b);
typ = 1;
--b;
}
else{
scanf("%d", &a);
b = -1;
typ = 0;
}
}
}query[300300];
struct Query2{
int x, y1, y2, z, typ;
Query2(){}
Query2(int _x, int _y1, int _y2, int _z, int _typ): x(_x), y1(_y1), y2(_y2), z(_z), typ(_typ) {}
bool operator < (const Query2 &Q) const{
if (x==Q.x) return typ < Q.typ;
return x < Q.x;
}
};
char s[300300];
int n, q;
ll ans[300300];
void process(const vector<Query> &T, const vector<Query> &Q){
vector<Query2> V;
for (auto &[a, b, i, typ]:T){
assert(typ==0);
auto [p, x] = tree1.calc(a);
auto [l, r] = p;
//printf("%d %d %d\n", l, r, x);
assert(l!=-1);
int add = x?(q-i):(i-q);
V.emplace_back(l, a, r, add, 0);
V.emplace_back(a+1, a, r, -add, 0);
}
for (auto &[a, b, i, typ]:Q){
assert(typ==1);
V.emplace_back(a, b, -1, i, 1);
}
sort(V.begin(), V.end());
tree2.init(n+3);
for (auto &[x, y1, y2, z, typ]:V){
if (typ==0) tree2.update(y1, y2, z);
else ans[z] += tree2.query(y1);
//if (typ==1) printf("%d -> add %lld\n", z, tree2.query(y1));
}
}
void dnc(int l, int r){
if (l==r){
if (query[l].typ==0) return;
auto [p, x] = tree1.calc(query[l].a, 1);
if (p.second >= query[l].b && x==1){
ans[query[l].i] -= q-query[l].i;
}
return;
}
int m = (l+r)>>1;
dnc(l, m);
vector<Query> T, Q;
for (int i=l;i<=m;i++) if (query[i].typ==0) T.push_back(query[i]);
for (int i=m+1;i<=r;i++) if (query[i].typ==1) Q.push_back(query[i]);
process(T, Q);
dnc(m+1, r);
for (auto &[a, b, i, typ]:T) tree1.toggle(a);
}
int main(){
scanf("%d %d", &n, &q);
scanf("%s", s+1);
tree1.init(1, 1, n, s);
for (int i=1;i<=q;i++){
query[i].input(i);
if (query[i].typ==1){
auto [p, x] = tree1.calc(query[i].a, 1);
if (p.second >= query[i].b && x==1) ans[i] += q;
}
}
dnc(1, q);
for (int i=1;i<=q;i++) printf("%lld\n", ans[i]);
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:180:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
180 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:181:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
181 | scanf("%s", s+1);
| ~~~~~^~~~~~~~~~~
street_lamps.cpp: In member function 'void Query::input(int)':
street_lamps.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%s", buf);
| ~~~~~^~~~~~~~~~~
street_lamps.cpp:101:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:106:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d", &a);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
813 ms |
23672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
