您的位置: 首页  >  IT文章  >  【刷题】洛谷 P3834 【模板】可持久化线段树 1（主席树）

【刷题】洛谷 P3834 【模板】可持久化线段树 1（主席树）

分类: IT文章 • 2022-04-03 20:30:15

【刷题】洛谷 P3834 【模板】可持久化线段树 1（主席树）

题目背景

这是个非常经典的主席树入门题——静态区间第K小

数据已经过加强，请使用主席树。同时请注意常数优化

题目描述

如题，给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。

输入输出格式

输入格式：

第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。

第二行包含N个正整数，表示这个序列各项的数字。

接下来M行每行包含三个整数l, r, kl,r,k , 表示查询区间[l, r][l,r] 内的第k小值。

输出格式：

输出包含k行，每行1个正整数，依次表示每一次查询的结果

输入输出样例

输入样例#1：

5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

输出样例#1：

6405
15770
26287
25957
26287

说明

数据范围：

对于20%的数据满足：(1 leq N, M leq 10)

对于50%的数据满足：(1 leq N, M leq 10^3)

对于80%的数据满足：(1 leq N, M leq 10^5)

对于100%的数据满足：(1 leq N, M leq 2cdot 10^5)

对于数列中的所有数(a_i)​ ，均满足(-{10}^9 leq a_i leq {10}^9)

样例数据说明：

N=5，数列长度为5，数列从第一项开始依次为([25957, 6405, 15770, 26287, 26465 ])

第一次查询为([2, 2]) 区间内的第一小值，即为6405

第二次查询为([3, 4]) 区间内的第一小值，即为15770

第三次查询为([4, 5]) 区间内的第一小值，即为26287

第四次查询为([1, 2]) 区间内的第二小值，即为25957

第五次查询为([4, 4]) 区间内的第一小值，即为26287

题解

主席树
这道题当作是我学习主席树的开端吧，模板题
主席树维护的是区间，但这个区间不是下标（即位置）的区间，而是权值的区间
在一个版本中

  • 区间([l,l])上记录的是(l)这个数出现了多少次
  • 区间([l,r])上记录的就是(l,l+1,...,r-1,r)每个数出现次数之和了

所以要先离散化
主席树说白了就是给一个长度为(n)的序列建(n)棵权值线段树，第(i)棵线段树只存了(a_1,a_2,a_3,...a_{i-1},a_i)
这样我们对于本题这样的静态查询第(k)小，就可以差分了（想一想原理）
然后发现相邻两棵线段树改变的只有一条路径上的值，其它的值都是一样的，那么为了节省空间，我们把那些值一样的存在同一个节点（即共用节点），就不用再开节点了
同时，我们称第(i)棵线段树为第(i)个版本
差分的话，就是
如果要查询([l,r])中的信息，那么我们看
第(r)棵线段树记录的是(a_1,a_2,...,a_r)中的信息
第(l-1)棵线段树记录的是(a_1,a_2,...a_{l-1})中的信息
它们相减后，就变成(a_l,a_{l+1},...,a_r)中的信息了
而它们能够相减的依据是：每一棵线段树每一个节点维护的内容是一样的（只是其中的值不一样而已）

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ld long double
#define Mid ((l+r)>>1)
#define lson l,Mid
#define rson Mid+1,r
const int MAXN=200000+10;
int n,m,A[MAXN];
struct ChairMan_Tree{
	int sum[MAXN<<5],lc[MAXN<<5],rc[MAXN<<5],cnt,root[MAXN];
	inline void init()
	{
		memset(sum,0,sizeof(sum));
		memset(lc,0,sizeof(lc));
		memset(rc,0,sizeof(rc));
		cnt=0;
	}
	inline void Build(int &rt,int l,int r)
	{
		rt=++cnt;
		sum[rt]=0;
		if(l==r)return ;
		Build(lc[rt],lson);
		Build(rc[rt],rson);
	}
	inline void Insert(int &rt,int l,int r,int last,int pos)
	{
		rt=++cnt;
		lc[rt]=lc[last];
		rc[rt]=rc[last];
		sum[rt]=sum[last]+1;
		if(l==r)return ;
		else
		{
			if(pos<=Mid)Insert(lc[rt],lson,lc[last],pos);
			else Insert(rc[rt],rson,rc[last],pos);
		}
	};
	inline int Query(int now,int last,int l,int r,int k)
	{
		if(l==r)return l;
		else
		{
			int t=sum[lc[now]]-sum[lc[last]];
			if(k<=t)return Query(lc[now],lc[last],lson,k);
			else return Query(rc[now],rc[last],rson,k-t);
		}
	};
};
ChairMan_Tree T;
std::vector<int> V;
std::map<int,int> M;
template<typename T> inline void read(T &x)
{
	T data=0,w=1;
	char ch=0;
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')w=-1,ch=getchar();
	while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
	x=data*w;
}
template<typename T> inline void write(T x,char c=' ')
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
	if(c!=' ')putchar(c);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void discre()
{
	sort(V.begin(),V.end());
	V.erase(unique(V.begin(),V.end()),V.end());
	for(register int i=1;i<=n;++i)
	{
		int pre=A[i];
		A[i]=lower_bound(V.begin(),V.end(),A[i])-V.begin()+1;
		M[A[i]]=pre;
	}
}
int main()
{
	read(n);read(m);
	T.init();
	T.Build(T.root[0],1,n);
	for(register int i=1;i<=n;++i)
	{
		read(A[i]);
		V.push_back(A[i]);
	}
	discre();
	for(register int i=1;i<=n;++i)T.Insert(T.root[i],1,n,T.root[i-1],A[i]);
	while(m--)
	{
		int l,r,k;
		read(l);read(r);read(k);
		write(M[T.Query(T.root[r],T.root[l-1],1,n,k)],'
');
	}
	return 0;
}

相关推荐