首页 > 其他分享 >二逼平衡树

二逼平衡树

时间：2024-02-16 09:56:14浏览次数：19  
标签：return int 查询 query 操作 平衡 now

它是真“二逼”啊。

Describe：

维护一个序列，支持以下操作：

  1. 查询 \(x\) 在区间内的排名；
  2. 查询区间内排名为 \(k\) 的值；
  3. 修改某一位置上的数值；
  4. 查询 \(x\) 在区间内的前驱（前驱定义为小于 \(x\)，且最大的数）；
  5. 查询 \(x\) 在区间内的后继（后继定义为大于 \(x\)，且最小的数）。

Solution:

经典树套树。但选择什么树呢？看到操作，很容易想到线段树套平衡树。但是它的码量和细节比我命都长。这确实是一种好方法，你愿意写就写吧。我选择树状数组套权值线段树。

在学主席树时，就可以知道主席树是可以支持第二个操作的。对于区间的限制，也很方便处理。主席树本质上就是树的前缀和，对于区间是可以通过差分限制的。但还需要支持操作三，而前缀和修改是 \(O(n)\) 的。这时就是树状数组派上作用了。就由它来平摊查询和修改的复杂度。

具体而言：

对于每个操作，先用树状数组选出需要操作的树。

void prepare(int l,int r)
{
	cnt[0]=cnt[1]=0;
	for(int i=r;i;i-=lowbit(i))
		tmp[++cnt[0]][0]=rt[i];
	for(int i=l-1;i;i-=lowbit(i))
		tmp[++cnt[1]][1]=rt[i];
}

对于操作一，将 \(x\) 与左子树中最大值比较，若大于则计入左子树的总数，下到右子树做同样操作，反之直接下到左子树。

int query_rank(int l,int r,int c)
{
	if(l==r)
		return 0;
	int mid=(l+r)>>1;
	if(c>v[mid-1])
	{
		int s=0;
		for(int i=1;i<=cnt[0];i++)
		{
			s+=tr[lc(tmp[i][0])].siz;
			tmp[i][0]=rc(tmp[i][0]);
		}
		for(int i=1;i<=cnt[1];i++)
		{
			s-=tr[lc(tmp[i][1])].siz;
			tmp[i][1]=rc(tmp[i][1]);
		}
		return s+query_rank(mid+1,r,c);
	}
	else
	{
		for(int i=1;i<=cnt[0];i++)
			tmp[i][0]=lc(tmp[i][0]);
		for(int i=1;i<=cnt[1];i++)
			tmp[i][1]=lc(tmp[i][1]);
		return query_rank(l,mid,c);
	}
}
int prepare_query_rank(int l,int r,int c)
{
	prepare(l,r);
	return query_rank(1,len,c)+1;
}

对于操作二，可以判断左子树的叶子数（序列都在叶子上）是否大于当前的排名，是则减去右子树的叶子数，下到右子树做同样操作，否则下到左子树。

int query_kth(int l,int r,int c)
{
	if(l==r)
		return v[l-1];
	int s=0;
	for(int i=1;i<=cnt[0];i++)
		s+=tr[lc(tmp[i][0])].siz;
	for(int i=1;i<=cnt[1];i++)
		s-=tr[lc(tmp[i][1])].siz;
	int mid=(l+r)>>1;
	// cerr<<l<<' '<<r<<' '<<c<<' '<<s<<'\n';
	if(c>s)
	{
		for(int i=1;i<=cnt[0];i++)
			tmp[i][0]=rc(tmp[i][0]);
		for(int i=1;i<=cnt[1];i++)
			tmp[i][1]=rc(tmp[i][1]);
		return query_kth(mid+1,r,c-s);
	}
	else 
	{
		for(int i=1;i<=cnt[0];i++)
			tmp[i][0]=lc(tmp[i][0]);
		for(int i=1;i<=cnt[1];i++)
			tmp[i][1]=lc(tmp[i][1]);
		return query_kth(l,mid,c);
	}
}
int prepare_query_kth(int l,int r,int c)
{
	prepare(l,r);
	return query_kth(1,len,c);
}

对于操作三，对每个有影响的树直接修改即可。

void insert(int &now,int l,int r,int x,int c)
{
	if(!now)
		now=++trlen;
	tr[now].siz+=c;
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	if(x<=mid)
		insert(lc(now),l,mid,x,c);
	else
		insert(rc(now),mid+1,r,x,c);
}
int lowbit(int x)
{
	return x&-x;
}
int getid(int x)
{
	return std::lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void modify(int x,int c)
{
	for(int i=x;i<=n;i+=lowbit(i))
		insert(rt[i],1,len,getid(a[x]),-1);
	a[x]=c;
	for(int i=x;i<=n;i+=lowbit(i))
		insert(rt[i],1,len,getid(a[x]),1);
}

而操作四可以利用操作一和操作二实现。对于当前区间，如果比 \(x\) 的排名小就满足小于 \(x\) 的条件，且排名最高，就满足且最大的数的条件，也即查询 \(x\) 的排名减一的值。

int query_nxt(int l,int r,int k)
{
	int rk=prepare_query_rank(l,r,k)-1;
	return prepare_query_kth(l,r,rk);
}

操作五同样也可以利用操作一和操作二实现，但与操作四略有区别。若只是排名加一，则可能查询到与 \(x\) 相同的值。但若查询 \(x+1\) 的排名，就满足了大于 \(x\) 且最小值的条件了。因为查询排名时，都是查询相同值的最小排名。

int query_pre(int l,int r,int k)
{
	int rk=prepare_query_rank(l,r,k+1);
	return prepare_query_kth(l,r,rk);
}

时间复杂度 \(O(n\log^2 n)\)，空间复杂度 \(O(n\log^2 n)\)。

剩下注意亿点点细节，就可以愉快的 AC 了。

Code:

完整代码奉上：

bool _Start;
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
namespace IO
{
	#define TP template<typename T>
	#define TP_ template<typename T,typename ... T_>
	#ifdef DEBUG
	#define gc() (getchar())
	#else
	char buf[1<<20],*p1,*p2;
	#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
	#endif
	#ifdef DEBUG
	void pc(const char &c)
	{
		putchar(c);
	}
	#else
	char pbuf[1<<20],*pp=pbuf;
	void pc(const char &c)
	{
		if(pp-pbuf==1<<20)
			fwrite(pbuf,1,1<<20,stdout),pp=pbuf;
		*pp++=c;
	}
	struct IO{~IO(){fwrite(pbuf,1,pp-pbuf,stdout);}}_;
	#endif
	TP void read(T &x)
	{
		x=0;static int f;f=0;static char ch;ch=gc();
		for(;ch<'0'||ch>'9';ch=gc())ch=='-'&&(f=1);
		for(;ch>='0'&&ch<='9';ch=gc())x=(x<<1)+(x<<3)+(ch^48);
		f&&(x=-x);
	}
	TP void write(T x)
	{
		if(x<0)
			pc('-'),x=-x;
		static T sta[35],top;top=0;
		do
			sta[++top]=x%10,x/=10;
		while(x);
		while(top)
			pc(sta[top--]^48);
	}
	TP_ void read(T &x,T_&...y){read(x);read(y...);}
	TP void writeln(const T x){write(x);pc('\n');}
	TP void writesp(const T x){write(x);pc(' ');}
	TP_ void writeln(const T x,const T_ ...y){writesp(x);writeln(y...);}
	TP void debugsp(const T x){fprintf(stderr,"%d ",x);}
	TP void debug(const T x){fprintf(stderr,"%d\n",x);}
	TP_ void debug(const T x,const T_...y){debugsp(x);debug(y...);}
	TP inline T max(const T &a,const T &b){return a>b?a:b;}
	TP_ inline T max(const T &a,const T_&...b){return max(a,max(b...));} 
	TP inline T min(const T &a,const T &b){return a<b?a:b;}
	TP_ inline T min(const T &a,const T_&...b){return min(a,min(b...));}
	TP inline void swap(T &a,T &b){static T t;t=a;a=b;b=t;}
	TP inline T abs(const T &a){return a>0?a:-a;}
	#undef TP
	#undef TP_
}
using namespace IO;
using std::cerr;
using LL=long long;
constexpr int N=5e4+5;
constexpr int inf=0x7fffffff;
struct trnode
{
	int lc,rc,siz;
}tr[N<<8];int trlen;
int tmp[N][2],cnt[2],a[N],rt[N],len;
std::vector<int>v;
#define lc(x) tr[x].lc
#define rc(x) tr[x].rc
void insert(int &now,int l,int r,int x,int c)
{
	if(!now)
		now=++trlen;
	tr[now].siz+=c;
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	if(x<=mid)
		insert(lc(now),l,mid,x,c);
	else
		insert(rc(now),mid+1,r,x,c);
}
int query_kth(int l,int r,int c)
{
	if(l==r)
		return v[l-1];
	int s=0;
	for(int i=1;i<=cnt[0];i++)
		s+=tr[lc(tmp[i][0])].siz;
	for(int i=1;i<=cnt[1];i++)
		s-=tr[lc(tmp[i][1])].siz;
	int mid=(l+r)>>1;
	// cerr<<l<<' '<<r<<' '<<c<<' '<<s<<'\n';
	if(c>s)
	{
		for(int i=1;i<=cnt[0];i++)
			tmp[i][0]=rc(tmp[i][0]);
		for(int i=1;i<=cnt[1];i++)
			tmp[i][1]=rc(tmp[i][1]);
		return query_kth(mid+1,r,c-s);
	}
	else 
	{
		for(int i=1;i<=cnt[0];i++)
			tmp[i][0]=lc(tmp[i][0]);
		for(int i=1;i<=cnt[1];i++)
			tmp[i][1]=lc(tmp[i][1]);
		return query_kth(l,mid,c);
	}
}
int query_rank(int l,int r,int c)
{
	if(l==r)
		return 0;
	int mid=(l+r)>>1;
	if(c>v[mid-1])
	{
		int s=0;
		for(int i=1;i<=cnt[0];i++)
		{
			s+=tr[lc(tmp[i][0])].siz;
			tmp[i][0]=rc(tmp[i][0]);
		}
		for(int i=1;i<=cnt[1];i++)
		{
			s-=tr[lc(tmp[i][1])].siz;
			tmp[i][1]=rc(tmp[i][1]);
		}
		return s+query_rank(mid+1,r,c);
	}
	else 
	{
		for(int i=1;i<=cnt[0];i++)
			tmp[i][0]=lc(tmp[i][0]);
		for(int i=1;i<=cnt[1];i++)
			tmp[i][1]=lc(tmp[i][1]);
		return query_rank(l,mid,c);
	}
}
int n,m;
struct Query
{
	int op,l,r,x,k;
	int pos,y;
}q[N];
int lowbit(int x)
{
	return x&-x;
}
int getid(int x)
{
	return std::lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void modify(int x,int c)
{
	for(int i=x;i<=n;i+=lowbit(i))
		insert(rt[i],1,len,getid(a[x]),-1);
	a[x]=c;
	for(int i=x;i<=n;i+=lowbit(i))
		insert(rt[i],1,len,getid(a[x]),1);
}
void prepare(int l,int r)
{
	cnt[0]=cnt[1]=0;
	for(int i=r;i;i-=lowbit(i))
		tmp[++cnt[0]][0]=rt[i];
	for(int i=l-1;i;i-=lowbit(i))
		tmp[++cnt[1]][1]=rt[i];
}
int prepare_query_kth(int l,int r,int c)
{
	prepare(l,r);
	return query_kth(1,len,c);
}
int prepare_query_rank(int l,int r,int c)
{
	prepare(l,r);
	return query_rank(1,len,c)+1;
}
int query_nxt(int l,int r,int k)
{
	int rk=prepare_query_rank(l,r,k)-1;
	return prepare_query_kth(l,r,rk);
}
int query_pre(int l,int r,int k)
{
	int rk=prepare_query_rank(l,r,k+1);
	return prepare_query_kth(l,r,rk);
}
int prepare_query(int l,int r,int c,int nxt)
{
	if(nxt)
		return query_nxt(l,r,c);
	else 
		return query_pre(l,r,c);
}
bool _End;
int main()
{
	// fprintf(stderr,"%.2 MBlf\n",(&_End-&_Start)/1048576.0);
	read(n,m);
	for(int i=1;i<=n;i++)
		read(a[i]),v.emplace_back(a[i]);
	for(int i=1;i<=m;i++)
	{
		read(q[i].op);
		switch(q[i].op)
		{
			case 1:
				read(q[i].l,q[i].r,q[i].x);
				break;
			case 2:
				read(q[i].l,q[i].r,q[i].k);
				break;
			case 3:
				read(q[i].pos,q[i].y);
				v.emplace_back(q[i].y);
				break;
			case 4:
				read(q[i].l,q[i].r,q[i].x);
				v.emplace_back(q[i].x);
				break;
			case 5:
				read(q[i].l,q[i].r,q[i].x);
				v.emplace_back(q[i].x);
				break;
		}
	}
	v.emplace_back(-inf);
	v.emplace_back(inf);
	std::sort(v.begin(),v.end());
	v.erase(std::unique(v.begin(),v.end()),v.end());
	len=v.size();
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j+=lowbit(j))
			insert(rt[j],1,len,getid(a[i]),1);
	for(int i=1;i<=m;i++)
	{
		switch(q[i].op)
		{
			case 1:
				writeln(prepare_query_rank(q[i].l,q[i].r,q[i].x));
				break;
			case 2:
				writeln(prepare_query_kth(q[i].l,q[i].r,q[i].k));
				break;
			case 3:
				modify(q[i].pos,q[i].y);
				break;
			case 4:
			{
				writeln(prepare_query(q[i].l,q[i].r,q[i].x,1));
				break;
			}
			case 5:
			{
				writeln(prepare_query(q[i].l,q[i].r,q[i].x,0));
				break;
			}
		}
	}
	return 0;
}

打完之后，旁边的同学跟我说，线段树套平衡树码量其实也就跟这个一样大。

标签：return,int,查询,query,操作,平衡,now
From： https://www.cnblogs.com/lofty2007/p/18016927

相关文章

  • 文艺平衡树
    Describe：给定一个有\(n\)个元素且没有重复元素的序列，进行\(m\)次翻转操作，输出最终序列。Solution:翻转操作类似LCT中的makeroot,稍加改造即可。splay有一个很好的性质，就是旋转过后也不改变中序遍历的顺序。所以若将左右子树交换且对子树内的节点做同样的操作，就是一次......
  • 【文化课学习笔记】【化学】选必一：水溶液中的离子反应与平衡（下）
    【化学】选必一：水溶液中的离子反应与平衡（下）盐类水解基本概念定义：盐电离出的离子与水电离出的\(\ce{H+}\)或\(\ce{OH-}\)相互作用生成弱电解质的反应。特点：可逆：水解是可逆反应，在一定条件下达到化学平衡。程度小：通常盐类水解程度很小，一般无沉淀析出、无气体放出。例......
  • 代码随想录算法训练营第十七天| 110.平衡二叉树 257. 二叉树的所有路径 404.左叶
    110.平衡二叉树 题目链接：110.平衡二叉树-力扣（LeetCode）思路：判断平衡二叉树，就是判断两个子树的高度差，继而问题转化为了如何求子树的高度——后序遍历（主要卡在了这里)。递归函数返回的是树的高度，同时用-1来表示退出递归（一开始想着用bool型作为返回值，发现函数不好设计）。同时要关......
  • 在Go中使用接口：实用性与脆弱性的平衡货币的精度
    在Go中使用接口：实用性与脆弱性的平衡原创 TimLiu 爱发白日梦的后端 2024-02-0307:00 发表于广东 听全文爱发白日梦的后端专注Go语言领域的发展，学习成为更牛逼的架构师，日常分享Go语言、架构、软件工具的使用。168篇原创内容公众号点击上方“名......
  • 平衡小车 高速运动时 紧急避障转弯继续运动的超声波传感器代码
    以下是一个使用超声波传感器实现平衡小车高速运动时紧急避障转弯继续运动的示例代码：#include<Wire.h>//定义超声波传感器引脚constinttrigPin=2;//触发引脚constintechoPin=3;//回声引脚//定义电机引脚constintmotorA1=9;constintmotorA2=10;const......
  • 平衡树
    能pbds写pbds无pbds写fhq#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+3;intrt,tot,lc[N],rc[N],val[N],rd[N],sz[N];#definelslc[p]#definersrc[p]voidUp(intp){sz[p]=sz[ls]+sz[rs]+1;}voidSpl(intp,int......
  • 通达信大盘平衡仪优化版指标公式源码
    {指标介绍：红色大盘指数安全，绿色大盘指数调整，红箭头超跌，绿箭头超涨，分析大盘不错的工具。}总家数:=INDEXADV+INDEXDEC;多:=INDEXADV;空:=INDEXDEC;差:=INDEXADV-INDEXDEC;起稳:=Ema(EMA(多,3),5);失衡:=EMA(EMA(EMA(空,4),4),2);生命:=EMA(MA(LLV(起稳,5),3),3);平衡差:=起......
  • 【文化课学习笔记】【物理】平衡力学
    【物理】平衡力学重力大小：\(G=m\mathrm{g}\)；方向：竖直向下；\(\mathrm{g}\)：不是定值，与高度和纬度有关；高度越高，\(\mathrm{g}\)越小；纬度越高，\(\mathrm{g}\)越大。重心：测量方法：悬挂法。规则图形的重心在几何中心。误区：重心不一定在物体上。注意事项：一个装满水的气球下方开......
  • 32_将有序数组转换为平衡二叉搜索树
    108、将有序数组转换为二叉搜索树给你一个整数数组nums，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过1」的二叉树。示例1：输入：nums=[-10,-3,0,5,9]输出：[0,-3,9,-10,nul......
  • P3391 文艺平衡树 题解
    QuestionP3391文艺平衡树写一种数据结构维护有序数列，需要完成以下操作：翻转一个区间，例如原有的序列是\(5,3,3,2,1\)，翻转区间是\([2,4]\)的话，结果是\(5,2,3,4,1\)Solution这道题的表达是\(Splay\)但是\(Splay\)的代码实现比较困难，考虑使用FHQTreap。先思考如何将一......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99