Pagini recente » Cod sursa (job #2369344) | Cod sursa (job #991500) | Cod sursa (job #921651) | Cod sursa (job #2840834) | Cod sursa (job #568129)
Cod sursa(job #568129)
#include<cstdio>
using namespace std;
const int MaxArb = 1 << 18;
#define max(a, b) ((a)>(b)?(a):(b))
int n,P,st,dr,op;
struct arbore{
int r,l,c; // rezistor bobina condensator :))
};
arbore Arb[MaxArb];
void update_initial(int nod , int left , int right )
{
if( left == right )
{
Arb[nod].r = Arb[nod].l = Arb[nod].c = 1;
return ;
}
int midd = (left + right) >> 1;
update_initial(2*nod, left , midd );
update_initial(2*nod+1 , midd+1 , right );
Arb[nod].r = Arb[2*nod].r + Arb[2*nod+1].r;
Arb[nod].l = Arb[2*nod].l + Arb[2*nod+1].l;
Arb[nod].c = Arb[2*nod].c + Arb[2*nod+1].c;
}
void update(int nod , int left , int right )
{
if( st <= left && right <= dr )
{
if( op == 1 )
Arb[nod].l = Arb[nod].c = Arb[nod].r = 0;
else
Arb[nod].l = Arb[nod].c = Arb[nod].r = right - left + 1;
return;
}
if( left >= right )
return ;
int midd = (left + right) >> 1;
if( Arb[nod].c == 0 )
{
Arb[2*nod].c = Arb[2*nod].l = Arb[2*nod].r = 0;
Arb[2*nod+1].c = Arb[2*nod+1].l = Arb[2*nod+1].r = 0;
}
if( Arb[nod].c == right - left + 1 )
{
Arb[2*nod].c = Arb[2*nod].l = Arb[2*nod].r = midd - left+1;
Arb[2*nod+1].c = Arb[2*nod+1].l = Arb[2*nod+1].r = right - midd;
}
if( st <= midd )
update(2*nod , left , midd );
if( midd < dr )
update(2*nod+1 , midd+1 , right );
Arb[nod].l = Arb[2*nod].l;
if( Arb[nod].l == midd - left + 1 )
Arb[nod].l += Arb[2*nod+1].l;
Arb[nod].r = Arb[2*nod+1].r;
if( Arb[nod].r == right - midd )
Arb[nod].r += Arb[2*nod].r;
Arb[nod].c = max( max(Arb[2*nod].c , Arb[2*nod+1].c) , Arb[2*nod].r + Arb[2*nod+1].l );
}
int main()
{
freopen( "hotel.in" , "r" , stdin );
freopen( "hotel.out" , "w" ,stdout );
scanf("%d%d" , &n , &P);
update_initial(1,1,n);
for( ; P ; P-- )
{
scanf("%d" , &op );
if( op == 1 || op == 2 )
{
scanf("%d%d" , &st , &dr );
dr += (st - 1);
update(1,1,n);
}
else
printf("%d\n" , Arb[1].c);
}
return 0;
}