蒟蒻求助QAQ
查看原帖
蒟蒻求助QAQ
100091
GaryH楼主2021/1/29 21:25

样例过了,实测8pts求助

 #include<bits/stdc++.h>
#define ls(p) p<<1
#define rs(p) p<<1|1
using namespace std;
const int maxn=50000+5;
int n,m;
struct Tree{
	int l,r;
	int len;
	int lmx,rmx;
	int val,lzy;
	#define mid(p) ((t[p].l+t[p].r)>>1)
}t[maxn<<3];
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void push_up(int p){
	t[p].val=max(t[ls(p)].rmx+t[rs(p)].lmx,max(t[ls(p)].val,t[rs(p)].val));
	t[p].lmx=(t[ls(p)].len==t[ls(p)].val)?(t[ls(p)].len+t[rs(p)].lmx):t[ls(p)].lmx;
	t[p].rmx=(t[rs(p)].len==t[rs(p)].val)?(t[rs(p)].len+t[ls(p)].rmx):t[rs(p)].rmx;
}
inline void push_down(int p){
	if(!t[p].lzy)return;
	t[ls(p)].lzy=t[rs(p)].lzy=t[p].lzy;
	if(t[p].lzy==1){
		t[ls(p)].lmx=t[ls(p)].rmx=t[ls(p)].val=t[ls(p)].len;
		t[rs(p)].lmx=t[rs(p)].rmx=t[rs(p)].val=t[rs(p)].len;
	}else{
		t[ls(p)].lmx=t[ls(p)].rmx=t[ls(p)].val=0;
		t[rs(p)].lmx=t[rs(p)].rmx=t[rs(p)].val=0;
	}
}
inline void build(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].len=r-l+1;
	if(l==r){t[p].val=t[p].lmx=t[p].rmx=1; return;}
	int mid=(l+r)>>1; build(ls(p),l,mid),build(rs(p),mid+1,r),push_up(p);
}
inline int query(int p,int x){ push_down(p);
	if(t[p].l==t[p].r)return t[p].l;
	if(t[ls(p)].val>=x)return query(ls(p),x);
	if(t[ls(p)].rmx+t[rs(p)].lmx>=x)return mid(p)-t[ls(p)].rmx+1;
	return query(rs(p),x);
}
inline void modify(int op,int p,int l,int r){ push_down(p);
	if(l<=t[p].l&&r>=t[p].r){
		if(op==1)t[p].lmx=t[p].rmx=t[p].val=t[p].len;
		if(op==2)t[p].lmx=t[p].rmx=t[p].val=0;
		t[p].lzy=op; return;
	}
	if(l<=mid(p))modify(op,ls(p),l,r);
	if(r>mid(p))modify(op,rs(p),l,r);
	push_up(p);
}
int main(){
	n=read(),m=read();
	build(1,1,n);int a,b,c;
	for(int i=1;i<=m;i++){
		a=read(),b=read();
		if(a==1){
			if(t[1].val>=b){
				int ll=query(1,b);
				printf("%d\n",ll),modify(2,1,ll,ll+b-1);
			}else{printf("0\n");continue;}
			
		}else{
			c=read(),modify(1,1,b,b+c-1);
		}
	}
	return 0;
}
``
2021/1/29 21:25
加载中...