#include <bits/stdc++.h>
using namespace std;
#define MAX_QUERY_NUMBER 1200005
#define MAXF 300005
#define QUERY_OPT 0
#define UPDATE_OPT 1
#define DUMMY 0
struct Query {
// type == QUERY_OPT: query for ans_id, val is not relevent;
// type == UPDATE_OPT: update with val, ans_id is not relevent.
int x, y, val, type, ans_id;
};
Query queries[MAX_QUERY_NUMBER];
Query sorted_queries[MAX_QUERY_NUMBER];
int ans[MAXF];
inline int lowbit( int num ) { return num&(-num); }
namespace BIT {
int c[MAXF] = {0};
void add( int x, int v ) {
for( ; x <= MAXF-1; x += lowbit(x) ) {
c[x] += v;
}
}
int query( int x ) {
int sum = 0;
for( ; x; x -= lowbit(x) ) {
sum += c[x];
}
return sum;
}
void clear( ) {
memset(c, 0, sizeof(int) * MAXF);
}
}
void solve(int l, int r) {
if (r - l <= 1) return;
int m = (l + r) / 2;
solve(l, m);
solve(m, r);
int p = l, q = m, t = l;
while (p < m && q < r) {
if (queries[p].x <= queries[q].x) {
if (queries[p].type == UPDATE_OPT) {
BIT::add(queries[p].y, queries[p].val);
}
sorted_queries[t++] = queries[p];
p++;
} else {
if (queries[q].type == QUERY_OPT) {
ans[queries[q].ans_id] += BIT::query(queries[q].y);
}
sorted_queries[t++] = queries[q];
q++;
}
}
while (q < r) {
if (queries[q].type == QUERY_OPT) {
ans[queries[q].ans_id] += BIT::query(queries[q].y);
}
sorted_queries[t++] = queries[q];
q++;
}
while (p < m) {
sorted_queries[t++] = queries[p++];
}
for (int i = l; i < r; i++) {
queries[i] = sorted_queries[i];
}
BIT::clear();
return;
}
struct comp {
inline bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
return a.second < b.second;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
set< pair<int, int>, comp> st;
for (int i = 1; i <= n + 1; i++) {
st.insert({i, i});
}
string s;
cin >> s;
for (int i = 1; i <= n; i++) {
if (s[i - 1] == '1') {
auto it = st.upper_bound({0, i});
pair<int, int> tmp = {prev(it)->first, it->second};
st.erase(prev(it)); st.erase(it);
st.insert(tmp);
}
}
int idx = 0, ans_number = 0;
for (int cur = 1; cur <= q; cur++) {
string t;
cin >> t;
if (t == "query") {
int l, r;
cin >> l >> r;
if (st.lower_bound({0, l}) == st.lower_bound({0, r})) {
ans[ans_number] += cur;
}
queries[idx++] = (Query){l, r, DUMMY, QUERY_OPT, ans_number++};
} else {
int x;
cin >> x;
int i_1, j_1, i_2, j_2;
int val = cur;
if (s[x - 1] == '1') {
auto it = st.lower_bound({0, x});
i_1 = it->first;
j_1 = x + 1;
i_2 = x;
j_2 = it->second;
pair<int, int> tmp_1 = {it->first, x}, tmp_2 = {x + 1, it->second};
st.erase({it->first, it->second});
st.insert(tmp_1); st.insert(tmp_2);
s[x - 1] = '0';
} else {
auto it = st.upper_bound({0, x});
i_1 = prev(it)->first, i_2 = prev(it)->second, j_1 = it->first, j_2 = it->second;
pair<int, int> tmp = {i_1, j_2};
val = - val;
st.erase({i_1, i_2}); st.erase({j_1, j_2});
st.insert(tmp);
s[x - 1] = '1';
}
queries[idx++] = Query{i_1, j_1, val, UPDATE_OPT, 0};
queries[idx++] = Query{i_1, j_2 + 1, - val, UPDATE_OPT, 0};
queries[idx++] = Query{i_2 + 1, j_1, - val, UPDATE_OPT, 0};
queries[idx++] = Query{i_2 + 1, j_2 + 1, val, UPDATE_OPT, 0};
}
}
solve(0, idx);
for (idx = 0; idx < ans_number; idx ++ ) {
cout << ans[idx] << "\n";
}
return 0;
}
Compilation message
street_lamps.cpp:78:2: error: stray '\302' in program
78 | for (int i = l; i < r; i++) {
| ^
street_lamps.cpp:78:3: error: stray '\240' in program
78 | for (int i = l; i < r; i++) {
| ^
street_lamps.cpp:79:2: error: stray '\302' in program
79 | queries[i] = sorted_queries[i];
| ^
street_lamps.cpp:79:3: error: stray '\240' in program
79 | queries[i] = sorted_queries[i];
| ^
street_lamps.cpp:79:5: error: stray '\302' in program
79 | queries[i] = sorted_queries[i];
| ^
street_lamps.cpp:79:6: error: stray '\240' in program
79 | queries[i] = sorted_queries[i];
| ^
