题解：CF292E Copying Data

· · 题解

怎么没人写可持久化的。

题意：

在 a 数组中把一段区间中的值复制到 b 里面去。

单点查询 b 数组。

思路：

看到题解区各位大佬的线段树维护方式，鄙人十分膜拜。

如果考试的时候想不到差分维护下标怎么办（比如我）？

那就使用高级数据结构。根本不用思考，只需要无脑打代码。

题目中出现了关键句：把一个数组里的值区间覆盖到另一个数组里。

所以考虑可持久化平衡树。

具体怎么做呢？

对 a 数组维护一棵平衡树，在每次要给 b 数组区间赋值时，把 a 数组需复制的区间分裂出来。再把 b 数组分裂好，将 a 数组分裂出来的接到 b 数组里即可。

这个过程可以使用可持久化平衡树完成。

但是过不了，空间炸了。

定期重构即可。

#include<bits/stdc++.h>
#define maxm 10000005
#define maxn 200005
using namespace std;
int n,m,sum,fl,qwq=0,tott,tot,p=1,ans;
int rt1,rt2;
int a[maxn],b[maxn];
struct Fhq{
    int l,r;
    int key,rk,sz;
}t[maxm];
void Pushup(int k){
    t[k].sz=t[t[k].l].sz+t[t[k].r].sz+1;
} 
void Split(int k,int x,int &L,int &R){
    if(!k)L=R=0;
    else{
        int rt=++tot;
        t[rt]=t[k];
        if(t[t[rt].l].sz+1<=x){
            L=rt;
            Split(t[rt].r,x-t[t[rt].l].sz-1,t[rt].r,R);     
        }else{
            R=rt;
            Split(t[rt].l,x,L,t[rt].l);
        }Pushup(rt);
    }
}
int Merge(int x,int y){
    int rt=++tot;
    if(!x||!y){
        t[rt]=t[x+y];
        return rt;
    }
    if(t[x].rk>t[y].rk){
        t[rt]=t[x];
        t[rt].r=Merge(t[rt].r,y);
    }else{
        t[rt]=t[y];
        t[rt].l=Merge(x,t[rt].l);
    }Pushup(rt);
    return rt;
}
int Newnode(int x){
    t[++tot]=(Fhq){0,0,x,rand(),1};
    return tot;
}
void Insert(int x,int op){
    if(!op)rt1=Merge(rt1,Newnode(x));
    else rt2=Merge(rt2,Newnode(x));
}
void Print(int rt){
    if(t[rt].l)Print(t[rt].l);
    cout<<t[rt].key<<" ";
    if(t[rt].r)Print(t[rt].r) ;
} 
void Copy(int x,int y,int z){
    int a1,b1,c1;
    Split(rt1,x-1,a1,c1);
    Split(c1,z,b1,c1);
    int a2,b2,c2;
    Split(rt2,y-1,a2,c2);
    Split(c2,z,b2,c2);  
    rt2=Merge(Merge(a2,b1),c2);
    rt1=Merge(Merge(a1,b1),c1);
}
int Ask(int k,int x){
    while(k){
        int sum=t[t[k].l].sz+1;
        if(sum==x)return t[k].key;
        if(sum<x){
            x-=sum;
            k=t[k].r;
        }else k=t[k].l;
    }
}
void Cha(int rt,int op){
    if(t[rt].l)Cha(t[rt].l,op);
    if(!op)a[++qwq]=t[rt].key;
    else b[++qwq]=t[rt].key;
    if(t[rt].r)Cha(t[rt].r,op) ;
} 
void Rebuild(){
    if(tot<=7000000)return;
    qwq=0;
    Cha(rt1,0);
    rt1=0;

    qwq=0;
    Cha(rt2,1);
    rt2=0;

    tot=0;
    for(int i=1;i<=n;i++)Insert(a[i],0);
    for(int i=1;i<=n;i++)Insert(b[i],1);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    srand(time(0));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        Insert(x,0);
    }tott=tot;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        Insert(x,1);
    }   
    while(m--){
        int op,x,y,z;
        cin>>op>>x;
        if(op==1){
            cin>>y>>z;
            Copy(x,y,z);
            Rebuild();
        }else cout<<Ask(rt2,x)<<"\n";
    }
    return 0;
}

高级数据结构的其中一个意义是让你不用思考过多。