社区讨论
写了一中午了,调不出来,WA+RE求调玄关
P2894[USACO08FEB] Hotel G参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mma7sxix
- 此快照首次捕获于
- 2026/03/03 14:16 上周
- 此快照最后确认于
- 2026/03/06 16:40 4 天前
CPP
#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
using namespace std;
struct node{int l,r,sum,len,lmax,rmax,tag;}tr[50001];
int n,m;
void build(int p,int l,int r){
tr[p].l=l;tr[p].r=r;tr[p].tag=0;
tr[p].sum=tr[p].len=tr[p].lmax=tr[p].rmax=r-l+1;
if(l==r) return;
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
void pushdown(int p){
if(tr[p].tag==0) return;
if(tr[p].tag==1){
tr[lc].tag=tr[rc].tag=tr[p].tag;
tr[lc].sum=tr[lc].lmax=tr[lc].rmax=0;
tr[rc].sum=tr[rc].lmax=tr[rc].rmax=0;
}
else if(tr[p].tag==2){
tr[lc].tag=tr[rc].tag=tr[p].tag;
tr[lc].sum=tr[lc].lmax=tr[lc].rmax=tr[lc].len;
tr[rc].sum=tr[rc].lmax=tr[rc].rmax=tr[rc].len;
}
tr[p].tag=0;
}
void update(int p){
if(tr[lc].sum==tr[lc].len) tr[p].lmax=tr[lc].sum+tr[rc].lmax;
else tr[p].lmax=tr[lc].lmax;
if(tr[rc].sum==tr[rc].len) tr[p].rmax=tr[rc].sum+tr[lc].rmax;
else tr[p].rmax=tr[rc].rmax;
}
void change(int p,int l,int r,int tag){
pushdown(p);
if(l<=tr[p].l&&tr[p].r<=r){
if(tag==1) tr[p].sum=tr[p].lmax=tr[p].rmax=0;
else tr[p].sum=tr[p].lmax=tr[p].rmax=tr[p].len;
tr[p].tag=tag;
return;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(l<=mid) change(lc,l,r,tag);
if(r>mid) change(rc,l,r,tag);
update(p);
}
int query(int p,int len){
pushdown(p);
if(tr[p].l==tr[p].r) return 1;
int mid=(tr[p].l+tr[p].r)>>1;
if(tr[lc].sum>=len) return query(lc,len);
else if(tr[lc].rmax+tr[rc].lmax>=len) return mid-tr[lc].rmax+1;
else return query(rc,len);
}
int main(){
cin>>n>>m;
build(1,1,n);
for(int i=1;i<=m;i++){
int opt,x,y;
cin>>opt;
if(opt==1){
cin>>x;
if(tr[1].sum>=x){
int ans=query(1,x);
cout<<ans<<'\n';
change(1,ans,ans+x-1,opt);
}
else cout<<"0\n";
}
else{
cin>>x>>y;
change(1,x,x+y-1,opt);
}
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...