Pagini recente » Cod sursa (job #3284189) | Cod sursa (job #369188) | Cod sursa (job #143293) | Cod sursa (job #1543011) | Cod sursa (job #3289771)
#include <iostream>
using namespace std;
#define NMAX 100001
#define def int nod=1, int st=1, int dr=n
struct tree{
int lz=0;
int fst, fdr, sz;
friend bool operator<(tree t1, tree t2){
return t1.sz<t2.sz;
}
} aint[NMAX*4];
int n, q, x, y;
void add(def){
if (aint[nod].lz){
if (st!=dr){
aint[2*nod].lz=aint[nod].lz;
aint[2*nod+1].lz=aint[nod].lz;
}
if (aint[nod].lz==1){
aint[nod].sz=0;
} else aint[nod].sz=(dr-st+1);
aint[nod].lz=0;
}
if (y<st || dr<x)return;
if (x<=st && dr<=y){
aint[nod].sz=0;
if (st!=dr){
aint[2*nod].lz=1;
aint[2*nod+1].lz=1;
}
//cout<<st<<" "<<dr<<" -> "<<aint[nod].sz<<" nod: "<<nod<<endl;
return;
}
int mij=(st+dr)/2;
add(2*nod, st, mij);
add(2*nod+1, mij+1, dr);
if (aint[2*nod].sz && aint[2*nod+1].sz){
//cout<<"c1"<<" - "<<nod<<endl;
//cout<<aint[2*nod].sz<<" "<<aint[2*nod+1].sz<<endl;
if (aint[2*nod].fdr==aint[2*nod+1].fst-1){
aint[nod].fst=aint[2*nod].fst;
aint[nod].fdr=aint[2*nod+1].fdr;
aint[nod].sz=(abs(aint[nod].fdr-aint[nod].fst)+1);
return;
}
aint[nod]=max(aint[2*nod], aint[2*nod+1]);
return;
}
if (aint[2*nod].sz){
//cout<<"c2"<<" - "<<nod<<" from: "<<2*nod<<" - "<<aint[2*nod].sz<<endl;
aint[nod]=aint[2*nod];
return;
}
if (aint[2*nod+1].sz){
//cout<<"c3"<<" - "<<nod<<endl;
aint[nod]=aint[2*nod+1];
return;
}
//cout<<"c4"<<" - "<<nod<<endl;
aint[nod]={.lz=0, .fst=st, .fdr=dr, .sz=0};
}
void del(def){
if (aint[nod].lz){
if (st!=dr){
aint[2*nod].lz=aint[nod].lz;
aint[2*nod+1].lz=aint[nod].lz;
}
if (aint[nod].lz==1){
aint[nod].sz=0;
} else aint[nod].sz=(dr-st+1);
aint[nod].lz=0;
}
if (y<st || dr<x)return;
if (x<=st && dr<=y){
aint[nod].sz=dr-st+1;
aint[nod].fst=st;
aint[nod].fdr=dr;
if (st!=dr){
aint[2*nod].lz=-1;
aint[2*nod+1].lz=-1;
}
//cout<<st<<" "<<dr<<" -> "<<aint[nod].sz<<" nod: "<<nod<<endl;
return;
}
int mij=(st+dr)/2;
del(2*nod, st, mij);
del(2*nod+1, mij+1, dr);
if (aint[2*nod].sz && aint[2*nod+1].sz){
//cout<<"c1"<<" - "<<nod<<endl;
//cout<<aint[2*nod].sz<<" "<<aint[2*nod+1].sz<<endl;
if (aint[2*nod].fdr==aint[2*nod+1].fst-1){
aint[nod].fst=aint[2*nod].fst;
aint[nod].fdr=aint[2*nod+1].fdr;
aint[nod].sz=(abs(aint[nod].fdr-aint[nod].fst)+1);
return;
}
//cout<<"out\n";
aint[nod]=max(aint[2*nod], aint[2*nod+1]);
return;
}
if (aint[2*nod].sz){
//cout<<"c2"<<" - "<<nod<<" from: "<<2*nod<<" - "<<aint[2*nod].sz<<endl;
aint[nod]=aint[2*nod];
return;
}
if (aint[2*nod+1].sz){
//cout<<"c3"<<" - "<<nod<<endl;
aint[nod]=aint[2*nod+1];
return;
}
//cout<<"c4"<<" - "<<nod<<endl;
aint[nod]={.lz=0, .fst=st, .fdr=dr, .sz=0};
}
void init(def){
//cout<<nod<<" - "<<st<<" "<<dr<<endl;
/**
1 - 1 12
2 - 1 6
4 - 1 3
8 - 1 2
16 - 1 1
17 - 2 2
9 - 3 3
5 - 4 6
10 - 4 5
20 - 4 4
21 - 5 5
11 - 6 6
3 - 7 12
6 - 7 9
12 - 7 8
24 - 7 7
25 - 8 8
13 - 9 9
7 - 10 12
14 - 10 11
28 - 10 10
29 - 11 11
15 - 12 12
*/
if (st==dr){
aint[nod].sz=1;
aint[nod].fst=st;
aint[nod].fdr=st;
aint[nod].lz=0;
return;
}
int mij=(st+dr)/2;
init(2*nod, st, mij);
init(2*nod+1, mij+1, dr);
aint[nod].fst=st, aint[nod].fdr=dr;
aint[nod].sz=(dr-st+1);
}
void solve(void){
cin>>n>>q;
init();
while (q--){
int op, i, m;
cin>>op;
if (op==1){
cin>>i>>m;
x=i, y=i+m-1;
//cout<<" --- "<<x<<" -- "<<y<<endl;
//cout<<"\n\nSTART UPDATE\n\n\n";
add();
} else if (op==2){
cin>>i>>m;
x=i, y=i+m-1;
//cout<<"\n\nSTART UPDATE\n\n\n";
del();
} else {
cout<<aint[1].sz<<"\n";
//cout<<"*** "<<aint[1].fst<<" - "<<aint[1].fdr<<"\n";
}
}
}
int main(void){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifdef LOCAL
freopen("date.in", "r", stdin);
freopen("log.txt", "w", stdout);
#else
freopen("hotel.in", "r", stdin);
freopen("hotel.out", "w", stdout);
#endif
solve();
return 0;
}