差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:线段树合并_分裂 [2020/07/07 20:25]
jxm2001 ↷ 页面名由2020-2021:teams:legal_string:线段树合并改为2020-2021:teams:legal_string:线段树合并_分裂
+++ 2020-2021:teams:legal_string:jxm2001:线段树合并_分裂 [2021/07/14 15:53] (当前版本)
jxm2001 [算法思想]
@@ 行 1: / 行 1: @@
-====== 线段树合并 ======
+====== 线段树合并/分裂 ======
 ===== 算法简介 =====
-一种合并多个线段树(一般为权值线段树)的算法，主要用于解决染色问题，时空间复杂度 $O(m\log n)$。
+一种快速合并、分裂线段树(一般为权值线段树)的算法，时空间复杂度 $O(m\log n)$。
 ===== 算法思想 =====
-更新线段树时动态开点，合并时如果遇到叶子节点或空结点就直接 $\text{return}$，否则跑子树。
+更新、分裂线段树时动态开点，易知更新操作时空间复杂度 $O(\log n)$。
-关于空间复杂度，每次动态开点 $O(\log n)$，所以总空间复杂度 $O(m\log n)$，注意线段树是四倍空间。
+关于分裂操作，遇到空结点则返回。其余操作同线段树查询，遇到分裂区间的子区间则将原节点转移给新节点，然后返回。
-关于时间复杂度，每次合并时间复杂度为两棵线段树的重叠部分的结点数，所以不会超过较小的那棵线段树的结点数。
+所以分裂操作的时空间复杂度同线段树查询操作的时间复杂度，即 $O(\log n)$。
-所以合并操作的总时间复杂度等于动态开点总数，即 $O(m\log n)$。
+关于合并操作，如果遇到叶子节点或空结点就直接 $\text{return}$，否则跑子树。
+关于合并操作的时间复杂度，每次合并时间复杂度为两棵线段树的重叠部分的结点数，而每次合并一个节点等价于删除一个节点。
+每个节点至多被删除一次，所以合并操作的总时间复杂度等于空间复杂度，即 $O(m\log n)$。
 ===== 代码模板 =====
+[[https://www.luogu.com.cn/problem/P5494|洛谷p5494]]
 <hidden 查看代码>
 <code cpp>
-const int MAXS=MAXN*60;
+const int MAXN=2e5+5,MAXM=30;
-int root[MAXN],tot;
 struct Node{
-	int max_cnt,ans;//自己需要维护的信息
+	LL cnt;
 	int ch[2];
-}node[MAXS];
+}node[MAXN*MAXM];
-void push_up(int k){//自定义
+struct Pool{
-	if(node[node[k].ch[0]].max_cnt>=node[node[k].ch[1]].max_cnt)
+	int Stack[MAXN*MAXM],top,tot;
-	node[k].max_cnt=node[node[k].ch[0]].max_cnt,node[k].ans=node[node[k].ch[0]].ans;
+	int New(){return top?Stack[top--]:++tot;}
-	else
+	void Delate(int x){
-	node[k].max_cnt=node[node[k].ch[1]].max_cnt,node[k].ans=node[node[k].ch[1]].ans;
+		node[x].cnt=node[x].ch[0]=node[x].ch[1]=0;
-}
+		Stack[++top]=x;
+	}
+}pool;
+void push_up(int k){node[k].cnt=node[node[k].ch[0]].cnt+node[node[k].ch[1]].cnt;}
 void update(int &k,int lef,int rig,int pos,int v){
-	if(!k) k=++tot;
+	if(!k)k=pool.New();
-	if(lef==rig) return node[k].max_cnt+=v,node[k].ans=pos,void();
+	if(lef==rig)
+	return node[k].cnt+=v,void();
 	int mid=lef+rig>>1;
-	if(pos>mid)
+	if(mid>=pos)
-	update(node[k].ch[1],mid+1,rig,pos,v);
-	else
 	update(node[k].ch[0],lef,mid,pos,v);
+	else
+	update(node[k].ch[1],mid+1,rig,pos,v);
 	push_up(k);
 }
 void Merge(int &k1,int k2,int lef,int rig){
 	if(!k1||!k2) return k1|=k2,void();
-	if(lef==rig) return node[k1].max_cnt+=node[k2].max_cnt,void();
+	if(lef==rig) return node[k1].cnt+=node[k2].cnt,pool.Delate(k2);
 	int mid=lef+rig>>1;
 	Merge(node[k1].ch[0],node[k2].ch[0],lef,mid);
 	Merge(node[k1].ch[1],node[k2].ch[1],mid+1,rig);
+	pool.Delate(k2);
 	push_up(k1);
+}
+void split(int &k1,int &k2,int lef,int rig,int L,int R){
+	if(!k1)return;
+	if(L<=lef&&rig<=R){
+		k2=k1;
+		k1=0;
+		return;
+	}
+	k2=pool.New();
+	int mid=lef+rig>>1;
+	if(mid>=L)
+	split(node[k1].ch[0],node[k2].ch[0],lef,mid,L,R);
+	if(mid<R)
+	split(node[k1].ch[1],node[k2].ch[1],mid+1,rig,L,R);
+	push_up(k1);push_up(k2);
+}
+LL Count(int k,int lef,int rig,int L,int R){
+	if(!k)return 0;
+	if(L<=lef&&rig<=R)
+	return node[k].cnt;
+	int mid=lef+rig>>1;
+	if(mid>=R)
+	return Count(node[k].ch[0],lef,mid,L,R);
+	else if(mid<L)
+	return Count(node[k].ch[1],mid+1,rig,L,R);
+	else
+	return Count(node[k].ch[0],lef,mid,L,R)+Count(node[k].ch[1],mid+1,rig,L,R);
+}
+int Rank(int k,int lef,int rig,LL rk){
+	if(node[k].cnt<rk)
+	return -1;
+	int mid=lef+rig>>1;
+	if(lef==rig)return mid;
+	if(rk<=node[node[k].ch[0]].cnt)
+	return Rank(node[k].ch[0],lef,mid,rk);
+	else
+	return Rank(node[k].ch[1],mid+1,rig,rk-node[node[k].ch[0]].cnt);
+}
+int root[MAXN],root_cnt=1;
+int main()
+{
+    int n=read_int(),m=read_int(),v,p,x,y,opt;
+    _rep(i,1,n){
+    	v=read_int();
+    	if(v)
+    	update(root[1],1,n,i,v);
+	}
+	while(m--){
+		opt=read_int(),p=read_int();
+		switch(opt){
+			case 0:
+				x=read_int(),y=read_int();
+				split(root[p],root[++root_cnt],1,n,x,y);
+				break;
+			case 1:
+				x=read_int();
+				Merge(root[p],root[x],1,n);
+				break;
+			case 2:
+				x=read_int(),y=read_int();
+				update(root[p],1,n,y,x);
+				break;
+			case 3:
+				x=read_int(),y=read_int();
+				enter(Count(root[p],1,n,x,y));
+				break;
+			case 4:
+				x=read_int();
+				enter(Rank(root[p],1,n,x));
+				break;
+		}
+	}
+    return 0;
 }
 </code>
@@ 行 74: / 行 157: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5,MAXM=20;
 struct Edge{
@@ 行 261: / 行 297: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5,MAXM=20;
 struct Edge{
@@ 行 452: / 行 441: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5,MAXS=MAXN*40;
 int root[MAXN],tot;
@@ 行 604: / 行 546: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-    int t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline LL read_LL(){
-    LL t=0;bool sign=false;char c=getchar();
-    while(!isdigit(c)){sign|=c=='-';c=getchar();}
-    while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-    return sign?-t:t;
-}
-inline char get_char(){
-    char c=getchar();
-    while(c==' '||c=='\n'||c=='\r')c=getchar();
-    return c;
-}
-inline void write(LL x){
-    register char c[21],len=0;
-    if(!x)return putchar('0'),void();
-    if(x<0)x=-x,putchar('-');
-    while(x)c[++len]=x%10,x/=10;
-    while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=3e5+5;
 int head[MAXN],edge_cnt;

CVBB ACM Team

用户工具

站点工具

差别

页面工具