BZOJ 1593
luogu免权限地址
线段树记录4个信息：
lm: 左端点开始最长连续空区间
rm: 右端点开始最长连续空区间
sum:整个区间最长连续空区间
lazy:lazy标记 (-1:没有标记 0:空区间 1:满区间)
具体请看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
#define lc o*2
#define rc o*2+1
#define M (l+r)/2
const int MAXN = 100000 + 5;
int n,m;
struct st//线段树
{
int lm[MAXN*4], rm[MAXN*4], lazy[MAXN*4], sum[MAXN*4];
//lm: 左端点开始最长连续空区间
//rm: 右端点开始最长连续空区间
//sum:整个区间最长连续空区间
//lazy:lazy标记 (-1:没有标记 0:空区间 1:满区间)
void build(int o, int l, int r)
{
lm[o] = rm[o] = sum[o] = r-l+1;
lazy[o] = -1;
if (l==r) return ;
build(lc, l, M);
build(rc, M+1, r);
} //建树
void pushup(int o, int len)
{
lm[o] = lm[lc];
if (lm[lc]==len-len/2) lm[o] += lm[rc];
//如果左孩子全部为可用区间，那么加上右孩子的左端
rm[o] = rm[rc];
if (lm[rc]==len/2) rm[o] += rm[lc];
//如果右孩子全部为可用区间，那么加上左孩子的右端
sum[o] = max(max(sum[lc], sum[rc]), rm[lc]+lm[rc]);
//左孩子最大的空区间、有孩子最大的空区间，和跨越左右孩子加在一起的空区间
}
void pushdown(int o, int len)
{
if(lazy[o]!=-1)
{
if (lazy[o]==1)
{
sum[lc]=sum[rc]=lm[lc]=rm[lc]=lm[rc]=rm[rc]=0;//全部空
} else
{
sum[lc]=lm[lc]=rm[lc]=len - len/2;
sum[rc]=lm[rc]=rm[rc]=len/2;//全部满
}
lazy[lc]=lazy[rc]=lazy[o];
lazy[o] = -1;//传lazy
}
}
void update(int o, int l, int r, int x, int y, int ty)
{
if(x<=l&&r<=y)
{
lazy[o] = ty;
if (ty==1) sum[o]=lm[o]=rm[o]=0;
else sum[o]=lm[o]=rm[o]=r-l+1;
return ;
}
pushdown(o, r-l+1);
if (x<=M) update(lc,l,M,x,y,ty);
if (M<y) update(rc,M+1,r,x,y,ty);
pushup(o,r-l+1);
}
int query(int o, int l, int r, int w)
{
if (l==r) return l;
pushdown(o,r-l+1);
if (sum[lc]>=w) return query(lc,l,M,w);
if (rm[lc]+lm[rc]>=w) return M-rm[lc]+1;
if (sum[rc]>=w) return query(rc,M+1,r,w);
}
}tree;
int main()
{
scanf("%d%d", &n, &m);
tree.build(1,1,n);
for (int i=1;i<=m;i++)
{
int type;
scanf("%d", &type);
if (type==1)
{
int x;
scanf("%d", &x);
if (tree.sum[1]<x) printf("0\n");
else
{
int ans = tree.query(1,1,n,x);
printf("%d\n", ans);
tree.update(1,1,n,ans,ans+x-1,1);
}
} else
{
int x,y;
scanf("%d%d", &x, &y);
tree.update(1,1,n,x,x+y-1,0);
}
}
return 0;
}
