#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
const int N = 3e5 + 7;
const int inf = 1e9 + 7;
struct PersistentLazySegt{
struct Node{
int left , right , mn , mncnt , lzt;
Node(int x):left(-1) , right(-1) , mn(x) , mncnt(1) , lzt(0){}
};
vector < Node > tree;
vector < int > roots;
Node merge(int a , int b){
// cout << "MERGE ----" << endl;
// cout << "a : " << tree[a].mn << " " << tree[a].mncnt << endl;
// cout << "b : " << tree[b].mn << " " << tree[b].mncnt << endl;
Node c(inf);
c.left = a;
c.right = b;
c.mn = min(tree[a].mn , tree[b].mn);
c.mncnt = 0;
// cout << "c : " << c.mn << " " << c.mncnt << endl;
if(tree[a].mn == c.mn)c.mncnt += tree[a].mncnt;
// cout << "c : " << c.mn << " " << c.mncnt << endl;
if(tree[b].mn == c.mn)c.mncnt += tree[b].mncnt;
// cout << "c : " << c.mn << " " << c.mncnt << endl;
// cout << "WTF : " << tree[a].mn << " == " << c.mn << endl;
// cout << "WTF : " << tree[b].mn << " == " << c.mn << endl;
// cout << "----" << endl;
return c;
}
pair < int , int > merge(pair < int , int > a , pair < int , int > b){
if(a.first == b.first){
a.second += b.second;
return a;
}
else{
if(a.first < b.first)return a;
else return b;
}
}
int build(int l , int r){
if(l == r){
tree.push_back(Node(0));
// cout << l << " " << r << " : " << tree[sz(tree) - 1].mn << " " << tree[sz(tree) - 1].mncnt << " " << tree[sz(tree) - 1].lzt << endl;
return sz(tree) - 1;
}
tree.push_back(Node(0));
int mid = (l + r) >> 1 , myind = sz(tree) - 1;
tree[myind] = merge(build(l , mid) , build(mid+1 , r));
// cout << l << " " << r << " : " << tree[myind].mn << " " << tree[myind].mncnt << " " << tree[myind].lzt << endl;
return myind;
}
void init(){
roots.push_back(build(1 , N));
}
void push(int ind , int l , int r){
if(tree[ind].lzt){
tree[ind].mn += tree[ind].lzt;
int mid = (l + r) / 2;
// cout << "push : " << ind << " " << l << " " << r << " : " << tree[ind].mn << " , " << tree[ind].lzt << endl;
// cout << "pushkids : " << tree[ind].left << " , " << tree[ind].right << endl;
if(l != r){
// cout << "nice" << endl;
// left kid
// cout << "left : " << tree[tree[ind].left].mn << " " << tree[ind].left << endl;
tree.push_back(tree[tree[ind].left]);
tree[sz(tree) - 1].lzt += 1;
tree[ind].left = sz(tree) - 1;
// cout << "left : " << tree[tree[ind].left].mn << " " << tree[tree[ind].left].mncnt << endl;
// right kid
tree.push_back(tree[tree[ind].right]);
tree[sz(tree) - 1].lzt += 1;
tree[ind].right = sz(tree) - 1;
// cout << "right : " << tree[tree[ind].right].mn << " " << tree[tree[ind].right].mncnt << endl;
}
// cout << "pushkids1 : " << tree[ind].left << " , " << tree[ind].right << endl;
tree[ind].lzt = 0;
}
}
pair < int , int > query(int ql , int qr , int ind = 0 , int l = 1 , int r = N){
push(ind,l,r);
// cout << "\nQUERY : " << ind << " " << l << " " << r << " : " << tree[ind].mn << " " << tree[ind].mncnt << endl;
if(l >= ql and r <= qr){
return {tree[ind].mn , tree[ind].mncnt};
}
else if(l > qr or r < ql){
return {inf , 0};
}
else{
int mid = (l + r) >> 1;
return merge(query(ql , qr , tree[ind].left , l , mid) , query(ql , qr , tree[ind].right , mid+1 , r));
}
}
int update(int ql , int qr , int ind = 0 , int l = 1 , int r = N){
push(ind,l,r);
if(l >= ql and r <= qr){
tree.push_back(tree[ind]);
int myind = sz(tree) - 1;
tree[myind].lzt += 1;
push(myind,l,r);
// cout << myind << " update1 : " << l << " " << r << " = " << tree[myind].mn << " , " << tree[myind].mncnt << endl;
return myind;
}
else{
int mid = (l + r) >> 1;
Node thisnode = tree[ind];
if((l > qr or mid < ql) == 0){
thisnode.left = update(ql , qr , tree[ind].left , l , mid);
}
if((mid+1 > qr or r < ql) == 0){
thisnode.right = update(ql , qr , tree[ind].right , mid+1 , r);
}
thisnode = merge(thisnode.left , thisnode.right);
tree.push_back(thisnode);
// cout << sz(tree)-1 << " update2 : " << l << " " << r << " = " << thisnode.mn << " , " << thisnode.mncnt << endl;
// cout << "kids : " << thisnode.left << " " << thisnode.right << endl;
// cout << "left : " << tree[thisnode.left].mn << " " << tree[thisnode.left].mncnt << endl;
// cout << "right : " << tree[thisnode.right].mn << " " << tree[thisnode.right].mncnt << endl;
return sz(tree) - 1;
}
}
void new_update(int l , int r){
roots.push_back(update(l , r , roots.back()));
}
} pst;
void solve(){
// const int n = 20;
// pst.init();
// while(true){
// int typ;
// cin >> typ;
// if(typ == 1){
// int l,r;
// cin >> l >> r;
// pst.new_update(l ,r);
// }
// else if(typ == 2){
// int k;
// cin >> k;
// for(int i = 1;i<=n;i++)cout << pst.query(i,i,pst.roots[k]).first << " ";cout << endl;
// }
// else{
// int k,l,r;
// cin >> k >> l >> r;
// cout << "res : " << pst.query(l,r,pst.roots[k]).first << " , " << pst.query(l,r,pst.roots[k]).second << endl;
// }
// for(int i = 1;i<=n;i++)cout << pst.query(i,i,pst.roots[sz(pst.roots) - 1]).first << " ";cout << endl;
// }
// N = 100
pst.init();
int n,q;
cin >> n >> q;
string str;
cin >> str;
for(int i = 0;i<sz(str);i++){
if(str[i] == '0')str[i] = '1';
else str[i] = '0';
}
vector < pair < int , int > > ranges[n+1];
int version_map[n+2] , last[n+1];
memset(version_map , -1 , sizeof(version_map));
version_map[0] = 0;
memset(last , -1 , sizeof(last));
for(int i = 0;i<n;i++){
if(str[i] == '1')last[i+1] = 1;
}
// cout << "flag0" << endl;
vector < array < int , 3 > > queries;
for(int t = 2;t<=q+1;t++){
string typ;
cin >> typ;
if(typ == "toggle"){
int x;
cin >> x;
if(last[x] == -1)last[x] = t;
else {
ranges[x].push_back({last[x] , t-1});
last[x] = -1;
}
}
else{
int l,r;
cin >> l >> r;
queries.push_back({l , r , t-1});
}
}
// cout << "flag1" << endl;
for(int i = 1;i<=n;i++){
if(last[i] != -1){
ranges[i].push_back({last[i] , q+1});
}
}
// cout << "flag2" << endl;
for(int i = 1;i<=n;i++){
for(auto itr : ranges[i]){
// cout << "flag2.5" << endl;
pst.new_update(itr.first , itr.second);
// cout << i << " new update : " << itr.first << " , " << itr.second << endl;
}
// cout << "last : ";for(int j = 1;j<=q+1;j++)cout << pst.query(j , j , pst.roots.back()).first << " ";cout << endl;
version_map[i] = pst.roots.back();
}
version_map[n+1] = pst.roots.back();
// cout << "###########" << endl;
// for(int i = 1;i<=n;i++){
// cout << i << " : ";for(int j = 1;j<=q+1;j++)cout << pst.query(j , j , version_map[i]).first << " ";cout << endl;
// }
// cout << "flag3" << endl;
for(auto itr : queries){
// cout << "query : " << itr[0] << " " << itr[1] << " " << itr[2] << endl;
pair < int , int > r_val = pst.query(1 , itr[2] , version_map[itr[1]]);
pair < int , int > l_val = pst.query(1 , itr[2] , version_map[itr[0]-1]);
// cout << "lval : " << l_val.first << " " << l_val.second << endl;
// cout << "rval : " << r_val.first << " " << r_val.second << endl;
if(l_val.first == r_val.first){
cout << r_val.second << '\n';
}
else {
cout << 0 << '\n';
}
}
// cout << "flag4" << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase=1;//cin >> testcase;
while(testcase--)solve();
cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}
Compilation message
street_lamps.cpp: In member function 'void PersistentLazySegt::push(int, int, int)':
street_lamps.cpp:61:8: warning: unused variable 'mid' [-Wunused-variable]
61 | int mid = (l + r) / 2;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
20932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
288 ms |
334340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
21312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
22212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
20932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
