首页 > 其他分享 >浅谈 OI 中各种合并操作

浅谈 OI 中各种合并操作

时间：2023-07-18 21:44:57浏览次数：45  
标签：浅谈 OI int void 合并 back maxn inline

前言

合并操作一直是 OI 中一大考点，今天请各位跟着笔者来梳理一下各种合并操作。

启发式合并

几乎可以说是最经典的合并了。

假定我们可以在 \(O(k)\) 的时间内往某个集合中插入一个数，那么我们就可以在 \(O(n \log n k)\) 的时间内合并若干个元素总量为 \(n\) 的集合。

集合启发式合并

[NOI2022] 众数

看到查询绝对众数我们便想到一个方法：

用桶记录每个元素出现次数，查询时从序列中随机抽取 \(\log q\) 个数验证是否是绝对众数。

易证这种做法期望是正确的。这里略去。

然后对于在末尾插入删除以及拼接多个序列，我们可以用双端队列维护。

但是在拼接序列是怎么插入元素，暴力插入元素是 \(O(nq)\) 的。我们可以把较短的序列中的元素暴力插入到较长的序列中。

但是这么做的复杂度有保证吗？

注意到每次把一个元素插入到另一个序列中，花费了 \(O(1)\) 的时间（哈希表和双端队列均可以 \(O(1)\) 插入），而且这个操作使这个元素所在的序列长度至少翻了一倍，又因为总共只有 \(n\) 各元素，所以序列长度至多为 \(n\)，所以一个元素最多被插入 \(\log n\) 次。

那么合并操作的总复杂度就是 \(O(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)\) 怎么办？

答案是让全局节点信息公用一个集合，每次按如下流程操作：

  1. 先递归求解这个点的所有轻儿子并求解对于它们的询问。不保留它们的信息。

  2. 递归求解这个点的重儿子并求解对于它们的询问。保留它们的信息。

  3. 将这个节点的轻儿子子树内的信息插入集合并回答对于当前节点的询问。

这么做时间复杂度还是 \(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;
}

这个复杂度看上去很鬼畜，但是对的，为啥？

我们发现每调用一次 \(merge\) 函数那么就会合并两个不同的节点，也就是说节点总数就会减一。

那么又因为总共只有 \(n \log n\) 个节点，所有这个函数至多被调用 \(n \log n\) 次。

那么我们就 \(O(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 合并到父节点的问题。

类似于线段树合并一样的思想，首先我们要让 01trie 变成动态开点式的，然后在合并时依然是先合并左右儿子的信息，再更新节点本身的信息。

复杂度分析和线段树合并类似，都是 \(O(n \log n)\) 的。

不过这里给读者多留一个问题：压位 trie 合并能否实现？倘若能实现，其复杂度是否是 \(O(n \log_{w} 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;   
}

标签：浅谈,OI,int,void,合并,back,maxn,inline
From： https://www.cnblogs.com/chifan-duck/p/17564209.html

相关文章

  • 浅谈虚树优化线段树
    前言我们都知道动态开点权值线段树的空间复杂度是\(O(n\logV)\)的，但是很多题目中这样的空间是会被卡的，那我们能不能优化呢？实现看看下面这一棵树：在上图中，红色节点使我们平常会开的点。但是我们发现，其实只要维护绿色的点和红色的叶子结点。其实，绿色节点就是所有叶子结点......
  • P6227 [BalticOI 2019 Day1] 山谷
    P6227[BalticOI2019Day1]山谷Description给一棵树，一个根，一些特殊补给点，一些询问。求解如下问题：断掉一条边\(u\tov\)，这样以后你能否从给定的\(R_i\)走到根，若能输出escaped。不能到达根且不能到达任何一个特殊补给点输出oo。若不能到达根但可以到达特殊补给点输出边权和......
  • 「JOISC 2019 Day4」蛋糕拼接 3 题解
    先考虑这个式子：\(\sum_{j=1}^{M}|C_{k_{j}}-C_{k_{j+1}}|\)一定是在\(C\)有序时取到，具体证明很简单各位读者自己证明。那么现在式子变成：\(\sum{V}+2\times({C_{\max}-C_{\min}})\)这个时候一个常见的技巧是将\(C\)排序。这个时候就可以定义状态：\(dp_{i,j}=\s......
  • 洛谷 P8923 -『MdOI R5』Many Minimizations
    怎么ARC还能撞题的？只能说Kubic牛逼。首先显然没法保序回归。考虑用类似于凸壳优化DP的做法解决原问题（也就是P4331）：设\(dp_{i,j}\)表示考虑前\(i\)位，\(x_i=j\)的最小代价，显然有\(dp_{i,j}=\min_{k\lej}\{dp_{i-1,k}+|j-a_i|\}\)\(dp\)值显然是一个折线，用堆维护斜......
  • mysql集合合并逗号隔开
    MySQL集合合并（逗号隔开）在MySQL中，我们经常需要将多个值合并成一个集合，以便在查询中使用。常见的方法是使用逗号将多个值隔开，形成一个字符串。本篇文章将介绍如何在MySQL中使用逗号将多个值合并成一个集合，并提供相应的代码示例。方法一：使用GROUP_CONCAT函数MySQL提供了一个内置的......
  • P6835 [Cnoi2020] 线形生物题解
    P6835[Cnoi2020]线形生物题解题目描述求从\(1\)到\(n+1\)的链的期望，其中有\(m\)条返祖边：\(u->v\)这条边\(u\gev\)，等概率，求期望Solution这种爬楼梯的题一般求解\(E(x\rightarrowx+1)\)，则最后答案为\(\sum_{i=1}^nE(i\rightarrowi+1)\)我们考虑从\(x\rightarr......
  • Android平台GB28181设备接入侧音频采集推送示例
    技术背景GB/T28181是广泛应用于视频监控行业的标准协议规范，可以在不同设备之间实现互联互通。今天我们主要探讨Android平台的Audio采集部分。先说如何拿到数据源，在Android平台上采集音频，常用的方式如下：使用MediaRecorder类：MediaRecorder类提供了一组API，可以用于录制音频。您可以使......
  • Android使用Dagger注入的方式初始化对象的简单使用
    一.Dagger简介Dagger2是Google开源的一款依靠注入结构，它的前身是square的Dagger1，Dagger2在Android中有着较为广泛的运用。Dagger2根据Java注解，采用annotationProcessor（注解处理器）在项目编译时动态生成依靠注入需求的Java代码，然后咱们在合适的位置手动完结......
  • Android之adb安装busybox使用wget、telnet等服务
    二、通过busybox安装使用wgetbusyboxwget1也可以直接输入wget，不用加busybox了三、通过busybox使用telnet服务（1）进入root权限su1（2）每次开启adbshell后都需要设置环境变量才能重启busybox服务（没有安装busybox可以看DHCPv6之GitHub项目Android侧验证）exportPATH=/data/busybox:......
  • spark多表join
    Spark多表Join在大数据处理中，数据通常以分布式存储和处理的方式进行管理。当数据存储在不同的表中，并且需要将它们合并在一起以进行分析时，就需要使用多表连接操作。Spark是一个流行的分布式计算框架，提供了强大的多表连接功能，可以高效地处理大规模数据集。什么是多表Join？多表Join......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99