專輯：主席樹（洛谷P3834）

文章目錄

• • 一個問題
  • 前言
  • 與可持久化線段樹的差別
  • 線段樹上第 k k k小
  • 深度的思考
  • 回到原題
  • 原題代碼

一個問題

點我

前言

我驚呆了！這竟然隻算一個“模闆” Q w Q QwQ QwQ（我太弱了？）。正常的主席樹模闆應該是求序列字首的第 k k k大（小）數，而不是區間的。是以我們進入這個題之前先看看主席樹正常怎麼做。

與可持久化線段樹的差別

請千萬不要把這兩個概念搞混了！雖然主席樹的名字是亂起的，但是它是“基于權值線段樹的可持久化線段樹”，而并不是純粹的可持久化線段樹。主席樹可以解決的問題都是關于求可持久化的排名（和平衡樹有些相似），但是可持久化線段樹僅僅做到了“可持久化”的要求。

線段樹上第 k k k小

回到主席樹，先想想求字首中的第 k k k小該如何去做。我們先想一想平衡樹求第 k k k大是如何做的。它其實就是一個二分查找樹，左邊都是更小的，右邊都是比它大的。設左子樹大小為 s i z l sizl sizl，如果 k < s i z l k<sizl k<sizl，那麼它就一定在左子樹，否則就是自己或右子樹的第 k − s i z l − 1 k-sizl-1 k−sizl−1小（别忘了去掉自己）。那我們嘗試把這個方法放線上段樹上。但是線段樹是按下标排序的，可我們需要按大小排序才能行。于是我們又引出一種線段樹：權值線段樹

權值線段樹十分特别，它的點存的是某個值域内有幾個數，是以它是有序的，于是我們就可以依葫蘆畫瓢，按平衡樹的方法來找第 k k k小了。

深度的思考

權值線段樹本來是用來找第 k k k小的，但是本題有一個很變态的要求：要求的是某個字首中的第 k k k小！我們可以思考一下，如果已經加到了第 i i i個數，那麼此時前 i i i個數都已經加到權值線段樹裡了，剛好就是我們要求的某一個字首！是以我們隻需要讓線段樹可持久化就行了。

先看一個問題：

洛谷P3949

我們知道，線段樹不是一個可持久化資料結構，但是這個題竟然要求我們通路之前的版本！

很容易想出一個方案：每次新開一個線段樹存儲。但是很明顯 M L E MLE MLE。

我們來畫個圖思考一下：

假如我們更改了結點 8 8 8後，不難發現隻有結點 8 , 4 , 2 , 1 8,4,2,1 8,4,2,1需要修改。是以我們修改之後隻需要建立這幾個結點就可以儲存新舊兩個版本了，其餘沒修改的地方直接向舊版本的結點連邊即可。

于是，每次修改隻需要新開 log ⁡ n \log n logn的結點，過掉這個題完全沒有問題。

回到原題

我們知道了主席樹怎麼做，現在就是解決這個問題：區間中的第 k k k小。首先，我們的主席樹可以得到字首的第 k k k小，然後要求的是某個區間，于是我們自然而然地想到了字首和數組是怎麼求某個區間的和的： s [ r ] − s [ l − 1 ] s[r]-s[l-1] s[r]−s[l−1]。于是我們直接用 r r r版本的線段樹減去 l − 1 l-1 l−1版本的線段樹的權值即可。但是如何把兩個線段樹放在一起處理呢？我們又引出一個模型：合并線段樹。

其實合并線段樹并不難，就是從兩個線段樹的根出發，一起往左合并一下，再一起往右合并一下。因為本題雖然是不同的線段樹，但是它們是同構的，是以不需要考慮某個地方隻有一個點的情況。注意，本題的 a a a很大，用權值當下标需要離散化或 m a p map map，但是 m a p map map常數太高，會 T L E TLE TLE。

原題代碼

#include<bits/stdc++.h>
using namespace std;
const int NN=2e5+4;
int a[NN],b[NN];
struct segtree
{
	int sum,lson,rson;
}tr[NN*20];
int idx,t[NN];
int build(int l,int r)
{
	int point=++idx;
	if(l==r)
		return idx;
	int mid=l+(r-l)/2;
	tr[point].lson=build(l,mid);
	tr[point].rson=build(mid+1,r);
	return point;
}
int update(int u,int l,int r,int id)
{
	int point=++idx;
	tr[point]=tr[u];
	if(l==r)
	{
		tr[point].sum++;
		return point;
	}
	int mid=l+(r-l)/2;
	if(id<=mid)
		tr[point].lson=update(tr[u].lson,l,mid,id);
	else
		tr[point].rson=update(tr[u].rson,mid+1,r,id);
	tr[point].sum=tr[tr[point].lson].sum+tr[tr[point].rson].sum;
	return point;
}
int query(int u,int v,int l,int r,int k)
{
	if(l==r)
		return l;
	int mid=l+(r-l)/2;
	if(tr[tr[v].lson].sum-tr[tr[u].lson].sum>=k)
		return query(tr[u].lson,tr[v].lson,l,mid,k);
	else
		return query(tr[u].rson,tr[v].rson,mid+1,r,k-tr[tr[v].lson].sum+tr[tr[u].lson].sum);
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	memcpy(b,a,sizeof(a));
	sort(b+1,b+1+n);
	int cnt=unique(b+1,b+1+n)-b-1;
	t[0]=build(1,cnt);
	for(int i=1;i<=n;i++)
		t[i]=update(t[i-1],1,cnt,lower_bound(b+1,b+1+cnt,a[i])-b);
	while(m--)
	{
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",b[query(t[l-1],t[r],1,cnt,k)]);
	}
	return 0;
}