#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i)
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i)
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true; return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true; return false;
}
using ll = long long;
using ld = long double;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); }
template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); }
const int MAX = 3e5 + 5;
const int inf = 1e9 + 9;
int n, q;
string s;
set<pair<int, int>> onSegments;
ll ans[MAX];
struct event{
int t, type, l, r; //t is order of query
};
struct Fenwick{
vector<int> bit_cnt;
vector<ll> bit_sum;
Fenwick(int n) : bit_cnt(n + 1, 0), bit_sum(n + 1, 0) {}
void upd(int id, int cnt, int sum){
for(; id > 0; id -= id & (-id)){
bit_cnt[id] += cnt;
bit_sum[id] += sum;
}
}
pair<int, ll> qry(int id){
int total_cnt = 0;
ll total_sum = 0;
for(; id < sz(bit_cnt); id += id & (-id)){
total_cnt += bit_cnt[id];
total_sum += bit_sum[id];
}
return {total_cnt, total_sum};
}
};
void cdq(int l, int r, vector<event>& events, Fenwick& fenwick){
if(l >= r) return;
int mid = l + r >> 1;
vector<int> upds, qrys;
FOR(i, l, mid) if(events[i].type != 0) upds.push_back(i);
FOR(i, mid + 1, r) if(events[i].type == 0) qrys.push_back(i);
if(upds.empty() || qrys.empty());
else{
sort(all(upds), [&](int i, int j){ return events[i].l < events[j].l; });
sort(all(qrys), [&](int i, int j){ return events[i].l < events[j].l; });
vector<pair<int, int>> saves;
int j = 0;
rep(i, 0, sz(qrys)){
while(j < sz(upds) && events[upds[j]].l <= events[qrys[i]].l){
fenwick.upd(events[upds[j]].r, +1, events[upds[j]].t * events[upds[j]].type);
saves.push_back({events[upds[j]].r, events[upds[j]].t * events[upds[j]].type});
++j;
}
int num_cnt; ll num_sum;
tie(num_cnt, num_sum) = fenwick.qry(events[qrys[i]].r);
ans[events[qrys[i]].t] += 1LL * num_cnt * events[qrys[i]].t - num_sum;
// cout << dbg(events[qrys[i]].t) << dbg(num_cnt) << ' ' << num_sum << '\n';
}
while(!saves.empty()){
fenwick.upd(saves.back().first, -1, -saves.back().second);
saves.pop_back();
}
}
cdq(l, mid, events, fenwick);
cdq(mid + 1, r, events, fenwick);
}
void testcase(){
cin >> n >> q >> s;
s = '?' + s;
vector<event> events;
FOR(i, 1, n){
if(s[i] == '1'){
int j = i;
while(j < n && s[j + 1] == '1') ++j;
onSegments.insert({i, j});
events.push_back({0, +1, i, j});
i = j;
}
}
vector<int> queries;
FOR(t, 1, q){
string type;
cin >> type;
if(type == "toggle"){
int i;
cin >> i;
if(s[i] == '1'){ //off
auto it = onSegments.upper_bound({i, inf}); --it;
int x, y;
tie(x, y) = *it;
onSegments.erase(it);
events.push_back({t, -1, x, y});
if(s[i - 1] == '1'){
onSegments.insert({x, i - 1});
events.push_back({t, +1, x, i - 1});
}
if(s[i + 1] == '1'){
onSegments.insert({i + 1, y});
events.push_back({t, +1, i + 1, y});
}
s[i] = '0';
} else{ //on
int x = i, y = i;
if(s[i - 1] == '1'){
auto it = onSegments.upper_bound({i - 1, inf}); --it;
x = it -> first;
events.push_back({t, -1, x, i - 1});
onSegments.erase(it);
}
if(s[i + 1] == '1'){
auto it = onSegments.upper_bound({i + 1, inf}); --it;
y = it -> second;
events.push_back({t, -1, i + 1, y});
onSegments.erase(it);
}
events.push_back({t, +1, x, y});
onSegments.insert({x, y});
s[i] = '1';
}
} else{
int l, r;
cin >> l >> r;
--r;
events.push_back({t, 0, l, r});
queries.push_back(t);
}
}
// for(auto it : events){
// cout << dbg(it.t) << dbg(it.l) << dbg(it.r) << dbg(it.type) << '\n';
// }
Fenwick fenwick(n);
cdq(0, sz(events) - 1, events, fenwick);
for(int i : queries){
cout << ans[i] << '\n';
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
#define filename "task"
if(fopen(filename".inp", "r")){
freopen(filename".inp", "r", stdin);
freopen(filename".out", "w", stdout);
}
int T = 1; //cin >> T;
while(T--) testcase();
return 0;
}
Compilation message
street_lamps.cpp: In function 'bool minimize(T&, const T&)':
street_lamps.cpp:15:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
15 | if(a > b) return a = b, true; return false;
| ^~
street_lamps.cpp:15:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
15 | if(a > b) return a = b, true; return false;
| ^~~~~~
street_lamps.cpp: In function 'bool maximize(T&, const T&)':
street_lamps.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
20 | if(a < b) return a = b, true; return false;
| ^~
street_lamps.cpp:20:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
20 | if(a < b) return a = b, true; return false;
| ^~~~~~
street_lamps.cpp: In function 'void cdq(int, int, std::vector<event>&, Fenwick&)':
street_lamps.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int mid = l + r >> 1;
| ~~^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:200:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
200 | freopen(filename".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:201:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
201 | freopen(filename".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
331 ms |
19788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
