一道线段树好题
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=5e4+5;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct Seg{int l,r,lz,c,ls,ms,rs;}t[N<<2];//lz=1 or -1 标记 c=1为空,-1满,0不知道。
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if(l==r){t[p].lz=0;t[p].c=1;t[p].ls=t[p].ms=t[p].rs=1;return ;}
int mid=l+r>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);
t[p].ls=t[p].ms=t[p].rs=r-l+1;
t[p].c=1;t[p].lz=0;
}
void pushdown(int p)
{
if(t[p].lz)
{
t[p<<1].lz=t[p<<1|1].lz=t[p<<1].c=t[p<<1|1].c=t[p].lz;
if(t[p].lz==-1)t[p<<1].ls=t[p<<1].rs=t[p<<1].ms=t[p<<1|1].ls=t[p<<1|1].rs=t[p<<1|1].ms=0;
else t[p<<1].ls=t[p<<1].rs=t[p<<1].ms=t[p<<1].r-t[p<<1].l+1,t[p<<1|1].ls=t[p<<1|1].rs=t[p<<1|1].ms=t[p<<1|1].r-t[p<<1|1].l+1;
t[p].lz=0;
}
}
void change(int p,int ql,int qr,int k)
{
if(ql<=t[p].l&&qr>=t[p].r)
{
t[p].lz=t[p].c=k;
if(k==-1)t[p].ls=t[p].rs=t[p].ms=0;
else t[p].ls=t[p].rs=t[p].ms=t[p].r-t[p].l+1;
return ;
}
pushdown(p);
int mid=t[p].l+t[p].r>>1;
if(ql<=mid)change(p<<1,ql,qr,k);
if(qr>mid)change(p<<1|1,ql,qr,k);
if(t[p<<1].c==t[p<<1|1].c)t[p].c=t[p<<1].c;//更新操作
else t[p].c=0;
t[p].ls=t[p<<1].ls,t[p].rs=t[p<<1|1].rs;
if(t[p<<1].c==1)t[p].ls+=t[p<<1|1].ls;
if(t[p<<1|1].c==1)t[p].rs+=t[p<<1].rs;
t[p].ms=max(t[p<<1].ms,max(t[p<<1|1].ms,t[p<<1].rs+t[p<<1|1].ls));
}
int query(int p,int d)//优先找左边的
{
int pos=-1;
while(233)
{
if(t[p].c==-1)break;
if(t[p].ms<d)break;
if(t[p].ls>=d){pos=t[p].l;break;}
if(t[p<<1].ms>=d)p<<=1;
else
{
if(t[p<<1].rs+t[p<<1|1].ls>=d){pos=t[p<<1].r-t[p<<1].rs+1;break;}
else (p<<=1)|=1;
}
}
return pos;
}
int main()
{
int n,m;qr(n),qr(m);
build(1,1,n);
for(int i=1,op,d,l;i<=m;i++)
{
qr(op);
if(op==1)
{
qr(d);
int pos=query(1,d);
if(pos!=-1)
{
change(1,pos,pos+d-1,-1);
qw(pos),puts("");
}
else puts("0");
}
else
{
qr(l),qr(d);int r=l+d-1;
change(1,l,r,1);
}
}
return 0;
}
最后一次更新于2019-10-13
0 条评论