[Solution]CF911G

LJ07 · 2022-08-26 21:47:42 · 题解

题目描述

题目传送门

思路简述

简单题。观察到 a 的值域很小，考虑对每个值维护一个存对应下标的平衡树。

每次操作就相当于将第 x 棵平衡树值在 l 到 r 的节点分裂出来，再合并到第 y 课平衡树中。由于要合并的两棵平衡树值域不存在严格大于等于这种关系，所以使用启发式合并。

这里写的是 FHQ treap（为什么题解区没人写平衡树合并 qwq，感觉平衡树比线段树更简单更好写一点啊）。

启发式合并实现的好好像是跟线段树合并一个复杂度的。

空间复杂度仅是 O(n)。写平衡树的好处就是好写并且空间小，在本题不加任何优化跑得比大多数线段树做法快。~~快来写 FHQ treap 啊。~~

丑陋の代码

#include <bits/stdc++.h>
#define GC c=getchar()
#define IG isdigit(c)
#define rep(i,l,r) for(int i(l),_##i(r);i<=_##i;++i)
#define per(i,r,l) for(int i(r),_##i(l);i>=_##i;--i)
const int SZ(1<<23);
unsigned char buf[SZ],*s,*t;
#define getchar() (s==t&&(t=buf+fread(s=buf,1,SZ,stdin)),s==t?EOF:*s++)
template<class T=int>T frd(T x=0,char GC,bool f=1)
{
    for(;!IG;GC)f=c!='-';for(;IG;GC)x=x*10+(c^48);return f?x:-x;
}
using namespace std;
const int V(100),N(2e5+5);
int n,q,root[V+5],a[N+5];
mt19937 rnd(114514);
struct node {int ls,rs,rk; node() {ls=rs=0,rk=rnd();} }nd[N+5];
void split(int &x,int &y,int rt,int k)
{
    if(!rt) return (void)(x=y=0);
    if(rt<=k) x=rt,split(nd[x].rs,y,nd[x].rs,k);
    else y=rt,split(x,nd[y].ls,nd[y].ls,k);
}
int merge(int x,int y)
{
    if(!x||!y) return x+y; if(nd[x].rk>nd[y].rk) swap(x,y); int t1,t2;
    split(t1,t2,y,x),nd[x].ls=merge(nd[x].ls,t1),nd[x].rs=merge(nd[x].rs,t2);
    return x;
}
void put(int rt,int val)
{
    if(rt) a[rt]=val,put(nd[rt].ls,val),put(nd[rt].rs,val);
}
signed main()
{
    n=frd();
    rep(i,1,n) {int a(frd());root[a]=merge(root[a],i);}
    rep(q,1,frd())
    {
        int l(frd()),r(frd()),x(frd()),y(frd()),t1,t2,t3; 
        split(t1,t2,root[x],l-1),split(t2,t3,t2,r);
        root[x]=merge(t1,t3),root[y]=merge(root[y],t2);
    }
    rep(i,1,100) put(root[i],i);
    rep(i,1,n) printf("%d ",a[i]);
    return 0;
}