线段树分裂(指针版)
cpp
struct Node{
Node *ls,*rs;
int cnt;
Node(int x=0,Node *ls=nullptr,Node *rs=nullptr):ls(ls),rs(rs){
cnt=0;
}
};
// 哨兵节点
Node *nullNode=new Node();
Node* newNode(int x=0){
return new Node(x,nullNode,nullNode);
}
#define ls(x) (x->ls)
#define rs(x) (x->rs)
#define cnt(x) (x->cnt)
void pushup(Node* p){
cnt(p)=cnt(ls(p))+cnt(rs(p));
}
Node* merge(Node *&p,Node *&q,int l,int r){
if(p==nullNode)return q;
if(q==nullNode)return p;
if(l==r){
cnt(p)+=cnt(q);
delete q;
return p;
}
int mid=l+r>>1;
ls(p)=merge(ls(p),ls(q),l,mid);
rs(p)=merge(rs(p),rs(q),mid+1,r);
pushup(p);
delete q;
return p;
}
void insert(Node *&p,int l,int r,int x,int y){
if(p==nullNode)p=newNode();
if(l==r){
cnt(p)+=y;
return;
}
int mid=l+r>>1;
if(x<=mid)insert(ls(p),l,mid,x,y);
else insert(rs(p),mid+1,r,x,y);
pushup(p);
}
void split(Node *&p,Node *&q,int l,int r,int ql,int qr){
if(l>qr||r<ql||p==nullNode)return;
if(ql<=l&&r<=qr){
q=p;
p=nullNode;
return;
}
if(q==nullNode)q=newNode();
int mid=l+r>>1;
if(ql<=mid)split(ls(p),ls(q),l,mid,ql,qr);
if(qr>mid)split(rs(p),rs(q),mid+1,r,ql,qr);
pushup(p);
pushup(q);
}
int query(Node *p,int l,int r,int ql,int qr){
if(p==nullNode)return 0;
if(ql<=l&&r<=qr)return cnt(p);
int mid=l+r>>1,res=0;
if(ql<=mid)res+=query(ls(p),l,mid,ql,qr);
if(qr>mid)res+=query(rs(p),mid+1,r,ql,qr);
return res;
}
int kth(Node *p,int l,int r,int k){
if(l==r)return l;
int mid=l+r>>1;
if(cnt(ls(p))>=k)return kth(ls(p),l,mid,k);
return kth(rs(p),mid+1,r,k-cnt(ls(p)));
}
void solve(){
int n,m;
cin>>n>>m;
vector<Node*> root={newNode(),newNode()};
for(int i=1;i<=n;i++){
int x;
cin>>x;
insert(root[1],1,n,i,x);
}
while(m--){
int op,p,x,y,t;
cin>>op;
if(op==0){//从可重集p分裂出[x,y]
cin>>p>>x>>y;
root.push_back(newNode());
split(root[p],root.back(),1,n,x,y);
}
else if(op==1){// 可重集p+=t,t=0
cin>>p>>t;
root[p]=merge(root[p],root[t],1,n);
root[t]=nullNode;
}
else if(op==2){// 插入x个y到p
cin>>p>>x>>y;
insert(root[p],1,n,y,x);
}
else if(op==3){// 询问p中[x,y]的个数
cin>>p>>x>>y;
cout<<query(root[p],1,n,x,y)<<"\n";
}
else{// 询问p的kth
cin>>p>>x;
if(cnt(root[p])<x){
cout<<"-1\n";
continue;
}
cout<<kth(root[p],1,n,x)<<"\n";
}
}
}