社区讨论

求助析构函数, 释放new 申请的空间

P5494【模板】线段树分裂参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lo8qd85j
此快照首次捕获于
2023/10/27 22:50
2 年前
此快照最后确认于
2023/10/27 22:50
2 年前
查看原帖
rt, 最后释放空间的时候RE
CPP
#include<iostream>
#include<iomanip>
#include<cstdio>
using namespace std;
const int MAXN=2e5+10;
struct node
{
    node *ls,*rs;
    int siz;
    node(){
        this->siz=0;
        this->ls=this->rs=0;
    }
};
int n,m;
class Line_Tree
{
    private:
        node *root[MAXN];
        int cnt;
    public:
        Line_Tree(){
            for(int i=1;i<=MAXN;i+=1)
                root[i]=new node();
            cnt=1;
        }
        ~Line_Tree(){
            for(int i=1;i<=MAXN;i+=1)
            if(root[i]) destroy(root[i]);
        }
        void destroy(node *t)
        {
            if(t->ls) destroy(t->ls);
            if(t->rs) destroy(t->rs);
            delete t;
        }
        void pushup(node *t)
        {
            t->siz=0;
            if(t->ls) t->siz+=t->ls->siz;
            if(t->rs) t->siz+=t->rs->siz;
        }
        void add(node *t,int l,int r,int x,int k)
        {
            if(l==x&&r==x)
                return (void)(t->siz+=k);
            int mid=(l+r)>>1;
            if(x<=mid)
            {
                if(t->ls==nullptr) t->ls=new node();
                add(t->ls,l,mid,x,k);
            }
            else
            {
                if(t->rs==nullptr) t->rs=new node();
                add(t->rs,mid+1,r,x,k);
            }
            pushup(t);
        }
        void split(node *x,node *y,int l,int r,int pl,int pr)
        {
            if(pl<=l&&r<=pr) return swap(*x,*y);
            int mid=(l+r)>>1;
            if(mid>=pl&&x->ls)
            {
                y->ls=new node();
                split(x->ls,y->ls,l,mid,pl,pr);
            }
            if(mid <pr&&x->rs)
            {
                y->rs=new node();
                split(x->rs,y->rs,mid+1,r,pl,pr);
            }
            pushup(x); pushup(y);
        }
        void merge(node *x,node *y)
        {
            if(y==nullptr) return ;
            if(x==nullptr) return (void)(x=y);
            merge(x->ls,y->ls);
            merge(x->rs,y->rs);
            x->siz+=y->siz;
        }
        int query_siz(node *t,int l,int r,int pl,int pr)
        {
            if(pl<=l&&r<=pr) return t->siz;
            int mid=(l+r)>>1,siz=0;
            if(mid>=pl&&t->ls) siz+=query_siz(t->ls,l,mid,pl,pr);
            if(mid <pr&&t->rs) siz+=query_siz(t->rs,mid+1,r,pl,pr);
            return siz;
        }
        int query_kth(node *t,int l,int r,int k)
        {
            if(l==r) return l;
            int mid=(l+r)>>1;
            if(k<=t->ls->siz) return query_kth(t->ls,l,mid,k);
            else return query_kth(t->rs,mid+1,r,k-t->ls->siz);
        }
        void opt_init(int tr,int l,int r,int x,int k){add(root[tr],l,r,x,k);}
        void opt_0(int tr,int x,int y){split(root[tr],root[++cnt],1,n,x,y);}
        void opt_1(int p,int t){merge(root[p],root[t]);destroy(root[t]);}
        void opt_2(int tr,int k,int x){add(root[tr],1,n,x,k);}
        int opt_3(int tr,int l,int r){return query_siz(root[tr],1,n,l,r);}
        int opt_4(int tr,int k){return (root[tr]->siz<k)?(-1):(query_kth(root[tr],1,n,k));}
}cyr;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x;i<=n;i+=1)
    {
        scanf("%d",&x);
        cyr.opt_init(1,1,n,i,x);
    }
    int op,x,y,p,q,t,k;
    for(int i=1;i<=m;i+=1)
    {
        scanf("%d",&op);
        if(op==0)
        {
            scanf("%d%d%d",&p,&x,&y);
            cyr.opt_0(p,x,y);
        }
        else if(op==1)
        {
            scanf("%d%d",&p,&t);
            cyr.opt_1(p,t);
        }
        else if(op==2)
        {
            scanf("%d%d%d",&p,&x,&q);
            cyr.opt_2(p,x,q);
        }
        else if(op==3)
        {
            scanf("%d%d%d",&p,&x,&y);
            printf("%d\n",cyr.opt_3(p,x,y));
        }
        else if(op==4)
        {
            scanf("%d%d",&p,&k);
            printf("%d\n",cyr.opt_4(p,k));
        }
    }
    return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...