将所有盒子插入链表，每当一个盒子变空时，从链表里删去它。

查一下它的前驱后继$pre,nxt$，那么$[pre+1,nxt-1]$都是空的。

每次对于$[A,B]$这段都为空，对小朋友按$R$维护线段树，维护区间内$L$的最大值，不断询问$[1,B]$内$L$的最大值，如果$\geq A$则拿出来。

时间复杂度$O(m\log m)$。

 

#include
     
      #include
      
       #define N 100010int n,m,q,i,j,a[N],pre[N],nxt[N],c[N],v[262150],ans;struct P{int l,r;}b[N];inline bool cmp(const P&a,const P&b){return a.r
       
        ='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline int merge(int x,int y){return b[x].l>b[y].l?x:y;}void build(int x,int a,int b){  if(a==b){v[x]=a;return;}  int mid=(a+b)>>1;  build(x<<1,a,mid),build(x<<1|1,mid+1,b);  v[x]=merge(v[x<<1],v[x<<1|1]);}void change(int x,int a,int b,int c){  if(a==b){v[x]=0;return;}  int mid=(a+b)>>1;  if(c<=mid)change(x<<1,a,mid,c);else change(x<<1|1,mid+1,b,c);  v[x]=merge(v[x<<1],v[x<<1|1]);}int ask(int x,int a,int b,int d){  if(b<=d)return v[x];  int mid=(a+b)>>1,t=ask(x<<1,a,mid,d);  if(d>mid)t=merge(t,ask(x<<1|1,mid+1,b,d));  return t;}inline void del(int x){  a[x]--;  if(a[x])return;  int l=pre[x],r=nxt[x];  nxt[l]=r,pre[r]=l;  r=c[r-1];  if(!r)return;  while(1){    int t=ask(1,1,m,r);    if(b[t].l<=l)return;    ans++;    change(1,1,m,t);  }}int main(){  read(n),read(m);  for(i=1;i<=n;i++)read(a[i]),pre[i]=i-1,nxt[i]=i+1;  for(i=1;i<=m;i++)read(b[i].l),read(b[i].r);  std::sort(b+1,b+m+1,cmp);  for(i=1;i<=m;i++)if(b[i].r!=b[i-1].r)for(j=b[i-1].r;j