树套树，顾名思义，就是要将两种或多种树形数据结构结合起来，解决一些单独无法解决的问题。

P3157 [CQOI2011]动态逆序对

题意

现在给出 $1\sim n$ 的一个排列，按照某种顺序依次删除 $m$ 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。 $1\le n \le 10^5$ ， $1\le m \le 50000$ 。

点击查看题解

题解

利用树状数组套动态开点线段树来解决这个问题。

使用树状数组维护进行区间前缀和统计，每个树状数组节点管理一个动态开点权值线段树；树状数组将区间划分开，使用动态开点权值线段树维护各自区间中数字出现个数。

考虑删掉一个点位置是 $i$ ，值为 $x_i$ 对逆序对减少的贡献。寻找 $[1,i-1]$ 大于 $x_i$ 的个数以及 $[i+1,n]$ 小于 $x_i$ 的个数（这里的“区间”是指位置）。

时间复杂度为 $O(n \log^2 n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz 
{
	//树状数组套动态开点线段树
	typedef int ll;//（手动滑稽
	const ll N=100000+10,M=1000000000;
	ll cnt=0,n,m,pos[N],root[N];
	long long ans=0,del=0;
	struct SGT
	{
		struct node{int lson,rson,data;}t[N*30*30];
		#define lson t[root].lson
		#define rson t[root].rson
		#define mid ((l+r)/2)
		ll update(ll root,ll l,ll r,ll pos,ll data)
		{
			if(root==0) root=++cnt;
			if(l==r&&r==pos)
			{
				t[root].data+=data;
				return root;
			}
			if(pos<=mid) lson=update(lson,l,mid,pos,data);
			else rson=update(rson,mid+1,r,pos,data);
			t[root].data=t[lson].data+t[rson].data;
			return root;
		}
		ll query(ll root,ll l,ll r,ll x,ll y)
		{
			ll ret=0;
			if(root==0) return 0;
			if(x<=l&&r<=y) return t[root].data;
			if(x<=mid) ret+=query(lson,l,mid,x,y);
			if(y>=mid+1) ret+=query(rson,mid+1,r,x,y);
			return ret;
		}
	}Tree;
	ll lb(ll x){return x&-x;}
	ll query(ll rt,ll x,ll y)
	{
		ll ret=0;
		while(rt>=1)
		{
			ret+=Tree.query(root[rt],1,n,x,y);
			rt-=lb(rt);
		}
		return ret;
	}
	void update(ll rt,ll x,ll data)
	{
		while(rt<=n)
		{
			root[rt]=Tree.update(root[rt],1,n,x,data);
			rt+=lb(rt);
		}
		return;
	}
	void yzmain()
	{
		ll tmp,root;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&tmp);
			pos[tmp]=i;
			ans+=query(i-1,tmp+1,n);
			update(i,tmp,1);
		}
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&tmp);
			printf("%lld\n",ans);
			root=pos[tmp];del=0;
			del+=query(root-1,tmp+1,n);
			del+=query(n,0,tmp-1);//由于树状数组维护的是前缀和，
			del-=query(root,0,tmp-1);//所以这样搞。
			ans-=del;
			update(root,tmp,-1);
		}
		return;
	}
}
int main()
{
	_yz::yzmain();
	return 0;
}

P3380 【模板】二逼平衡树（树套树）

题意

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：

查询 $k$ 在区间内的排名；
查询区间内排名为 $k$ 的值；
修改某一位值上的数值；
查询 $k$ 在区间内的前驱（前驱定义为严格小于 $x$ ，且最大的数，若不存在输出 -2147483647）；
查询 $k$ 在区间内的后继（后继定义为严格大于 $x$ ，且最小的数，若不存在输出 2147483647）。

$1≤n,m≤5×10^4$ ，序列中的值在任何时刻 $\in[0,10^8]$ 。

点击查看题解

题解

模板题，不用多说。这里使用线段树+Splay 实现，~~开 O2 优化也过不了~~。

由于操作中包含区间的限制，所以利用线段树来维护整个数列，每颗节点都开一棵平衡树，管理这个节点维护的范围内的数。

~~调这个代码用了 26 小时，写完之后感觉自己就是二逼~~。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	#define ms(a) memset(a,0,sizeof(a))
	typedef long long ll;
	const ll N=3000000+10,inf=2147483647;
	ll n,m,a[N],opt,l,r,x;
	ll read()
	{
		ll x=0,f=1;
		char ch=getchar();
		while(!isdigit(ch))
		{
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch))
		{
			x=(x<<3)+(x<<1)+(ch^48);
			ch=getchar();
		}
		return x*f;
	}
	struct Splay
	{
		ll son[N][2],data[N],num[N],size[N],dad[N];
		ll cnt;
		Splay()
		{
			ms(son);ms(data);ms(num);
			ms(size);ms(dad);cnt=0;
		}
		void visitor(ll root)
		{
			if(son[root][0]) visitor(son[root][0]);
			printf("%lld ",data[root]);
			if(son[root][1]) visitor(son[root][1]);
		}
		void pushup(ll pos)
		{
			size[pos]=num[pos]+size[son[pos][0]]+size[son[pos][1]];
			return; //size 只需要在 pushup 时更新 
		}
		ll check(ll pos){return son[dad[pos]][1]==pos;}
		void rotate(ll pos)
		{
			ll par=dad[pos],gpar=dad[par],way=check(pos);
			ll son2=son[pos][way^1];
			son[gpar][check(par)]=pos; dad[pos]=gpar;     
			son[par][way]=son2;        dad[son2]=par;
			son[pos][way^1]=par;       dad[par]=pos;                              
			pushup(par);               pushup(pos);                              
			return;
		}
		void splay(ll &root,ll pos,ll des)//不要误认为 des 是根节点 
		{
			while(dad[pos]!=des)
			{
				ll par=dad[pos],gpar=dad[par];
				if(gpar!=des)
				{
					if(check(pos)==check(par)) rotate(par);        
					else rotate(pos);
				}
				rotate(pos);
			}
			if(des==0) root=pos;
		}
		ll _new(ll val,ll fa)
		{
			data[++cnt]=val;dad[cnt]=fa;
			num[cnt]=1;
			pushup(cnt);
			return cnt;
		}
		void insert(ll &root,ll val)
		{
			ll pos=root,fa=0,way=(val>data[pos]);
			if(!pos) {pos=_new(val,0);root=pos;return;}//特判根为空的情况 
			while(pos&&data[pos]!=val)
			{
				fa=pos;
				pos=son[pos][way];
				way=(val>data[pos]);
			}
			if(pos) num[pos]++;
			else{
				pos=_new(val,fa);
				if(fa) son[fa][data[fa]<val]=pos;
			}
			splay(root,pos,0);
		}
		void find(ll &root,ll x)
		{
			ll pos=root,way=(x>data[pos]);
			if(!pos) return;
			while(data[pos]!=x&&son[pos][way])
			{
				pos=son[pos][way];
				way=(x>data[pos]);
			}
			splay(root,pos,0);
		}
		ll rank(ll &root,ll val)
		{
			find(root,val);
			ll pos=son[root][0];//平衡树中存在，好说 
			if(data[root]>=val) return size[pos]-1;
			//如果不存在，且值比 data 小，其排名等价于 data 的排名 
			else return size[pos]+num[root]-1;
			//反之，且值比 data 大，其排名等价于 data 的后继排名 
			//注意减去 -inf 的排名 
			//返回的是比 val 小的数的个数 
		}
		ll pre(ll &root,ll val)
		{
			find(root,val);
			ll pos=root;
			if(data[pos]<val) return pos;
			pos=son[pos][0];
			while(son[pos][1]) pos=son[pos][1];
			return pos;
		}
		ll suc(ll &root,ll val)
		{
			find(root,val);
			ll pos=root;
			if(data[pos]>val) return pos;
			pos=son[pos][1];
			while(son[pos][0]) pos=son[pos][0];
			return pos;
		}
		void remove(ll &root,ll val) 
		{
		    ll l=pre(root,val),r=suc(root,val);
		    splay(root,r,0);splay(root,l,r);
		    ll pos=son[l][1];
		    if(data[pos]!=val) return;
		    if(num[pos]>1)
		    	num[pos]--,splay(root,pos,0);
			else son[l][1]=0;
			pushup(l);/*注意 pushup 的对象*/
		}
	}BST;
	#define ls (p*2)
	#define rs ((p*2)+1)
	#define mid ((l+r)/2)
	struct Seg_tree
	{
		ll root[N];
		Seg_tree(){ms(root);}
		void insert(ll p,ll l,ll r,ll x,ll y)
		{
			if(!root[p])
			{
				BST.insert(root[p],-inf);
				BST.insert(root[p],inf);
			}
			BST.insert(root[p],y);
			if(l==r) return;
			if(x<=mid) insert(ls,l,mid,x,y);
			else insert(rs,mid+1,r,x,y);
		}
		void update(ll p,ll l,ll r,ll x,ll y)
		{
			BST.remove(root[p],a[x]);
			BST.insert(root[p],y);
			if(l==r) return;
			if(x<=mid) update(ls,l,mid,x,y);
			else update(rs,mid+1,r,x,y);
		}
		ll rank(ll p,ll l,ll r,ll x,ll y,ll k)
		{
			ll ret=0;
			if(x<=l&&r<=y) return BST.rank(root[p],k);
			if(x<=mid) ret+=rank(ls,l,mid,x,y,k);
			if(y>=mid+1) ret+=rank(rs,mid+1,r,x,y,k);
			return ret;
		}
		ll atrank(ll p,ll x,ll y,ll k)
		{
			ll l=0,r=100000000,ans;
			while(l<=r)
			{
				ll check=rank(1,1,n,x,y,mid)+1;
				ll M=mid;
				//printf("%lld %lld\n",M,check); 
				if(check>k) r=M-1;
				else l=M+1,ans=M;
			}
			return ans;
		}
		ll pre(ll p,ll l,ll r,ll x,ll y,ll k)
		{
			if(x<=l&&r<=y) return BST.data[BST.pre(root[p],k)];
			ll al=-inf,ar=-inf;
			if(x<=mid) al=pre(ls,l,mid,x,y,k);
			if(y>=mid+1) ar=pre(rs,mid+1,r,x,y,k);
			return max(al,ar);
		}
		ll suc(ll p,ll l,ll r,ll x,ll y,ll k)
		{
			if(x<=l&&r<=y) return BST.data[BST.suc(root[p],k)];
			ll al=inf,ar=inf;
			if(x<=mid) al=suc(ls,l,mid,x,y,k);
			if(y>=mid+1) ar=suc(rs,mid+1,r,x,y,k);
			return min(al,ar);
		}
		void visitor(ll p,ll l,ll r)
		{
			printf("[%lld,%lld]\n",l,r);
			BST.visitor(root[p]);printf("\n");
			if(l==r) return;
			visitor(ls,l,mid);
			visitor(rs,mid+1,r);
		}
	}SGT;
	void yzmain()
	{
		n=read(),m=read();
		for(ll i=1;i<=n;i++)
		{
			a[i]=read();
			SGT.insert(1,1,n,i,a[i]);
		}
		for(ll i=1;i<=m;i++)
		{
			opt=read();
			if(opt==3)
			{
				l=read(),x=read();
				SGT.update(1,1,n,l,x);
				a[l]=x;
			}
			else
			{
				ll ans=0;
				l=read(),r=read(),x=read();
				if(opt==1) ans=SGT.rank(1,1,n,l,r,x)+1;
				else if(opt==2) ans=SGT.atrank(1,l,r,x);
				else if(opt==4) ans=SGT.pre(1,1,n,l,r,x);
				else ans=SGT.suc(1,1,n,l,r,x);
				printf("%lld\n",ans);
			}
		}
		return;
	}
}
int main()
{
	_yz::yzmain();
	return 0;
}

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/4b5701f09701/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 树树状数组线段树一些动态开点线段树

最后更新：2023-08-21, 23:18:21

By Yurchiu.

一些关于树套树的题目

P3157 [CQOI2011]动态逆序对

题意

题解

代码

P3380 【模板】二逼平衡树（树套树）

题意

题解

代码