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

浅谈 OI 中各种合并操作

时间：2023-05-19 13:37:01浏览次数：53  
标签：浅谈 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/17414826.html

相关文章

  • [转]Android冷启动白屏解析，带你一步步分析和解决问题
    [img]http://dl2.iteye.com/upload/attachment/0118/3095/d8d8c13d-7225-33cd-9559-efcc6e1f9432.png[/img]关于首次启动程序白屏时间过长这个问题其实我也早就发现了，而且正如评论中所说，有的时候白屏时间可以长达七八秒。看来这个问题已经是一个普遍存在的......
  • Android 有些机型不带tcpdump的解决办法
    输入mount命令[quote]mountrootfson/typerootfs(ro,relatime)tmpfson/devtypetmpfs(rw,relatime,mode=755)devptson/dev/ptstypedevpts(rw,relatime,mode=600)procon/proctypeproc(rw,relatime)sysfson/systypesysfs(rw,relatime)tmpfson......
  • Android 代码混淆proguard技术介绍
    由于各种反编译工具的泛滥，作为Android程序员在2.3版本以前只能通过手动添加proguard来实现代码混淆proguard这个工具是一个java代码混淆的工具在2.3版本的sdk中我们可以看到在android-sdk-windows/tools/下面多了一个proguard文件夹google已经把proguard......
  • Android Fragment完全解析，关于碎片你所需知道的一切
    我们都知道，Android上的界面展示都是通过Activity实现的，Activity实在是太常用了，我相信大家都已经非常熟悉了，这里就不再赘述。但是Activity也有它的局限性，同样的界面在手机上显示可能很好看，在平板上就未必了，因为平板的屏幕非常大，手机的界面放在平板上可能会有......
  • Android系统联系人全特效实现(下)，字母表快速滚动
    其实ListView本身是有一个快速滚动属性的，可以通过在XML中设置android:fastScrollEnabled="true"来启用。包括以前老版本的Android联系人中都是使用这种方式来进行快速滚动的。效果如下图所示：[img]http://dl2.iteye.com/upload/attachment/0088/8223/48aec4c5......
  • Android 百度地图GPS获取定位经纬度
    首先进入百度地图官网，点击开发文档-->Android定位SDK-->获取密匙，进入应用创建界面，创建新的应用。准备好后，在“产品下载”栏目下载Android定位的包，将其打包放入项目中的libs文件目录。之后就需要在AndroidManifest.xml中添加APK，在Application标签中添加：<meta-dataand......
  • 合并两个文件夹下名称交集的标签
    标签为黑白图，合并两个文件夹下名称交集的标签 1#合并两个文件夹下相同名称的两张png标签2#3#开发时间：2023/5/1816:384importos56fromPILimportImage78defmerge(path1,path2,path3):9#打开第一张图片10img1=Image.open(path1......
  • P5540 [BalkanOI2011] timeismoney | 最小乘积生成树
    题意给一个无向图，边有两个权\(a\)和\(b\)，定义一个生成树的权值是\(\left(\sum\limits_{e\inT}a_e\right)\left(\sum\limits_{e\inT}b_e\right)\)，求最小权值生成树。权值相同请最小化\(a\)的和。\(1\len\le200,1\lem\le10000,0\lea_e,b_e\le255\)。题解纯粹记......
  • P2052 [NOI2011] 道路修建
    题不算难，但还是有一点坑的求一条边一侧的结点数量显然可以dfs求出来，另一侧结点数就是\(n-size_i\)，其中\(size_i\)是结点\(i\)的子树大小。longlongans,size[N];inlinevoiddfs(intp,intfa){ size[p]=1; for(autoi:v[p]){ if(i.to==fa)continue; dfs(i.to,p......
  • Oracle从入门到精通-合并查询、添加修改删除数据
    6Oracle表的管理6.5oracle表的管理-表查询（重点）6.5.5Oracle表复杂查询--合并查询·合并查询有时在实际应用中，为了合并多个select语句的结果，可以使用集合操作符号union,unionall,intersect,minus1)union该操作符用于取得两个结果集的并集，当使用该操作符时，=selectename,sal,j......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99