题意：
操作1：找长为$len$的空区间并填满，没有输出$0$
操作2：将$[l,r]$之间的区间置空
我真是太弱了这种线段树还写了一个半小时，中间为了查错手动模拟了$30min$线段树操作，然后发现$zz$的寻找时没有单独判断跨过中间的情况，自以为看一下$t[x].pos$就可以了...
然后交到洛谷$T$了一个点，交到$BZOJ$跑了$7s$度人家都是不到半秒，突然发现自己的寻找是$nlogn$的......然后改成$logn$又出了点小问题无奈加上了判断$l==r$.....我太弱了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; #define lc x<<1 #define rc x<<1|1 #define mid ((l+r)>>1) #define lson lc,l,mid #define rson rc,mid+1,r const int N=1e5+5,INF=1e9; typedef long long ll; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();} return x*f; } int n,Q,op,p,len; struct Node{ int mx,lm,rm,pos,rpos; int tag; Node():mx(0),lm(0),rm(0){} void debug(){printf("%d %d %d %d %d %d ",mx,lm,rm,pos,rpos,tag);} }t[N<<2]; inline void merge(int x,int l,int r){ if(t[lc].mx>t[rc].mx) t[x].mx=t[lc].mx,t[x].pos=t[lc].pos; else t[x].mx=t[rc].mx,t[x].pos=t[rc].pos; if(t[lc].rm+t[rc].lm>t[x].mx) t[x].mx=t[lc].rm+t[rc].lm,t[x].pos=t[lc].rpos; if(t[lc].lm==mid-l+1) t[x].lm=t[lc].lm+t[rc].lm; else t[x].lm=t[lc].lm; if(t[rc].rm==r-mid&&t[lc].rm) t[x].rm=t[rc].rm+t[lc].rm,t[x].rpos=t[lc].rpos; else t[x].rm=t[rc].rm, t[x].rpos=t[rc].rpos; } inline void paint(int x,int l,int r,int v){ t[x].tag=v; if(v==1) t[x].mx=t[x].lm=t[x].rm=0,t[x].pos=t[x].rpos=INF; else t[x].mx=t[x].lm=t[x].rm=r-l+1,t[x].pos=t[x].rpos=l; } inline void pushDown(int x,int l,int r){ if(t[x].tag){ paint(lson,t[x].tag); paint(rson,t[x].tag); t[x].tag=0; } } void build(int x,int l,int r){ if(l==r) t[x].mx=t[x].lm=t[x].rm=1,t[x].pos=t[x].rpos=l; else{ build(lson); build(rson); merge(x,l,r); } //printf("build %d %d %d ",x,l,r); //t[x].debug(); } void segAdd(int x,int l,int r,int ql,int qr,int v){//printf("segAdd %d %d %d ",x,l,r); if(ql<=l&&r<=qr) paint(x,l,r,v); else{ pushDown(x,l,r); if(ql<=mid) segAdd(lson,ql,qr,v); if(mid<qr) segAdd(rson,ql,qr,v); merge(x,l,r); } //printf("segAdd %d %d %d ",x,l,r); //t[x].debug(); } int segFin(int x,int l,int r,int len){//printf("segFin %d %d %d %d %d ",x,l,r,len,t[x].mx); if(l==r) return l; if(t[x].mx<len) return INF; else{ pushDown(x,l,r); if(t[lc].mx>=len) return segFin(lson,len); else if(t[lc].rm+t[rc].lm>=len&&t[lc].rm) return t[lc].rpos; else return segFin(rson,len); } } inline void Query1(int len){ if(t[1].mx<len) puts("0"); else{ int ans=segFin(1,1,n,len); printf("%d ",ans); segAdd(1,1,n,ans,ans+len-1,1);//printf("ql qr %d %d ",ans,ans+len-1); } } inline void Query2(int ql,int qr){ segAdd(1,1,n,ql,qr,-1); } int main(){ freopen("in","r",stdin); //freopen("out","w",stdout); n=read();Q=read(); build(1,1,n); for(int id=1;id<=Q;id++){//printf("Q %d %d ",id,t[1<<1].mx); op=read(); if(op==1) len=read(),Query1(len); else p=read(),len=read(),Query2(p,p+len-1); } }