1175 区间中第K大的数

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1175&judgeId=649231
主席树与普通线段树的建树方法有点不同，他只保存他的左儿子和右儿子，以及这条路径覆盖了多少次
比如要找
1 2 3 3 4 5
这6个数[2,4]中第3大的数
先离散化，就只有5个数了，然后建一颗空的线段树，每条路径都是0，然后依次把 1 2 3 3 4 5 加进去，每加一个数，就多加线段树上的一条路径
①这是空树：

②：然后把1加进去

③然后把2加进去

④然后把3加进去

⑤再加一个3进去

⑥把4加进去

⑦把5加进去

假如要求[2,4]这个区间的第3大的数，那么就是用加入了4个数的线段树来减去，加入了两个数的线段树的前面一个线段树（类似于前缀和那种sum[R]-sum[L-1]），就能得到这段区间有多少数了，并且大小顺序是有的，数量也是有的

第4个线段树最下面一层就是：1 1 2 0 0
第1个线段树最下面一层就是：1 0 0 0 0
于是减完就是：0 1 2 0 0

我们查询就是用这个东西来查询的，之前一直没理解好~

那么要求第k小就是求前缀和，看多少能达到k，而求第k大就是求后缀和，看多少能达到k

就像这样，从左边开始，当框起来的数的和达到了k，那就找到了

同理第k大，就从右边开始框，框起来的数达到了k，那么这个位置的数就是第 k大了

#include"bits/stdc++.h"
using namespace std;
const int maxn=5e4+5;
int a[maxn];
int data[maxn];//原始数据
int N,n,tot,Q;
vector<int>Root;//用来保存加进去的每个数的头节点是多少
int tree[maxn*30],Ls[maxn*30],Rs[maxn*30];
int Build(int L,int R)//对离散后的n个数先建一个空数
{
	int id=++tot;
	tree[id]=0;
	if(L==R)return id;
	int mid=L+R>>1;
	Ls[id]=Build(L,mid);
	Rs[id]=Build(mid+1,R);
	return id;
}
void Update(int id1,int v)
{
	v=lower_bound(a+1,a+1+n,v)-a;	//找到这个数排在第几
	int id2=++tot;				//新建一个root
	tree[id2]=tree[id1]+1;
	Root.push_back(id2);
	int L=1,R=n;
	while(L<R)
	{
		int mid=L+R>>1;
		if(v<=mid)			//说明这个数是在左边
		{
			R=mid;
			Ls[id2]=++tot;
			Rs[id2]=Rs[id1];//继承原来的右儿子
			id2=tot;
			id1=Ls[id1];//向左走 
		}
		else
		{
			L=mid+1;
			Rs[id2]=++tot;
			Ls[id2]=Ls[id1];
			id2=tot;
			id1=Rs[id1];//向右走 
		}
		tree[id2]=tree[id1]+1;//这条路径上都加1 
	}
}
int query(int rt1,int rt2,int k)
{
	int id1=Root[rt1];
	int id2=Root[rt2];
	int L=1,R=n;
	while(L<R)
	{
		int mid=L+R>>1;
		//找第k个大的就先忘右边走，找第k个小的就先往左边走 
		int cnt=tree[Rs[id2]]-tree[Rs[id1]];//找第k大的就看Rs的，找第k小的就看Ls的 
		if(cnt>=k)//右边有>=k个数 
		{
			L=mid+1;
			id1=Rs[id1];
			id2=Rs[id2];
		}
		else
		{
			k-=cnt;
			R=mid;
			id1=Ls[id1];
			id2=Ls[id2];
		}
	}
	return L;
}
int main()
{
	while(cin>>N)
	{
		Root.resize(1);
		tot=0;
		for(int i=1; i<=N; i++)
		{
			cin>>data[i];
			a[i]=data[i];
		}
		sort(a+1,a+1+N);
		n=unique(a+1,a+1+N)-(a+1);//离散化
		Root[0]=Build(1,n);
		for(int i=1;i<=N;i++)Update(Root[i-1],data[i]);
		cin>>Q;
        for(int i=1;i<=Q;i++)
        {
            int L,R,K;
            cin>>L>>R>>K;
            L++,R++;
            int pos=query(L-1,R,K);
            cout<<a[pos]<<endl;
        }
	}
}

poj 2104 第k小

只有查询那里有点不同

#include"iostream"
#include"vector"
#include"algorithm"
#include"cstdio"
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int data[maxn];//原始数据
int N,n,tot,Q;
vector<int>Root;//用来保存加进去的每个数的头节点是多少
int tree[maxn*30],Ls[maxn*30],Rs[maxn*30];
int Build(int L,int R)//对离散后的n个数先建一个空数
{
	int id=++tot;
	tree[id]=0;
	if(L==R)return id;
	int mid=L+R>>1;
	Ls[id]=Build(L,mid);
	Rs[id]=Build(mid+1,R);
	return id;
}
void Update(int id1,int v)
{
	v=lower_bound(a+1,a+1+n,v)-a;	//找到这个数排在第几
	int id2=++tot;				//新建一个root
	tree[id2]=tree[id1]+1;
	Root.push_back(id2);
	int L=1,R=n;
	while(L<R)
	{
		int mid=L+R>>1;
		if(v<=mid)			//说明这个数是在左边
		{
			R=mid;
			Ls[id2]=++tot;
			Rs[id2]=Rs[id1];//继承原来的右儿子
			id2=tot;
			id1=Ls[id1];//向左走
		}
		else
		{
			L=mid+1;
			Rs[id2]=++tot;
			Ls[id2]=Ls[id1];
			id2=tot;
			id1=Rs[id1];//向右走
		}
		tree[id2]=tree[id1]+1;//这条路径上都加1
	}
}
int query(int rt1,int rt2,int k)
{
	int id1=Root[rt1];
	int id2=Root[rt2];
	int L=1,R=n;
	while(L<R)
	{
		int mid=L+R>>1;
		int cnt=tree[Ls[id2]]-tree[Ls[id1]];//找第k小就看左边 

		if(cnt>=k) 
		{
			R=mid;
			id1=Ls[id1];
			id2=Ls[id2];
		}
		else
		{
			k-=cnt;
			L=mid+1;
			id1=Rs[id1];
			id2=Rs[id2];
		}
	}
	return L;
}
int main()
{
	while(cin>>N>>Q)
	{
		
		Root.resize(1);
		tot=0;
		for(int i=1; i<=N; i++)
		{
			cin>>data[i];
			a[i]=data[i];
		}
		sort(a+1,a+1+N);
		n=unique(a+1,a+1+N)-(a+1);//离散化
		Root[0]=Build(1,n);
		for(int i=1; i<=N; i++)Update(Root[i-1],data[i]);
		for(int i=1; i<=Q; i++)
		{
			int L,R,K;
            cin>>L>>R>>K;
			int pos=query(L-1,R,K);
            cout<<a[pos]<<endl;
		}

	}
}

划分树：

/* 划分树 */
#include"iostream"
#include"algorithm"
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int tree[30][maxn];
int num[30][maxn];
int N,M;
void print()
{
	int NN=1;
	while(NN<N)
	{
		NN<<=1;
		for(int i=1;i<=N;i++)cout<<tree[NN-1][i]<<" ";
		cout<<"\n";
	}
	cout<<"\n";
}
void Build(int dep,int L,int R)
{
	if(L==R)return ;
	int mid=(L+R)>>1;
	int same=mid-L+1;
	int ls=L,rs=mid+1;
	for(int i=L;i<=R;i++)if(tree[dep][i]>a[mid])same--;
	for(int i=L;i<=R;i++)
	{
		if(i==L)num[dep][i]=0;
		else num[dep][i]=num[dep][i-1];
		
		if(tree[dep][i]>a[mid])
		{
			num[dep][i]++;
			tree[dep+1][ls++]=tree[dep][i];
		}
		else if(tree[dep][i]==a[mid]&&same)
		{
			same--;
			num[dep][i]++;
			tree[dep+1][ls++]=tree[dep][i];
		}
		else tree[dep+1][rs++]=tree[dep][i];
	}
	Build(dep+1,L,mid);
	Build(dep+1,mid+1,R);
}
int Query(int dep,int ql,int qr,int L,int R,int K)
{
	if(L==R)return tree[dep][L];
	int mid=(L+R)>>1;
	int c1,c2;
	if(ql==L)
	{
		c1=0;
		c2=num[dep][qr];
	}
	else
	{
		c1=num[dep][ql-1];
		c2=num[dep][qr]-c1;
	}
	
	if(K<=c2)
	{
		ql=L+c1;
		qr=L+c1+c2-1;//这儿为什么减1 啊？ 
		return Query(dep+1,ql,qr,L,mid,K);
	}
	else
	{
		ql+=mid-L+1 - c1;
		qr=mid-L+1 +qr-c1-c2;
		return Query(dep+1,ql,qr,mid+1,R,K-c2);
	}
}
int main()
{
	cin>>N;
	for(int i=1;i<=N;i++)
	{
		cin>>a[i];
		tree[0][i]=a[i];
	}
	sort(a+1,a+1+N,greater<int>());
	Build(0,1,N);
	cin>>M;
	for(int i=1;i<=M;i++)
	{
		int t1,t2,K;
		cin>>t1>>t2>>K;
		t1++;
		t2++;
		cout<<Query(0,t1,t2,1,N,K)<<"\n";
	}
}

求区间第k大（小）的数

文章目录

1175 区间中第K大的数

poj 2104 第k小

划分树：