#include <bits/stdc++.h>
using namespace std;
struct BIT{
vector<int> ip[300011], bit[300011];
void init(){
for(int i = 0; i < 300011; i++){
ip[i].push_back(0); sort(ip[i].begin(), ip[i].end());
ip[i].resize(unique(ip[i].begin(), ip[i].end()));
bit[i].resize(ip[i].size());
}
}
void init_add(int x, int y){
for(int i = x; i; i -= i & -i){
ip[i].push_back(y);
}
}
void add(int x, int y, int v){
for(int i = x; i < 300011; i += i & -i){
int y2 = lower_bound(bit[i].begin(), bit[i].end(), y) - bit[i].begin();
for(int j = y2; j < bit[i].size(); j += j & -j){
bit[i][j] += v;
}
}
}
int qry(int x, int y){
int ret = 0;
for(int i = x; i; i -= i & -i){
int y2 = upper_bound(bit[i].begin(), bit[i].end(), y) - bit[i].begin() - 1;
for(int j = y2; j; j -= j & -j){
ret += bit[i][j];
}
}
return ret;
}
} bit;
struct segment{
int l, r, t;
bool operator< (const segment& o) const {
return l < o.l || l == o.l && r < o.r;
}
};
vector<segment> segs[300011];
void add(const segment& s, int t2) {
cout << "ADD " << s.l << ' ' << s.r << ' ' << s.t << ' ' << t2 << endl;
init_add(s.l, s.r); segs[t2].push_back(s);
}
set<segment> S;
bool on[300011], isq[300011];
int L[300011], R[300011], rans[300011];
void show(){
for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
}
void toggle(int x, int t){
// cout << "TOGGLE " << x << ' ' << t << endl;
if(on[x]){
auto ptr = S.lower_bound({x, 1 << 30}); --ptr; int l = ptr->l, r = ptr->r; add(*ptr, t); S.erase(ptr);
if(on[x - 1]) { S.insert({l, x, t}); }
if(on[x + 1]) { S.insert({x + 1, r, t}); }
}else{
int l = x, r = x + 1;
if(on[x - 1]) { auto ptr = S.lower_bound({x, -1}); --ptr; l = ptr->l; add(*ptr, t); S.erase(ptr); }
if(on[x + 1]) { auto ptr = S.lower_bound({x, -1}); r = ptr->r; add(*ptr, t); S.erase(ptr); }
S.insert({l, r, t});
}
on[x] = !on[x];
// show();
}
void query(int l, int r, int t){
isq[t] = true; L[t] = l, R[t] = r;
auto ptr = S.lower_bound({l, 1 << 30});
if(ptr != S.begin() && prev(ptr)->l <= l && r <= prev(ptr)->r) rans[t] += t - prev(ptr)->t;
}
void query2(int l, int r, int t){
rans[t] += bit.qry(r, r) - bit.qry(l, r) - bit.qry(l, l) + bit.qry(r, r);
}
int32_t main(){
int n, q; cin >> n >> q;
string s; cin >> s; for(int i = 1; i <= n; i++) on[i] = s[i - 1] == '1';
vector<segment> v;
for(int i = 1; i <= n; i++) {
if(on[i]){
if(v.size() && v.back().r == i) v.back().r++; else v.push_back({i, i + 1, 0});
}
}
for(auto s : v) S.insert(s);
for(int t = 1; t <= q; t++){
string type; cin >> type;
if(type == "query"){
int l, r; cin >> l >> r;
query(l, r, t);
}else{
int x; cin >> x; toggle(x, t);
}
}
for(int t = 1; t <= q; t++){
for(auto s : segs[t]){
bit.add(s.l, s.r, t - s.t);
}
if(isq[t]){
query2(L[t], R[t], t);
}
}
for(int t = 1; t <= q; t++){
if(isq[t]){
cout << rans[t] << endl;
}
}
}
Compilation message
street_lamps.cpp: In member function 'void BIT::init()':
street_lamps.cpp:10:51: error: no matching function for call to 'std::vector<int>::resize(__gnu_cxx::__normal_iterator<int*, std::vector<int> >)'
10 | ip[i].resize(unique(ip[i].begin(), ip[i].end()));
| ^
In file included from /usr/include/c++/10/vector:67,
from /usr/include/c++/10/queue:61,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from street_lamps.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:937:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
937 | resize(size_type __new_size)
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:937:24: note: no known conversion for argument 1 from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' to 'std::vector<int>::size_type' {aka 'long unsigned int'}
937 | resize(size_type __new_size)
| ~~~~~~~~~~^~~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:957:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = int]'
957 | resize(size_type __new_size, const value_type& __x)
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:957:7: note: candidate expects 2 arguments, 1 provided
street_lamps.cpp: In member function 'void BIT::add(int, int, int)':
street_lamps.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int j = y2; j < bit[i].size(); j += j & -j){
| ~~^~~~~~~~~~~~~~~
street_lamps.cpp: In member function 'bool segment::operator<(const segment&) const':
street_lamps.cpp:42:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
42 | return l < o.l || l == o.l && r < o.r;
| ~~~~~~~~~^~~~~~~~~~
street_lamps.cpp: In function 'void add(const segment&, int)':
street_lamps.cpp:50:2: error: 'init_add' was not declared in this scope
50 | init_add(s.l, s.r); segs[t2].push_back(s);
| ^~~~~~~~
street_lamps.cpp: In function 'void show()':
street_lamps.cpp:58:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
58 | for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
| ^~~
street_lamps.cpp:58:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
58 | for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
| ^~~~
