段错误求助
查看原帖
段错误求助
315205
Kniqht楼主2023/1/4 08:47

可能是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;
}
2023/1/4 08:47
加载中...