社区讨论
求助析构函数, 释放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 条回复,欢迎继续交流。
正在加载回复...