#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
set<int> lpos, rpos;
int n, q;
vector<int> pfw[maxn];
vector<long long> FW[maxn];
int a[maxn], org[maxn];
int U[maxn], V[maxn], ty[maxn];
void fadd(int x, int y, bool type, int t){
for(x; x <= n+1; x+=x&(-x)){
if(!type)pfw[x].push_back(y);
else for(int idx = lower_bound(pfw[x].begin(), pfw[x].end(), y) - pfw[x].begin(); idx < pfw[x].size(); idx += idx&(-idx))FW[x][idx]+=t;
}
}
long long query(int x, int y){
long long re = 0;
for(x; x > 0; x-=x&(-x)){
for(int idx = upper_bound(pfw[x].begin(), pfw[x].end(), y) - pfw[x].begin() - 1; idx > 0; idx -= idx&(-idx))re += FW[x][idx];
}
return re;
}
void fadd_range(int a, int b, bool type, int t){
fadd(a, a, type, t);
fadd(a, b+1, type, -t);
fadd(b+1, a, type, -t);
fadd(b+1, b+1, type, t);
}
void new_range(int l, int r, int type, int t){
int fr = *prev(rpos.lower_bound(l)), fl = *lpos.upper_bound(l);
fadd_range(fr+1, fl, type, t);
fadd_range(fr+1, l, type, -t);
fadd_range(r+1, fl, type, -t);
lpos.insert(l);
rpos.insert(r);
}
void change_l(int l_old, int l_new, int type, int t){
int fr = *prev(rpos.lower_bound(l_old));
fadd_range(fr+1, l_old, type, t);
fadd_range(fr+1, l_new, type, -t);
lpos.erase(l_old);
lpos.insert(l_new);
}
void change_r(int r_old, int r_new, int type, int t){
int fl = *lpos.upper_bound(r_old);
fadd_range(r_old+1, fl, type, t);
fadd_range(r_new+1, fl, type, -t);
rpos.erase(r_old);
rpos.insert(r_new);
}
void del_range(int l, int r, int type, int t){
int fr = *prev(rpos.lower_bound(l)), fl = *lpos.upper_bound(r);
fadd_range(fr+1, fl, type, -t);
fadd_range(fr+1, l, type, t);
fadd_range(r+1, fl, type, t);
lpos.erase(l);
rpos.erase(r);
}
void turn_on(int pos, bool type, int t){
if(!a[pos-1] && !a[pos+1])new_range(pos, pos, type, t);
else if(a[pos-1] && !a[pos+1])change_r(pos-1, pos, type, t);
else if(!a[pos-1] && a[pos+1])change_l(pos+1, pos, type, t);
else {
fadd_range(pos, pos+1, type, t);
lpos.erase(pos+1);
rpos.erase(pos-1);
}
}
void turn_off(int pos, bool type, int t){
if(!a[pos-1] && !a[pos+1])del_range(pos, pos, type, t);
else if(a[pos-1] && !a[pos+1])change_r(pos, pos-1, type, t);
else if(!a[pos-1] && a[pos+1])change_l(pos, pos+1, type, t);
else {
fadd_range(pos, pos+1, type, -t);
lpos.insert(pos+1);
rpos.insert(pos-1);
}
}
void toggle(int pos, bool type, int t){
// cout << "TOGGLE " << pos << endl;
if(a[pos])turn_off(pos, type, t);
else turn_on(pos, type, t);
a[pos]^=1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
rpos.insert(0);
lpos.insert(n+1);
for(int i = 1; i <= n; i++){
char x;
cin >> x;
a[i] = (x-'0')^1;
if(a[i])turn_on(i, 0, 0);
}
for(int i = 0; i < q; i++){
string str;
cin >> str;
if(str == "query"){
ty[i] = 1;
cin >> U[i] >> V[i];
}
else {
cin >> V[i];
toggle(V[i], 0, 0);
}
}
lpos.clear();
rpos.clear();
rpos.insert(0);
lpos.insert(n+1);
for(int i = 0; i < q; i++){
if(!ty[i])a[V[i]]^=1;
}
for(int i = 1; i <= n+1; i++){
pfw[i].push_back(0);
sort(pfw[i].begin(), pfw[i].end());
pfw[i].erase(unique(pfw[i].begin(), pfw[i].end()), pfw[i].end());
FW[i].assign(pfw[i].size(), 0);
}
for(int i = 1; i <= n; i++){
if(a[i])turn_on(i, 1, 0);
}
for(int i = 0; i < q; i++){
// cout << i << endl;
// for(int j = 1; j <= n; j++)cout << a[j] << " ";
// cout << endl;
if(!ty[i]){
toggle(V[i], 1, i+1);
}
else {
int fr = *prev(rpos.lower_bound(U[i])), fl = *lpos.lower_bound(fr);
long long ans = query(U[i], V[i]);
if(fr+1 <= U[i] && V[i] <= fl)ans += i+1;
cout << ans << "\n";
}
}
}
Compilation message
street_lamps.cpp: In function 'void fadd(int, int, bool, int)':
street_lamps.cpp:15:9: warning: statement has no effect [-Wunused-value]
15 | for(x; x <= n+1; x+=x&(-x)){
| ^
street_lamps.cpp:17:95: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | else for(int idx = lower_bound(pfw[x].begin(), pfw[x].end(), y) - pfw[x].begin(); idx < pfw[x].size(); idx += idx&(-idx))FW[x][idx]+=t;
| ~~~~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'long long int query(int, int)':
street_lamps.cpp:23:9: warning: statement has no effect [-Wunused-value]
23 | for(x; x > 0; x-=x&(-x)){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
20056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
379 ms |
45708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
20568 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
20560 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
20316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
20056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
