前言
启发式合并
几乎可以说是最经典的合并了。
元素总量为 \(n\ 的集合。
集合启发式合并
[NOI2022] 众数
用桶记录每个元素出现次数，查询时从序列中随机抽取 \(\log q\ 个数验证是否是绝对众数。
然后对于在末尾插入删除以及拼接多个序列，我们可以用双端队列维护。
但是这么做的复杂度有保证吗？
而且这个操作使这个元素所在的序列长度至少翻了一倍，又因为总共只有 \(n\ 各元素，所以序列长度至多为 \(n\，所以一个元素最多被插入 \(\log n\ 次。
参考代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
namespace IO{
const int SIZE=1<<21;
static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
int qr;
char qu[55],c;
bool f;
#define getchar( (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf+fread(IO::ibuf,1,IO::SIZE,stdin,(IO::iS==IO::iT?EOF:*IO::iS++:*IO::iS++
#define putchar(x *IO::oS++=x,IO::oS==IO::oT?flush(:0
#define flush( fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout,IO::oS=IO::obuf
#define puts(x IO::Puts(x
template<typename T>
inline void read(T&x{
for(f=1,c=getchar(;c<48||c>57;c=getchar(f^=c=='-';
for(x=0;c<=57&&c>=48;c=getchar( x=(x<<1+(x<<3+(c&15;
x=f?x:-x;
}
template<typename T>
inline void write(T x{
if(!x putchar(48; if(x<0 putchar('-',x=-x;
while(x qu[++qr]=x%10^48,x/=10;
while(qr putchar(qu[qr--];
}
inline void Puts(const char*s{
for(int i=0;s[i];i++
putchar(s[i];
putchar('\n';
}
struct Flusher_{~Flusher_({flush(;}}io_flusher_;
}
using IO::read;
using IO::write;
const int maxn = 5e5+1;
const int zbz = 22;
int tot;
int n,q;
class hhx{
public:
__gnu_pbds::gp_hash_table<int,int> warma;
int L,R;
inline void push_back(int x;
inline void push_front(int x;
inline void pop_back(;
inline void pop_front(;
inline int back(;
inline int front(;
inline int rd(;
inline int size(;
};
inline void hhx::push_back(int x{
warma[++R]=x;
}
inline void hhx::push_front(int x{
warma[--L]=x;
}
inline void hhx::pop_back({
--R;
}
inline void hhx::pop_front({
++L;
}
inline int hhx::back({
return warma[R];
}
inline int hhx::front({
return warma[L];
}
inline int hhx::rd({
return warma[L+rand(%(R-L+1];
}
inline int hhx::size({
return R-L+1;
}
struct Node{
__gnu_pbds::gp_hash_table<int,int> cnt;//出现次数
hhx lwx;
}chifan[maxn];
__gnu_pbds::gp_hash_table<int,int> xzy;
inline void insert(int pos,int x,bool type{
++chifan[pos].cnt[x];
if(type==0
chifan[pos].lwx.push_back(x;
else
chifan[pos].lwx.push_front(x;
}
inline void del(int pos{
int d=chifan[pos].lwx.back(;
chifan[pos].lwx.pop_back(;
--chifan[pos].cnt[d];
}
inline void merge(int x1,int x2,int x3{
int f=0;
if(chifan[x1].lwx.size(<chifan[x2].lwx.size({
f=1;
swap(x1,x2;
}
for(int u,i=chifan[x2].lwx.L;i<=chifan[x2].lwx.R;i++{
u=chifan[x2].lwx.warma[i];
insert(x1,u,f;
}
xzy[x3]=x1;
}//这里是启发式合并
vector<int> X;
vector<int> wyb;
inline int query({
int m;
read(m;
X.clear(;
wyb.clear(;
for(int i=1;i<=m;i++{
int x;
read(x;
x=xzy[x];
X.push_back(x;
}
int sum=0;
for(int u:X{
sum+=chifan[u].lwx.size(;
}
for(int i=1;i<=zbz;i++{
int pos=rand(%sum+1;
int v=0,s=0;
for(int v1:X{
s+=chifan[v1].lwx.size(;
if(s>=pos{
v=v1;
break;
}
}
wyb.push_back(chifan[v].lwx.rd(;
}
for(int u:wyb{
int s=0;
for(int v:X{
s+=chifan[v].cnt[u];
}
if((s<<1>sum{
return u;
}
}
return -1;
}
signed main({
ios::sync_with_stdio(0;
cin.tie(0;
cout.tie(0;
srand(time(0;
read(n;
read(q;
for(int i=0;i<=n;i++ chifan[i].lwx.L=1,chifan[i].lwx.R=0;
for(int i=1;i<=n;++i{
xzy[i]=i;
int m;
read(m;
for(int j=1;j<=m;++j{
int x;
read(x;
insert(i,x,0;
}
}
for(int i=1;i<=q;++i{
int opt;
read(opt;
if(opt==1{
int x,y;
read(x;
read(y;
x=xzy[x];
insert(x,y,0;
}
else if(opt==2{
int x;
read(x;
x=xzy[x];
del(x;
}
else if(opt==3{
write(query(;
putchar('\n';
}
else{
int x1,x2,x3;
read(x1;
read(x2;
read(x3;
x1=xzy[x1];
x2=xzy[x2];
merge(x1,x2,x3;
}
}
}
树上启发式合并
树上启发式合并多用于解决对子树的询问。
具体的思路是让父节点继承节点最多的儿子（重儿子）的信息，在把其他的儿子（轻儿子）的信息暴力插入。
空间复杂度是 \(O(n \log n\ 怎么办？
-
保留它们的信息。
先递归求解这个点的所有轻儿子并求解对于它们的询问。不保留它们的信息。
这么做时间复杂度还是 \(O(n \log n\ 但是空间复杂度却变成了 \(O(n\。
树形结构合并
线段树合并
[Vani有约会]雨天的尾巴 /【模板】线段树合并
当然，你可以直接树上启发式合并，这么做是 \(O(n \log^2 n\ 的，有没有更好的解法？
动态开点权值线段树（不同的同学请先学习动态开点）。这样就保证一个大小为 \(u\ 的集合线段树上至多有 \(u \log n\ 个节点。
我们可以递归进行，假设我们要合并两个节点，先分别合并这两个节点的左右儿子，再更新这个节点的信息。
写出代码就是这样：
int merge(int a,int b,int l,int r{
if(a==0||b==0 return a+b;
if(l==r{
tree[a].cnt+=tree[b].cnt;
tree[a].val=l;
return a;
}
int mid=(l+r/2;
tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid;
tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r;
pushup(a;
return a;
}
这个复杂度看上去很鬼畜，但是对的，为啥？
不同的节点，也就是说节点总数就会减一。
至多被调用 \(n \log n\ 次。
参考代码
#include<bits/stdc++.h>
using namespace std;
const int inf = 2e5;
int n,q;
const int maxn = 2e5+114;
vector<int> Add[maxn*2],Del[maxn*2];
int ans[maxn];
int tot;
int root[maxn];
int fa[maxn][18];
int depth[maxn];
int lg[maxn];
vector<int> edge[maxn];
struct Node{
int ls,rs,val,cnt;
}tree[maxn * 20];
void pushup(int &cur{
if(tree[tree[cur].ls].cnt<tree[tree[cur].rs].cnt{
tree[cur].cnt=tree[tree[cur].rs].cnt;
tree[cur].val=tree[tree[cur].rs].val;
}
else if(tree[tree[cur].rs].cnt<tree[tree[cur].ls].cnt{
tree[cur].cnt=tree[tree[cur].ls].cnt;
tree[cur].val=tree[tree[cur].ls].val;
}
else{
tree[cur].cnt=tree[tree[cur].ls].cnt;
tree[cur].val=min(tree[tree[cur].ls].val,tree[tree[cur].rs].val;
}
}
void addtag(int &cur,int lt,int rt,int l,int r,int v{
if(lt>r||rt<l return ;
if(cur==0{
cur=++tot;
}
if(lt==rt{
tree[cur].cnt+=v;
tree[cur].val=lt;
return ;
}
int mid = (lt+rt/2;
addtag(tree[cur].ls,lt,mid,l,r,v;
addtag(tree[cur].rs,mid+1,rt,l,r,v;
pushup(cur;
}
int merge(int a,int b,int l,int r{
if(a==0||b==0 return a+b;
if(l==r{
tree[a].cnt+=tree[b].cnt;
tree[a].val=l;
return a;
}
int mid=(l+r/2;
tree[a].ls=merge(tree[a].ls,tree[b].ls,l,mid;
tree[a].rs=merge(tree[a].rs,tree[b].rs,mid+1,r;
pushup(a;
return a;
}
inline void add(int u,int v{
edge[u].push_back(v;
edge[v].push_back(u;
}
inline void dfs1(int now,int fath{
fa[now][0]=fath;
depth[now]=depth[fath] + 1;
for(int i=1;i<=lg[depth[now]];++i
fa[now][i] = fa[fa[now][i-1]][i-1];
for(int nxt:edge[now]{
if(nxt==fath continue;
dfs1(nxt,now;
}
}
int LCA(int x,int y{
if(depth[x] < depth[y]
swap(x, y;
while(depth[x] > depth[y]
x=fa[x][lg[depth[x]-depth[y]]- 1];
if(x==y
return x;
for(int k=lg[depth[x]]-1; k>=0; --k
if(fa[x][k] != fa[y][k]
x=fa[x][k],y=fa[y][k];
return fa[x][0];
}
void change(int u,int v,int z{
Add[u].push_back(z;
Add[v].push_back(z;
int w=LCA(u,v;
Del[w].push_back(z;
Del[fa[w][0]].push_back(z;
}
void dfs2(int now,int fa{
for(int nxt:edge[now]{
if(nxt==fa continue;
dfs2(nxt,now;
root[now]=merge(root[now],root[nxt],1,inf;
}
pushup(root[now];
for(int c:Add[now]{
addtag(root[now],1,inf,c,c,1;
}
for(int c:Del[now]{
addtag(root[now],1,inf,c,c,-1;
}
ans[now]=tree[root[now]].val;
}
signed main({
ios::sync_with_stdio(0;
cin.tie(0;
cout.tie(0;
cin>>n>>q;
for(int i = 1; i <= n; ++i
lg[i]=lg[i-1]+(1<<lg[i-1]==i;
for(int i=1;i<n;i++{
int u,v;
cin>>u>>v;
add(u,v;
}
dfs1(1,0;
for(int i=1;i<=q;i++{
int u,v,z;
cin>>u>>v>>z;
change(u,v,z;
}
dfs2(1,0;
for(int i=1;i<=n;i++ cout<<ans[i]<<'\n';
}
Trie 合并
[省选联考 2020 A 卷] 树
转化题意便知道我们需要在每个点上用一种数据结构维护全局加一和异或和，很自然地想到用 01trie 维护，具体怎么维护限于篇幅就不赘述了，现在我们只考虑怎么把子树内 01trie 合并到父节点的问题。
复杂度分析和线段树合并类似，都是 \(O(n \log n\ 的。
关于压位 trie 推荐一篇好博客
参考代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6+114;
int anser,tot;
int col[maxn];
int n;
vector<int> edge[maxn];
struct Node{
int ls,rs,v,val;
int cnt;
}trie[maxn*40];
queue<int> is;
int root[maxn];
void pushup(int &cur,int pos{
if(cur!=pos
trie[cur].val=((trie[cur].cnt&1?trie[cur].v:0+((trie[trie[cur].ls].val^trie[trie[cur].rs].val<<1;
else
trie[cur].val=(trie[trie[cur].ls].val^trie[trie[cur].rs].val;
}
void insert(int &cur,int pos{
if(is.size(==0 return;
if(cur==0{
cur=++tot;
}
if(cur!=pos{
trie[cur].v=(is.front(&1,trie[cur].cnt++;
is.pop(;
}
if(!(is.front(&1 insert(trie[cur].ls,pos;
else insert(trie[cur].rs,pos;
pushup(cur,pos;
}
int merge(int &a,int &b,int pos{
if(a==0||b==0 return a+b;
trie[a].cnt+=trie[b].cnt;
trie[a].ls=merge(trie[a].ls,trie[b].ls,pos;
trie[a].rs=merge(trie[a].rs,trie[b].rs,pos;
pushup(a,pos;
return a;
}
void add(int &cur,int pos{
if(cur==0{
return ;
}
swap(trie[cur].ls,trie[cur].rs;
if(trie[cur].ls!=0
trie[trie[cur].ls].v=0;
if(trie[cur].rs!=0
trie[trie[cur].rs].v=1;
add(trie[cur].ls,pos;
pushup(trie[cur].ls,pos;
pushup(trie[cur].rs,pos;
pushup(cur,pos;
return ;
}
void chifan(int x{
while(is.size(>0 is.pop(;
while(x!=0{
is.push(x&1;
x>>=1;
}
while(is.size(<22 is.push(0;
return ;
}
void dfs(int u,int fa{
for(int v:edge[u]{
if(v==fa continue;
dfs(v,u;
merge(root[u],root[v],u;
}
chifan(col[u];
insert(root[u],u;
anser+=trie[root[u]].val;
add(root[u],u;
}
signed main({
ios::sync_with_stdio(0;
cin.tie(0;
cout.tie(0;
cin>>n;
for(int i=1;i<=n;i=-~i{
cin>>col[i];
root[i]=++tot;
}
for(int i=2;i<=n;i=-~i{
int v;
cin>>v;
edge[i].push_back(v;
edge[v].push_back(i;
}
dfs(1,0;
cout<<anser;
}