#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define f first
#define s second
using namespace std;
const int mxn=3e5+5;
const int inf=1e9;
int a[mxn];
ll ans[mxn] = {};
int n;
struct segtree {
int tree[4 * mxn + 1];
void Set(int node,int b,int e,int p,int v) {
if(e < p || b > p)return;
if(b == e) {
tree[node] = v;
return;
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
Set(left,b,mid,p,v);
Set(right,mid+1,e,p,v);
tree[node] = tree[left] + tree[right];
}
void update(int node,int b,int e,int p,int v) {
if(e < p || b > p)return;
if(b == e) {
tree[node]+=v;
return;
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
update(left,b,mid,p,v);
update(right,mid+1,e,p,v);
tree[node] = tree[left] + tree[right];
}
int query(int node,int b,int e,int l,int r) {
if(e < l || b > r) return 0;
if(b >= l && e <= r) {
return tree[node];
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
return query(left,b,mid,l,r) + query(right,mid+1,e,l,r);
}
} st1,st2;
struct QUERY {
int l,r,ind,i;
int val;
QUERY(int a = 0,int b = 0,int c = 0,int d = -1 ,int v = 0) : l(a),r(b),ind(c),i(d),val(v) {}
};
vector<QUERY> Qs;
void process(vector<QUERY> left,vector<QUERY> right) {
vector<pair<pii,int>> v;
for(int i = 0; i < left.size(); i++) {
v.push_back(mp(mp(left[i].l,-1),i));
v.push_back(mp(mp(left[i].i,2),i));
}
for(int i = 0; i < right.size(); i++) {
v.push_back(mp(mp(right[i].l,0),i));
//v.emplace_back(right[i].r,1,i);
}
sort(v.begin(),v.end());
ll cursum = 0;
for(auto i : v) {
if(i.f.s == -1) {
//cout<<left[i.s].l<<" -- "<<left[i.s].r<<" -- "<<left[i.s].i<<endl;
cursum += left[i.s].val;
st1.update(1,1,n,left[i.s].r,left[i.s].val);
st2.update(1,1,n,left[i.s].i,left[i.s].val);
}
if(i.f.s == 2) {
cursum -= left[i.s].val;
st1.update(1,1,n,left[i.s].r,-left[i.s].val);
st2.update(1,1,n,left[i.s].i,-left[i.s].val);
}
if(i.f.s == 0) {
ll x = st1.query(1,1,n,1,right[i.s].r - 1);
ll y = st2.query(1,1,n,right[i.s].r + 1,n);
//cout<<cursum<<" "<<x<<" "<<y<<" "<<right[i.s].r<<endl;
ans[right[i.s].ind] += cursum - x - y;
}
}
}
int main() {
int k;
cin >> n >> k;
string s;
cin >> s;
for(int i = 1; i <= n; i++) {
a[i] = s[i - 1] - '0';
}
segtree cur;
vector<QUERY> left,right;
for(int i = 1; i <= n; i++) {
cur.update(1,1,n,i,a[i]);
}
char p[7];
for(int i = 1; i <= k; i++) {
scanf("%s",p);
if(p[0] == 't') {
int x;
scanf("%d",&x);
QUERY q;
if(a[x] == 0)
cur.Set(1,1,n,x,1);
int lo = 1;
int hi = x;
while(lo <= hi) {
int mid = lo + hi >> 1;
if(cur.query(1,1,n,mid,x) == x - mid + 1) {
q.l = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
lo = x;
hi = n;
while(lo <= hi) {
int mid = lo + hi >> 1;
if(cur.query(1,1,n,x,mid) == mid - x + 1) {
q.r = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
q.ind = i;
q.i = x;
if(a[x] == 0) q.val = -i;
else q.val = i;
if(a[x] == 1) {
cur.Set(1,1,n,x,0);
}
a[x] ^= 1;
//Qs.push_back(q);
left.push_back(q);
} else {
int a,b;
scanf("%d%d",&a,&b);
//Qs.push_back(QUERY(a,b,i));
right.push_back(QUERY(a,b,i));
if(cur.query(1,1,n,a,b) == b - a + 1) {
ans[i] = i;
}
}
}
process(left,right);
for(auto i : right) {
cout<<ans[i.ind]<<endl;
}
}
Compilation message
street_lamps.cpp: In member function 'void segtree::Set(int, int, int, int, int)':
street_lamps.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int mid=b+e>>1;
| ~^~
street_lamps.cpp: In member function 'void segtree::update(int, int, int, int, int)':
street_lamps.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid=b+e>>1;
| ~^~
street_lamps.cpp: In member function 'int segtree::query(int, int, int, int, int)':
street_lamps.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid=b+e>>1;
| ~^~
street_lamps.cpp: In function 'void process(std::vector<QUERY>, std::vector<QUERY>)':
street_lamps.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<QUERY>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i = 0; i < left.size(); i++) {
| ~~^~~~~~~~~~~~~
street_lamps.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<QUERY>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i = 0; i < right.size(); i++) {
| ~~^~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:150:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
150 | int mid = lo + hi >> 1;
| ~~~^~~~
street_lamps.cpp:166:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
166 | int mid = lo + hi >> 1;
| ~~~^~~~
street_lamps.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
139 | scanf("%s",p);
| ~~~~~^~~~~~~~
street_lamps.cpp:142:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
142 | scanf("%d",&x);
| ~~~~~^~~~~~~~~
street_lamps.cpp:192:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
192 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
642 ms |
23704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
