社区讨论

写了一中午了,调不出来,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 条回复,欢迎继续交流。

正在加载回复...