目录
- $code$
题目
戳
思路
$bss$
$code$
#include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cstdio> #define maxn 500001 using namespace std; int n,m; struct node{ int l,r,lmax,maxx,rmax,len,lazy; }tree[maxn<<2]; inline int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f?-x:x; } void pushdown(int now){ if(tree[now].lazy==1){ tree[now<<1].lazy=tree[now<<1|1].lazy=1; tree[now<<1].maxx=tree[now<<1].lmax=tree[now<<1].rmax=0; tree[now<<1|1].maxx=tree[now<<1|1].lmax=tree[now<<1|1].rmax=0; } if(tree[now].lazy==2){ tree[now<<1].lazy=tree[now<<1|1].lazy=2; tree[now<<1].maxx=tree[now<<1].lmax=tree[now<<1].rmax=tree[now<<1].len; tree[now<<1|1].maxx=tree[now<<1|1].lmax=tree[now<<1|1].rmax=tree[now<<1|1].len; } tree[now].lazy=0; } void up(int now){ if(tree[now<<1].maxx==tree[now<<1].len) tree[now].lmax=tree[now<<1].lmax+tree[now<<1|1].lmax; else tree[now].lmax=tree[now<<1].lmax; if(tree[now<<1|1].rmax==tree[now<<1|1].len) tree[now].rmax=tree[now<<1|1].rmax+tree[now<<1].rmax; else tree[now].rmax=tree[now<<1|1].rmax; tree[now].maxx=max(tree[now<<1].maxx,tree[now<<1|1].maxx); tree[now].maxx=max(tree[now].maxx,tree[now<<1].rmax+tree[now<<1|1].lmax); } void build(int l,int r,int now){ tree[now].l=l,tree[now].r=r; tree[now].lmax=tree[now].rmax=tree[now].maxx=tree[now].len=r-l+1; if(tree[now].l==tree[now].r) return; int mid=(tree[now].l+tree[now].r)>>1; build(l,mid,now<<1);build(mid+1,r,now<<1|1); } void update_range(int x,int y,int k,int now){ pushdown(now); if(tree[now].l>=x&&tree[now].r<=y){ if(k==1) tree[now].maxx=tree[now].lmax=tree[now].rmax=0; else tree[now].maxx=tree[now].lmax=tree[now].rmax=tree[now].len; tree[now].lazy=k; return; } int mid=(tree[now].l+tree[now].r)>>1; if(x<=mid) update_range(x,y,k,now<<1); if(y>mid) update_range(x,y,k,now<<1|1); up(now); } int ask_range(int x,int now){ pushdown(now); if(tree[now].l==tree[now].r) return tree[now].l; int mid=(tree[now].l+tree[now].r)>>1; if(tree[now<<1].maxx>=x) return ask_range(x,now<<1); else if(tree[now<<1].rmax+tree[now<<1|1].lmax>=x) return mid-tree[now<<1].rmax+1; else return ask_range(x,now<<1|1); } int main(){ n=read(),m=read(); build(1,n,1); int bz,x,y; while(m--){ bz=read(),x=read(); if(bz==1){ if(tree[1].maxx>=x){ int left=ask_range(x,1); int right=left+x-1; printf("%dn",left); update_range(left,right,1,1); }else printf("0n"); }else{ y=read(); update_range(x,x+y-1,2,1); } } return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602721.html