//khodaya khodet komak kon
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 300000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;
int koj[N][LOG], n, q, a[N], F[N], R[N];
vi seg[N << 2],fen[N << 2], L[N];
set<int> One, Zero;
bool cmp(int x, int y){
return R[x] < R[y];
}
inline void add(int ind, int id, int x){
for (; id < fen[ind].size(); id += id & (-id)) fen[ind][id] += x;
}
inline int get(int ind, int id){
int res = 0;
for (; id > 0; id -= id & (-id)) res += fen[ind][id];
return res;
}
void build(int h, int id, int l, int r){
if (r - l == 1){
fen[id].pb(0);
for (auto u:L[l]) seg[id].pb(u), fen[id].pb(0);
sort(all(seg[id]), cmp);
// cout << "Seg " << l << ' ' << r - 1<<'\n';
// for (auto u:seg[id]) cout << R[u] << ' ';
for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
// cout << '\n';
return;
}
int md = (l + r) >> 1;
build(h + 1, id << 1, l, md);
build(h + 1, id << 1 |1 , md, r);
fen[id].pb(0);
for (auto u:seg[id << 1]) seg[id].pb(u), fen[id].pb(0);
for(auto u:seg[id << 1 | 1]) seg[id].pb(u), fen[id].pb(0);
sort(all(seg[id]), cmp);
for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
// cout << "Seg " << l << ' ' << r - 1 <<'\n';
// for (auto u:seg[id]) cout << R[u] << ' ';
// cout << '\n';
}
void Add(int id, int lq, int rq, int x, int t, int l, int r){
if (rq <= l || r <= lq) return;
if (lq <= l && r <= rq){
if (seg[id].size() == 0) return;
int LL = 0, RR = seg[id].size();
if (R[seg[id][0]] >= x) return;
while (RR - LL > 1){
int md = (LL + RR) >> 1;
if (R[seg[id][0]] < x) LL = md;
else RR = md;
}
int zar = 1;
add(id, 1, t);
add(id, r + 1, -t);
return;
}
int md = (l + r) >> 1;
Add(id << 1, lq, rq, x, t, l, md);
Add(id << 1 | 1, lq, rq, x, t, md, r);
}
void Add2(int id, int lq, int rq, int x, int t, int l, int r){
if (rq <= l || r <= lq) return;
if (lq <= l && r <= rq){
if (seg[id].size() == 0) return;
if (R[seg[id].back()] < x) return;
int LL = -1, RR = seg[id].size() - 1;
while (RR - LL > 1){
int md = (RR + LL) >> 1;
if (R[seg[id][md]] >= x) RR = md;
else LL = md;
}
// cout << "Query\n";
// cout << l << ' ' << r - 1 << ' ' << RR + 1 << ' ' << x << ' ';
add(id, RR + 1, t);
// cout << get(id, fen[id].size() - 1) << '\n';
return;
}
int md = (l + r) >> 1;
Add2(id << 1, lq, rq, x, t, l, md);
Add2(id << 1 | 1, lq, rq, x, t, md, r);
}
int Get(int h, int id, int lq, int rq, int x, int l, int r){
if (rq <= l || r <= lq)return 0;
if (lq <= l && r <= rq){
// cout << l << ' ' << r - 1 << ' ' << x << ' ' << koj[h][x] << ' ' << get(id, koj[h][x]) << '\n';
return get(id, koj[h][x]);
}
int res = get(id, koj[h][x]);
// cout << l << ' ' << r - 1 << ' ' << x << ' ' << koj[h][x] << ' ' <<res << '\n';
int md = (l + r) >> 1;
return (res + Get(h + 1, id << 1, lq, rq, x, l, md) + Get(h + 1, id << 1 | 1, lq, rq, x, md, r));
}
vector<pair<int, pii>> Q;
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
string s;
cin >> s;
Zero.insert(0);
Zero.insert(n + 1);
One.insert(0), One.insert(n + 1);
for (int i = 1; i <= n; i++) a[i] = (s[i - 1] == '1');
for (int i = 1; i <= n; i++){
if (a[i] == 1) One.insert(i);
else Zero.insert(i);
}
for (int i = 1; i <= q; i++){
cin >> s;
if (s == "query"){
int l, r;
cin >> l >> r;
r--;
R[i] = r;
L[l].pb(i);
Q.pb({1, {l, r}});
}else{
int x;
cin >> x;
Q.pb({2, {x, 0}});
}
}
build(0, 1, 1, n + 1);
for (int i = 1; i <= q; i++){
auto u = Q[i - 1];
int x = u.F;
if (x == 1){
int l = u.S.F, r = u.S.S;
int res = Get(0, 1, l, l + 1, i, 1, n + 1);
if (a[l] == 1){
auto koj = Zero.lower_bound(l);
if ((*koj) > r) res += i;
}
cout << res << '\n';
}else{
int l = u.S.F;
if (a[l] == 1){
a[l] = 0;
One.erase(l);
auto koj = Zero.lower_bound(l);
auto koj2 = koj;
koj2--;
// cout << (*koj2) + 1 << ' ' << l << ' ' << (*koj) << endl;
// cout << "YES" << endl;
Add(1, (*koj2) + 1, l + 1, (*koj), i, 1, n + 1);
// cout << "YES2" << endl;
Add(1, (*koj2) + 1, l + 1, l, -i, 1, n + 1);
Zero.insert(l);
}else{
a[l] = 1;
Zero.erase(l);
auto koj = Zero.lower_bound(l);
auto koj2 = koj;
koj2--;
// cout << "Fuck " << (*koj2) + 1 << ' ' << (*koj) << '\n';
Add2(1, (*koj2) + 1, l + 1, l, -i, 1, n + 1);
Add2(1, (*koj2) + 1, l + 1, (*koj), i, 1, n + 1);
One.insert(l);
}
}
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'void add(int, int, int)':
street_lamps.cpp:31:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (; id < fen[ind].size(); id += id & (-id)) fen[ind][id] += x;
~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void build(int, int, int, int)':
street_lamps.cpp:47:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
~~^~~~~~~~~~~~~~~~
street_lamps.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
~~^~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void Add(int, int, int, int, int, int, int)':
street_lamps.cpp:76:7: warning: unused variable 'zar' [-Wunused-variable]
int zar = 1;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
63744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
364 ms |
88180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
63992 KB |
Output is correct |
| 2 |
Incorrect |
39 ms |
64000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
64120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
63744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
