第K小數（主席樹+離散化）

題目描述

給定長度為 N 的整數序列 A，下标為 1∼N。

現在要執行 M 次操作，其中第 i 次操作為給出三個整數 li,ri,ki，求 A[li],A[li+1],…,A[ri] (即 A 的下标區間 [li,ri])中第 ki 小的數是多少。

輸入格式

第一行包含兩個整數 N 和 M。

第二行包含 N 個整數，表示整數序列 A。

接下來 M 行，每行包含三個整數 li,ri,ki，用以描述第 i 次操作。

輸出格式

對于每次操作輸出一個結果，表示在該次操作中，第 k 小的數的數值。

每個結果占一行。

資料範圍

N≤105,M≤104,|A[i]|≤109

輸入樣例

7 3

1 5 2 6 3 7 4

2 5 3

4 4 1

1 7 3

輸出樣例

5

6

3

題目分析

主席樹模闆。

主席樹本質上就是一個數組套線段樹。

代碼如下

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#define LL long long
#define ULL unsigned long long
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f;
struct Node{			//記錄主席樹節點
	int l,r;
	int size;
}tr[N*21];
int root[N],idx;		//root[]記錄各個版本
int a[N];
vector<int> num;
int insert(int p,int l,int r,int x)			//插入資料
{
	int u=++idx;
	if(l==r)
	{
		tr[u].size=1;
		return u;
	}
	tr[u]=tr[p];
	int mid=l+r>>1;
	if(x<=mid) tr[u].l=insert(tr[p].l,l,mid,x);
	else tr[u].r=insert(tr[p].r,mid+1,r,x);
	tr[u].size=tr[tr[u].l].size+tr[tr[u].r].size;
	return u;
}
int query(int p,int q,int l,int r,int k)		//查詢[l,r]内第k大數
{
	if(l==r) return l;
	int mid=l+r>>1;
	int size=tr[tr[p].l].size-tr[tr[q].l].size;
	if(size>=k) return query(tr[p].l,tr[q].l,l,mid,k);
	else return query(tr[p].r,tr[q].r,mid+1,r,k-size);
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		num.push_back(a[i]);
	}
	sort(num.begin(),num.end());				//離散化
	num.erase(unique(num.begin(),num.end()),num.end());
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(num.begin(),num.end(),a[i])-num.begin();
	
	for(int i=1;i<=n;i++)						//建樹
		root[i]=insert(root[i-1],0,num.size()-1,a[i]);
	
	while(m--)
	{
		int l,r,k;
		scanf("%d %d %d",&l,&r,&k);
		printf("%d\n",num[query(root[r],root[l-1],0,num.size()-1,k)]);
	}
    return 0;
}