#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const ll NMAX = 300001;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;
int n;
class AINT{
public:
struct Node{
int sum, st, dr;
};
vector <Node> aint;
void update(int node, int st, int dr, int a, int b, int val){
debug("AICI");
debug(node);
if(!aint.size()){
aint.push_back({0, -1, -1});
}
if(a <= st && dr <= b){
aint[node].sum += val;
return;
}
int mid = (st + dr) / 2;
if(a <= mid){
if(aint[node].st == -1){
aint[node].st = aint.size();
aint.push_back({0, -1, -1});
}
update(aint[node].st, st, mid, a, b, val);
}
if(b > mid){
if(aint[node].dr == -1){
aint[node].dr = aint.size();
aint.push_back({0, -1, -1});
}
update(aint[node].dr, mid + 1, dr, a, b, val);
}
}
int query(int node, int st, int dr, int a){
if(node == -1 || !aint.size()){
return 0;
}
int aici = aint[node].sum;
if(st == dr)
return aici;
int mid = (st + dr) / 2;
if(a <= mid){
return aici + query(aint[node].st, st, mid, a);
}
return aici + query(aint[node].dr, mid + 1, dr, a);
}
}stt[NMAX * 4];
void update(int node, int st, int dr, int x1, int x2, int y1, int y2, int val){
if(x2 < x1) return;
if(y2 < y1) return;
if(x1 <= st && dr <= x2){
stt[node].update(0, 1, n, y1, y2, val);
return;
}
int mid = (st + dr) / 2;
if(x1 <= mid)
update(node * 2, st, mid, x1, x2, y1, y2, val);
if(x2 > mid)
update(node * 2 + 1, mid + 1, dr, x1, x2, y1, y2, val);
}
int query(int node, int st, int dr, int x, int y){
int aici = stt[node].query(0, 1, n, y);
if(st == dr){
return aici;
}
int mid = (st + dr) / 2;
if(x <= mid)
return aici + query(node * 2, st, mid, x, y);
return aici + query(node * 2 + 1, mid + 1, dr, x, y);
}
int a[NMAX];
string s[NMAX];
int qa[NMAX];
int qb[NMAX];
int aib[NMAX * 4];
void upd(int node, int val){
for(; node <= n; node += node&(-node))
aib[node] += val;
}
int qry(int node){
int val = 0;
for(; node; node -= node&(-node))
val += aib[node];
return val;
}
signed main() {
#ifdef HOME
ifstream cin(".in");
ofstream cout(".out");
#endif // HOME
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int i, q;
cin >> n >> q;
for(i = 1; i <= n; i++){
char c;
cin >> c;
a[i] = c - '0';
upd(i, a[i]);
}
for(i = 1; i <= q; i++){
cin >> s[i];
cin >> qa[i];
if(s[i][0] == 'q'){
cin >> qb[i];
qb[i]--;
cout << query(1, 1, n, qa[i], qb[i]) + i * ((qry(qb[i]) - qry(qa[i] - 1)) == (qb[i] - qa[i] + 1)) << "\n";
}else{
if(a[qa[i]] == 1){
int r = 0, pas = (1 << nrbits);
while(pas){
if(r + pas <= qa[i] && qry(qa[i]) - qry(r + pas - 1) != (qa[i] - (r + pas) + 1))
r += pas;
pas /= 2;
}
r++;
int st = r;
r = qa[i], pas = (1 << nrbits);
while(pas){
if(r + pas <= n && qry(r + pas) - qry(qa[i] - 1) == ((r + pas) - qa[i] + 1))
r += pas;
pas /= 2;
}
int dr = r;
update(1, 1, n, st, qa[i], qa[i], dr, i);
}else{
int r = 0, pas = (1 << nrbits);
while(pas){
if(r + pas < qa[i] && qry(qa[i]) - qry(r + pas - 1) != (qa[i] - (r + pas)))
r += pas;
pas /= 2;
}
r++;
int st = r;
r = qa[i], pas = (1 << nrbits);
while(pas){
if(r + pas <= n && qry(r + pas) - qry(qa[i] - 1) == ((r + pas) - qa[i]))
r += pas;
pas /= 2;
}
int dr = r;
update(1, 1, n, st, qa[i], qa[i], dr, -i);
}
upd(qa[i], -a[qa[i]]);
a[qa[i]] ^= 1;
upd(qa[i], a[qa[i]]);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
41836 KB |
Output is correct |
| 2 |
Correct |
11 ms |
41820 KB |
Output is correct |
| 3 |
Correct |
14 ms |
41992 KB |
Output is correct |
| 4 |
Correct |
14 ms |
41820 KB |
Output is correct |
| 5 |
Correct |
17 ms |
41904 KB |
Output is correct |
| 6 |
Correct |
10 ms |
41824 KB |
Output is correct |
| 7 |
Correct |
10 ms |
41976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5032 ms |
54268 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
232 ms |
42768 KB |
Output is correct |
| 2 |
Correct |
181 ms |
42476 KB |
Output is correct |
| 3 |
Correct |
147 ms |
42320 KB |
Output is correct |
| 4 |
Correct |
11 ms |
41816 KB |
Output is correct |
| 5 |
Execution timed out |
5026 ms |
66688 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
41820 KB |
Output is correct |
| 2 |
Correct |
57 ms |
42068 KB |
Output is correct |
| 3 |
Correct |
102 ms |
42252 KB |
Output is correct |
| 4 |
Correct |
165 ms |
42324 KB |
Output is correct |
| 5 |
Correct |
939 ms |
53940 KB |
Output is correct |
| 6 |
Execution timed out |
5016 ms |
65864 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
41836 KB |
Output is correct |
| 2 |
Correct |
11 ms |
41820 KB |
Output is correct |
| 3 |
Correct |
14 ms |
41992 KB |
Output is correct |
| 4 |
Correct |
14 ms |
41820 KB |
Output is correct |
| 5 |
Correct |
17 ms |
41904 KB |
Output is correct |
| 6 |
Correct |
10 ms |
41824 KB |
Output is correct |
| 7 |
Correct |
10 ms |
41976 KB |
Output is correct |
| 8 |
Execution timed out |
5032 ms |
54268 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
