一、线段树分裂

类似于 \(FHQ-Treap\) 的方式，下给出模板题代码。

//Luogu5494
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,M=5e6+5;
int n,m,id,cnt,rt[N];
int sz[M],ls[M],rs[M];
void push_up(int x){
	sz[x]=sz[ls[x]]+sz[rs[x]];
}void add(int &x,int l,int r,int v,int k){
	if(!x) x=++id;
	if(l==r) return sz[x]+=k,void();
	int mid=(l+r)/2;
	if(v<=mid) add(ls[x],l,mid,v,k);
	else add(rs[x],mid+1,r,v,k);
	push_up(x);
}int kth(int x,int l,int r,int k){
	if(sz[x]<k) return -1;
	if(l==r) return l;
	int mid=(l+r)/2;
	if(sz[ls[x]]>=k) return kth(ls[x],l,mid,k);
	return kth(rs[x],mid+1,r,k-sz[ls[x]]);
}int merge(int x,int y,int l,int r){
	if(!x||!y) return x+y;
	if(l==r){
		sz[x]+=sz[y];
		return x;
	}int mid=(l+r)/2;
	ls[x]=merge(ls[x],ls[y],l,mid);
	rs[x]=merge(rs[x],rs[y],mid+1,r);
	return push_up(x),x;
}void spilt(int x,int &y,int k){
	if(!x) return;y=++id;
	if(sz[ls[x]]>=k) swap(rs[x],rs[y]);
	else spilt(rs[x],rs[y],k-sz[ls[x]]);
	if(sz[ls[x]]>k) spilt(ls[x],ls[y],k);
	push_up(x),push_up(y);
}int sum(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R) return sz[x];
	int mid=(l+r)/2,re=0;
	if(L<=mid) re=sum(ls[x],l,mid,L,R);
	if(R>mid) re+=sum(rs[x],mid+1,r,L,R);
	return re;
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m,cnt=1;
	for(int i=1,x;i<=n;i++)
		cin>>x,add(rt[1],1,n,i,x);
	while(m--){
		int opt;cin>>opt;
		if(!opt){
			int p,x,y,a,lx,rx;
			cin>>p>>x>>y;
			lx=sum(rt[p],1,n,1,y);
			rx=sum(rt[p],1,n,x,y);
			spilt(rt[p],rt[++cnt],lx-rx);
			spilt(rt[cnt],a,rx);
			rt[p]=merge(rt[p],a,1,n);
		}if(opt==1){
			int p,t;cin>>p>>t;
			rt[p]=merge(rt[p],rt[t],1,n);
		}if(opt==2){
			int p,x,q;cin>>p>>x>>q;
			add(rt[p],1,n,q,x);
		}if(opt==3){
			int p,x,y;cin>>p>>x>>y;
			cout<<sum(rt[p],1,n,x,y)<<"\n";
		}if(opt==4){
			int p,k;cin>>p>>k;
			cout<<kth(rt[p],1,n,k)<<"\n";
		}
	}return 0;
}

二、线段树优化建图

考虑要从一段区间向另一段区间连边。容易想到首先建立中转点，将 \(n^2\) 的边数降到 \(n\)。当然，我们也可以结合线段树，将边数降到 \(\log n\) 级别。

下给出相对模板题的题的代码。

//CF786B
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=8e5+5;
struct node{int y,c;};
bool operator<(node x,node y){
	return x.c>y.c;
}vector<node>g[N];
int n,m,s,a[N],dis[N];
priority_queue<node>q;
void dij(int s){
	memset(dis,0x3f,sizeof(dis));
	q.push({s,dis[s]=0});
	while(q.size()){
		int x=q.top().y;
		int w=q.top().c;q.pop();
		if(w!=dis[x]) continue;
		for(auto nd:g[x]){
			int y=nd.y,c=nd.c;
			if(dis[y]>w+c)
				q.push({y,dis[y]=w+c});
		}
	}
}void build(int x,int l,int r){
	if(l==r){
		g[x+4*n].push_back({x,0});
		return a[l]=x,void();
	}int mid=(l+r)/2;
	g[x*2].push_back({x,0});
	g[x*2+1].push_back({x,0});
	g[x+4*n].push_back({x*2+4*n,0});
	g[x+4*n].push_back({x*2+1+4*n,0});
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
}void get1(int x,int l,int r,int L,int R,int gt,int w){
	if(L<=l&&r<=R)
		return g[gt].push_back({x+4*n,w}),void();
	int mid=(l+r)/2;
	if(L<=mid) get1(x*2,l,mid,L,R,gt,w);
	if(R>mid) get1(x*2+1,mid+1,r,L,R,gt,w);
}void get2(int x,int l,int r,int L,int R,int gt,int w){
	if(L<=l&&r<=R)
		return g[x].push_back({gt,w}),void();
	int mid=(l+r)/2;
	if(L<=mid) get2(x*2,l,mid,L,R,gt,w);
	if(R>mid) get2(x*2+1,mid+1,r,L,R,gt,w);
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>s,build(1,1,n);
	while(m--){
		int opt;cin>>opt;
		if(opt==1){
			int u,v,w;cin>>u>>v>>w;
			g[a[u]].push_back({a[v]+4*n,w});
		}if(opt==2){
			int u,l,r,w;cin>>u>>l>>r>>w;
			get1(1,1,n,l,r,a[u],w);
		}if(opt==3){
			int u,l,r,w;cin>>u>>l>>r>>w;
			get2(1,1,n,l,r,a[u]+4*n,w);
		}
	}dij(a[s]);
	for(int i=1;i<=n;i++)
		cout<<(dis[a[i]]>1e18?-1:dis[a[i]])<<" ";
	return 0;
}

三、线段树分治

主要特征是在一段时间内加边，将时间轴线段树化，然后进行区间修改，之后离线简单处理。通常要结合可撤销并查集，通常时间复杂度为 \(O(n\log^2n)\)。

//BZOJ4045+Luogu5494
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,k,fa[N],sz[N];
struct mer{
	int sz,x,y;
};stack<mer>st;
struct ed{
	int x,y;
};vector<ed>g[4*N];
inline void init(){
	for(int i=1;i<=2*n;i++)
		fa[i]=i,sz[i]=1;
}inline int find(int x){
	return fa[x]==x?x:find(fa[x]);
}inline void unite(int x,int y){
	x=find(x),y=find(y);
	if(x==y) return;
	if(sz[x]<sz[y]) swap(x,y);
	st.push({sz[x],x,y});
	fa[y]=x,sz[x]+=sz[y];
}inline void chg(int x,int l,int r,int L,int R,ed e){
	if(L>R) return;
	if(L<=l&&r<=R){
		g[x].push_back(e);
		return;
	}int mid=(l+r)/2;
	if(L<=mid) chg(x*2,l,mid,L,R,e);
	if(R>mid) chg(x*2+1,mid+1,r,L,R,e);
}inline void solve(int x,int l,int r){
	int ans=1,ltp=st.size();
	for(auto e:g[x]){
		if(find(e.x)==find(e.y)){ans=0;break;}
		unite(e.x,e.y+n),unite(e.x+n,e.y);
	}int mid=(l+r)/2;
	if(!ans) for(int i=l;i<=r;i++) cout<<"No\n";
	else if(l==r) cout<<"Yes\n";
	else solve(x*2,l,mid),solve(x*2+1,mid+1,r);
	while(st.size()>ltp){
		mer x=st.top();st.pop();
		fa[x.y]=x.y,sz[x.x]=x.sz;
	}
}int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k,init();
	while(m--){
		int x,y,l,r;
		cin>>x>>y>>l>>r;
		chg(1,1,k,l+1,r,{x,y});
	}solve(1,1,k);
	return 0;
}

未完待续……