主席树|求区间第k小模板

主席树

学了主席树，用来求区间上的第k小
写一下自己整理后的模板

求区间第k小

#include<bits/stdc++.h>
using namespace std;

//求区间第k小 

const int maxn = 500010;
struct node{
	int v,lc,rc;
}T[maxn * 21];
int n,m;
int root[maxn];
int e; 

void insert(int pre,int cur,int pos,int l,int r){
	if(l == r){
		T[cur].v = T[pre].v + 1;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <=mid ){
		T[cur].lc = ++e; //新建左子结点 
		T[cur].rc = T[pre].rc; //保留右子节点 
		insert(T[pre].lc,T[cur].lc,pos,l,mid); //insert左 
	}else{
		T[cur].rc = ++e; //新建右子节点 
		T[cur].lc = T[pre].lc; //保留左子结点 
		insert(T[pre].rc,T[cur].rc,pos,mid+1,r); //insert右 
	}
	T[cur].v = T[T[cur].lc].v + T[T[cur].rc].v;
}


int query(int ql,int qr,int l,int r,int k){
	if(l == r) return l;
	int mid = (l + r) >> 1;
	int sum = T[T[qr].lc].v - T[T[ql].lc].v;
	if(sum >= k) return query(T[ql].lc,T[qr].lc,l,mid,k);
	else return query(T[ql].rc,T[qr].rc,mid+1,r,k-sum);  //这个ql.rc 和 qr.lc什么时候用老是搞不清楚 
} 


int main(){
	int x,y,d,k;
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>d;
		root[i] = ++e;
		insert(root[i-1],root[i],d,1,n);
	}
	while(m--){
		cin>>x>>y>>k;
		cout<<query(root[x-1],root[y],1,n,k)<<endl;
	}
	return 0;
} 

SPOJ 3946主席树 + 离散化

当数据比较大时(比如这道题的1e9那么大)，就需要先离散化了。

#include<bits/stdc++.h>
using namespace std;
//sp3946

const int maxn = 500010;
struct node{
	int v,lc,rc;
}T[maxn * 21];
int n,m;
int root[maxn];
int ranks[maxn];
int e; 

struct A{
	int x,idx;
	bool operator < (const A &temp)const{
		return x < temp.x;
	}
}a[maxn];

void insert(int pre,int cur,int pos,int l,int r){
	if(l == r){
		T[cur].v = T[pre].v + 1;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <=mid ){
		T[cur].lc = ++e; //新建左子结点 
		T[cur].rc = T[pre].rc; //保留右子节点 
		insert(T[pre].lc,T[cur].lc,pos,l,mid); //insert左 
	}else{
		T[cur].rc = ++e; //新建右子节点 
		T[cur].lc = T[pre].lc; //保留左子结点 
		insert(T[pre].rc,T[cur].rc,pos,mid+1,r); //insert右 
	}
	T[cur].v = T[T[cur].lc].v + T[T[cur].rc].v;
}

int query(int ql,int qr,int l,int r,int k){
	if(l == r) return l;
	int mid = (l + r) >> 1;
	int sum = T[T[qr].lc].v - T[T[ql].lc].v;
	if(sum >= k) return query(T[ql].lc,T[qr].lc,l,mid,k);
	else return query(T[ql].rc,T[qr].rc,mid+1,r,k-sum);  //这个ql.rc 和 qr.lc什么时候用老是搞不清楚 
} 

int main(){
	int x,y,d,k;
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].x;
		a[i].idx = i;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++) ranks[a[i].idx] = i;
	for(int i=1;i<=n;i++){
		root[i] = ++e;
		insert(root[i-1],root[i],ranks[i],1,n);
	}
	while(m--){
		cin>>x>>y>>k;
		cout<<query(root[x-1],root[y],1,n,k)<<endl;
	}
	return 0;
} 

poi2014 出现次数次数>(r-l+1)/2

因为这个数 在区间(l,r)上出现的次数最多为1次或者0次
所以用主席树维护每个数出现的次数，然后query查询时 左子树出现次数>goal就往左走、右子树出现次数>goal就往右走，否则return 0，最后直到叶节点(l==r)就会找到目标数

#include<bits/stdc++.h>
using namespace std;
//poi2014

const int maxn = 500001;
struct node{
	int v,lc,rc;
}T[maxn * 21];
int n,m;
int root[maxn];
int e; 

void insert(int pre,int cur,int pos,int l,int r){
	if(l == r){
		T[cur].v = T[pre].v + 1;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <=mid ){
		T[cur].lc = ++e; //新建左子结点 
		T[cur].rc = T[pre].rc; //保留右子节点 
		insert(T[pre].lc,T[cur].lc,pos,l,mid); //insert左 
	}else{
		T[cur].rc = ++e; //新建右子节点 
		T[cur].lc = T[pre].lc; //保留左子结点 
		insert(T[pre].rc,T[cur].rc,pos,mid+1,r); //insert右 
	}
	T[cur].v = T[T[cur].lc].v + T[T[cur].rc].v;
}

int goal;

//对于读入的区间，取长度后进行询问
//如果左子树大于mid的就继续往左走
//右子树大于mid的就继续往右走，否则return 0
int query(int ql,int qr,int l,int r){ //这里 T数组两棵树相减  为什么左子树相减  右子树相减 没搞懂 
	if(l == r) return l;
	int mid = (l + r) >> 1; 
	if(T[T[qr].lc].v - T[T[ql].lc].v > goal) return query(T[ql].lc,T[qr].lc,l,mid);
	else if(T[T[qr].rc].v - T[T[ql].rc].v > goal) return query(T[ql].rc,T[qr].rc,mid+1,r);
	return 0;  //没有就返回0 
} 

int main(){
	int x,y,d;
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>d;
		root[i] = ++e;
		insert(root[i-1],root[i],d,1,n);
	}
	while(m--){
		cin>>x>>y;
		goal = y-x+1>>1;
		cout<<query(root[x-1],root[y],1,n)<<endl;
	}
	return 0;
}