可能是modify得问题,因为把modify注释掉就不Re了,但是没看出问题球球大佬帮忙看看
#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int n,m;
struct Node{
int l,r;
int lmax,rmax,tmax;
int tag;
}tr[N*4];
void pushup(int x){
tr[x].tmax=max(tr[x>>1].tmax,max(tr[x>>1|1].tmax,tr[x>>1].rmax+tr[x>>1|1].lmax));
}
void pushdown(int u){
/*
tag=1 入住
tag=2 退房
pushup/down
modify
query
*/
if(!tr[u].tag) return;
else if(tr[u].tag==1){
tr[u>>1].lmax=tr[u>>1].rmax=tr[u>>1].tmax=(tr[u>>1].r-tr[u>>1].l+1);
tr[u>>1|1].lmax=tr[u>>1|1].rmax=tr[u>>1|1].tmax=(tr[u>>1|1].r-tr[u>>1|1].l+1);
}
else{
tr[u>>1].lmax=tr[u>>1].rmax=tr[u>>1].tmax=0;
tr[u>>1|1].lmax=tr[u>>1|1].rmax=tr[u>>1|1].tmax=0;
}
}
void build(int u,int l,int r){
tr[u]={l,r,0,0,0,0};
if(l==r) return;
int mid=l+r>>1;
build(u>>1,l,mid);
build(u>>1|1,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,int k){
pushdown(u);
if(tr[u].l>=l&&tr[u].r<=r){
if(k==1) tr[u].tmax=tr[u].rmax=tr[u].lmax=(tr[u].r-tr[u].l+1);
else tr[u].tmax=tr[u].lmax=tr[u].rmax=0;
tr[u].tag=k;
return;
}
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,k);
if(r>mid) modify(u<<1|1,l,r,k);
pushup(u);
}
int query(int u,int l,int r,int k){
if(l==r) return l;
// pushdown(u);
int mid=l+r>>1;
if(tr[u>>1].tmax>k) return query(u>>1,l,mid,k);
else if(tr[u>>1].rmax+tr[u>>1|1].lmax>=k) return mid-tr[u>>1].rmax+1;
else return query(u>>1|1,mid+1,r,k);
}
int op,x,y;
signed main(){
scanf("%d%d",&n,&m);
build(1,1,n);
while(m--){
scanf("%d%d",&op,&x);
if(op==1){
if(tr[1].tmax<x){
printf("0\n");
continue;
}
int l=query(1,1,n,x);
printf("%d\n",l);
modify(1,l,l+x-1,1);
}
else{
scanf("%d",&y);
modify(1,x,x+y-1,2);
}
}
return 0;
}