关于区间第 k 小问题的探讨

## 问题简述
给定一个数列，多次查询求区间第 $k$ 小数。（可加单点修改）

数据范围：$1\leq n,q\leq 10^5,|a_i|\leq 10^9$。

## 静态问题的解决

### 算法 1：莫队+平衡树
将询问离线后使用莫队算法，并使用平衡树维护当前区间内的数。该做法的时间复杂度是 $O(n\sqrt{q}\log n)$，可能需要精妙的卡常技巧才能通过。

### 算法 2：莫队+值域分块
同样使用莫队算法。考虑莫队算法的本质，实际上是一个有着 $O(n\sqrt{q})$ 级别的修改和 $O(q)$ 级别的查询的数据结构。因此，我们考虑找到一种快速修改，低速查询的数据结构。

在这样的要求下，一种简单的算法——分块就应运而生了。将序列离散化，我们可以在值域上进行分块。由于分块算法的修改复杂度为 $O(1)$，查询复杂度为 $O(\sqrt{n})$，因此我们使用莫队+值域分块，可以在 $O(n\sqrt{q}+q\sqrt{n})$ 的优秀时间复杂度内解决这个问题。

Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e4+10;
int n,m,block,a[N]; 
struct query
{
	int l,r,k,id;
	bool operator < (query b) const
	{
		if(l/block!=b.l/block)return l<b.l;
		if((l/block)&1)return r<b.r;
		return r>b.r;
	}
}q[M];
int ans[M];
vector<int>v;
int sz,L[N],R[N],pos[N],bcnt[N],cnt[N];
void add(int x){bcnt[pos[x]]++,cnt[x]++;}
void del(int x){bcnt[pos[x]]--,cnt[x]--;}
int query(int k)
{
	int i;
	for(i=1;i<=sz;i++)
		if(k>bcnt[i])k-=bcnt[i];
		else break;
	for(int j=L[i];j<=R[i];j++)
	{
		if(k>cnt[j])k-=cnt[j];
		else return j;
	}
	return -1;
}
unordered_map<int,int>mp;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=n;i++)
	{
		int t=a[i];
		a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
		mp[a[i]]=t;
	}
	int tot=v.size();
	sz=(int)sqrt(tot); 
	for(int i=1;i<=sz;i++)
		L[i]=(i-1)*sqrt(tot)+1,R[i]=i*sqrt(tot);
	if(R[sz]<n)sz++,L[sz]=R[sz-1]+1,R[sz]=n;
	for(int i=1;i<=sz;i++)
		for(int j=L[i];j<=R[i];j++)pos[j]=i;
	block=max(1,(int)(n/sqrt(m)));
	for(int i=1;i<=m;i++)scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k),q[i].id=i;
	sort(q+1,q+m+1);
	for(int i=1,l=1,r=0;i<=m;i++)
	{
		while(l>q[i].l)add(a[--l]);
		while(r<q[i].r)add(a[++r]);
		while(l<q[i].l)del(a[l++]);
		while(r>q[i].r)del(a[r--]);
		ans[q[i].id]=mp[query(q[i].k)];
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}
```
### 算法 3：基于值域的整体分治算法（整体二分）
设数列中最小的数为 $min_a$，最大的数为 $max_a$，我们尝试在值域 $[min_a,max_a]$ 上进行二分答案。

在二分的过程内部，扫描每个询问 $i=1\sim q$，并统计下标 $[l_i,r_i]$ 中 $\leq mid$ 的数有多少个，设为 $cnt_i$。这里的统计可以用树状数组来完成。

然后我们对询问进行分类：
1. 若 $k_i\leq cnt_i$，说明第 $i$ 个询问的答案在 $[min_a,mid]$ 中。
1. 若 $k_i>cnt_i$，说明第 $i$ 个询问的答案在 $(mid,max_a]$ 中，即在 $(mid,max_a]$ 中第 $k_i-cnt_i$ 小的数。

将序列中的数分为两部分：不大于 $mid$ 的数放入一个序列 $LA$，大于 $mid$ 的数放入另一个序列 $RA$。

这样，我们得到了一个分治算法：设 $solve(L,R,A,q)$ 表示值域为 $[L,R]$ 的序列 $A$ 对询问序列 $q$ 的回答。

于是，只要递归地执行 $solve(L,R,A,q)\to solve(L,mid,LA,Lq),solve(mid+1,R,RA,Rq)$ 即可。

时间复杂度为 $O((n+q)\log SIZE \log n)$，其中 $SIZE$ 是值域大小。

Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,SIZE=1e9;
int n,m,cnt,ans[N];
struct query
{
	int id,l,r,k;
}q[N<<1],lq[N<<1],rq[N<<1];
struct BIT
{
	int c[N];
	void add(int x,int y)
	{
		for(;x<=n;x+=x&(-x))c[x]+=y;
	}
	int ask(int x)
	{
		int res=0;
		for(;x;x-=x&(-x))res+=c[x];
		return res;
	}
}t;
void solve(int L,int R,int l,int r)
{
	if(l>r)return;
	if(L==R)
	{
		for(int i=l;i<=r;i++)if(q[i].id)ans[q[i].id]=L;
		return;
	}
	int mid=(L+R)>>1;
	int lt=0,rt=0;
	for(int i=l;i<=r;i++)
	{
		if(!q[i].id)
		{
			if(q[i].r<=mid)t.add(q[i].l,1),lq[++lt]=q[i];
			else rq[++rt]=q[i];
		}
		else
		{
			int tot=t.ask(q[i].r)-t.ask(q[i].l-1);
			if(tot>=q[i].k)lq[++lt]=q[i];
			else q[i].k-=tot,rq[++rt]=q[i];
		}
	}
	for(int i=r;i>=l;i--)
		if(!q[i].id&&q[i].r<=mid)t.add(q[i].l,-1);
	for(int i=1;i<=lt;i++)q[i+l-1]=lq[i];
	for(int i=1;i<=rt;i++)q[i+l+lt-1]=rq[i];
	solve(L,mid,l,l+lt-1);solve(mid+1,R,l+lt,r);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,v;i<=n;i++)
	{
		scanf("%d",&v);
		q[++cnt]=(query){0,i,v,0};
	}
	for(int i=1;i<=m;i++)
		++cnt,scanf("%d%d%d",&q[cnt].l,&q[cnt].r,&q[cnt].k),q[cnt].id=i;
	solve(-SIZE,SIZE,1,cnt);
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}
```
### 算法 4：可持久化线段树
离散化后在值域上建立可持久化线段树，记录序列中的数属于值域 $[l,r]$ 的下标。

此时，以 $root_i$ 为根的线段树的值域区间 $[L,R]$ 就保存了序列中的前 $i$ 个数有多少个落在 $[L,R]$ 内。

于是对于每个询问，同时从 $root_r$ 和 $root_{l-1}$ 出发，同步地在两棵线段树上进行查询即可。

该算法的时间复杂度为 $O((n+m)\log n)$。

Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,SIZE=1e9;
int n,m,a[N],rt[N];
struct SegmentTree
{
	int ls[N<<5],rs[N<<5],sum[N<<5];
	int sz;
	int build(int l,int r)
	{
		int p=++sz;sum[p]=0;
		if(l==r)return p;
		int mid=(l+r)>>1;
		ls[p]=build(l,mid),rs[p]=build(mid+1,r);
		return p;
	}
	int upd(int rt,int l,int r,int pos,int d)
	{
		int p=++sz;
		ls[p]=ls[rt],rs[p]=rs[rt],sum[p]=sum[rt];
		if(l==r){sum[p]+=d;return p;}
		int mid=(l+r)>>1;
		if(pos<=mid)ls[p]=upd(ls[rt],l,mid,pos,d);
		else rs[p]=upd(rs[rt],mid+1,r,pos,d);
		sum[p]=sum[ls[p]]+sum[rs[p]];
		return p;
	}
	int query(int p,int q,int L,int R,int k)
	{
		if(L==R)return L;
		int mid=(L+R)>>1;
		int lcnt=sum[ls[p]]-sum[ls[q]];
		if(k<=lcnt)return query(ls[p],ls[q],L,mid,k);
		return query(rs[p],rs[q],mid+1,R,k-lcnt);
	}
}segt;
int b[N],cnt;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[++cnt]=a[i];
	sort(b+1,b+cnt+1);
	int siz=unique(b+1,b+cnt+1)-(b+1);
	rt[0]=segt.build(1,siz);
	for(int i=1;i<=n;i++)
	{
		int x=lower_bound(b+1,b+siz+1,a[i])-b;
		rt[i]=segt.upd(rt[i-1],1,siz,x,1);
	}
	for(int i=1,l,r,k;i<=m;i++)
	{
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",b[segt.query(rt[r],rt[l-1],1,siz,k)]);
	}
	return 0;
}
```
### 算法 5：线段树套平衡树
在静态问题中使用该做法显得很蠢，我们留到动态问题中再进行讨论。

上述的几种算法在 [ACwing](https://www.acwing.com/problem/content/description/257/) 上的效率对比如下：

| 算法 | 莫队+值域分块 | 整体二分 | 可持久化线段树 |
| :----------: | :----------: | :----------: | :----------: |
| 时间 | $\text{1504ms}$ | $\text{1859ms}$ | $\text{1243ms}$ |
| 空间 | $\text{6892KB}$ | $\text{9568KB}$ | $\text{31452KB}$ |
| 码长 | $\text{1539}$ | $\text{1285}$ | $\text{1297}$ |

在洛谷的[模板题](https://www.luogu.com.cn/problem/P3834)上，三种算法的表现如下：
![算法表现](https://cdn.luogu.com.cn/upload/image_hosting/2wo5bxyq.png?x-oss-process=image/resize,m_lfit,h_170,w_225)

## 动态问题的解决
此时需要支持单点修改和区间查询第 $k$ 小。

### 算法 1：带修莫队+值域分块
只要把静态的普通莫队改成带修莫队即可。

块长设为 $n^{\frac{2}{3}}$，时间复杂度约为 $O(n^{\frac{5}{3}}+m\sqrt{n})$，空间复杂度为 $O(n+m)$。

Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10; 
int n,m,unit,a[N],aa[N];
int tot,maxn,v[N<<1];
int cntq,cntu;
struct query
{
	int l,r,k,t,id;
	bool operator < (query b) const
	{
		return l/unit==b.l/unit?r/unit==b.r/unit?t<b.t:r<b.r:l<b.l;
	}
}q[N];
struct update
{
	int x,y;
}u[N];
int pos[N<<1],cnt[N<<1],ans[N];
struct block//值域分块 
{
	int L[N<<1],R[N<<1],bcnt[N<<1],sz;
	void init()
	{
		sz=sqrt(maxn);
		for(int i=1;i<=sz;i++)
			L[i]=(i-1)*sqrt(maxn)+1,R[i]=i*sqrt(maxn);
		if(R[sz]<maxn)sz++,L[sz]=R[sz-1]+1,R[sz]=maxn;
		for(int i=1;i<=sz;i++)
			for(int j=L[i];j<=R[i];j++)pos[j]=i;
	}
	void add(int x){cnt[x]++,bcnt[pos[x]]++;}
	void del(int x){cnt[x]--,bcnt[pos[x]]--;}
	void upd(int i,int t)
	{
		if(q[i].l<=u[t].x&&u[t].x<=q[i].r)
			del(aa[u[t].x]),add(u[t].y);
		swap(aa[u[t].x],u[t].y);
	}
	int query(int k)
	{
		int i;
		for(i=1;i<=sz;i++)
			if(k>bcnt[i])k-=bcnt[i];
			else break;
		for(int j=L[i];j<=R[i];j++)
		{
			if(k>cnt[j])k-=cnt[j];
			else return j;
		}
		return -1;
	}
}B;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),v[++tot]=a[i];
	for(int i=1;i<=m;i++)
	{
		char str[5];
		scanf("%s",str);
		if(str[0]=='Q')
		{
			int l,r,k;
			scanf("%d%d%d",&l,&r,&k);
			++cntq,q[cntq]=(query){l,r,k,cntu,cntq};
		}
		else
		{
			int x,y;
			scanf("%d%d",&x,&y);
			++cntu,u[cntu]=(update){x,y};
			v[++tot]=y;
		}
	}
	unit=(int)pow(n,2.0/3.0);
	sort(v+1,v+tot+1);
	maxn=unique(v+1,v+tot+1)-(v+1);
	for(int i=1;i<=n;i++)aa[i]=lower_bound(v+1,v+maxn+1,a[i])-v;
	for(int i=1;i<=cntu;i++)u[i].y=lower_bound(v+1,v+maxn+1,u[i].y)-v;
	B.init();
	sort(q+1,q+cntq+1);
	for(int i=1,l=1,r=0,t=0;i<=cntq;i++)
	{
		while(l>q[i].l)B.add(aa[--l]);
		while(r<q[i].r)B.add(aa[++r]);
		while(l<q[i].l)B.del(aa[l++]);
		while(r>q[i].r)B.del(aa[r--]);
		while(t<q[i].t)B.upd(i,++t);
		while(t>q[i].t)B.upd(i,t--);
		ans[q[i].id]=v[B.query(q[i].k)];
	}
	for(int i=1;i<=cntq;i++)printf("%d\n",ans[i]);
	return 0;
}
```
### 算法 2：线段树套平衡树
将序列离散化后在值域上建立线段树。对于线段树的每个节点建立一棵平衡树保存序列中落在值域区间 $[L,R]$ 内的数的下标。

该算法的时间复杂度为 $O((n+m)\log^2n)$，空间复杂度为 $O(n\log n)$。
### 算法 3：整体二分
把修改分为 “去掉一个数” 和 “增加一个数” 两次操作。将这些所有的修改和初始的 $n$ 个数一起组成一个操作序列。随后在分治的过程中设法计算这一区间的操作对这一区间询问的影响即可。

该算法的时间复杂度为 $O((n+m)\log^2 n)$。

Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,maxn=1e9;
int n,m,a[N],tot,cntq,ans[N];
struct node
{
	int op,x,y,k,id;
}q[N<<2],lq[N<<2],rq[N<<2];
struct BIT
{
	int c[N];
	void add(int x,int y){for(;x<=n;x+=x&(-x))c[x]+=y;}
	int ask(int x)
	{
		int res=0;
		for(;x;x-=x&(-x))res+=c[x];
		return res;
	}
}t;
void solve(int L,int R,int l,int r)
{
	if(l>r||L>R)return;
	if(L==R)
	{
		for(int i=l;i<=r;i++)if(!q[i].op)ans[q[i].id]=L;
		return;
	}
	int mid=(L+R)>>1,lt=0,rt=0;
	for(int i=l;i<=r;i++)
	{
		if(q[i].op==1)
		{
			if(q[i].y<=mid)t.add(q[i].x,1),lq[++lt]=q[i];
			else rq[++rt]=q[i];
		}
		else if(q[i].op==-1)
		{
			if(q[i].y<=mid)t.add(q[i].x,-1),lq[++lt]=q[i];
			else rq[++rt]=q[i];
		}
		else
		{
			int num=t.ask(q[i].y)-t.ask(q[i].x-1);
			if(num>=q[i].k)lq[++lt]=q[i];
			else q[i].k-=num,rq[++rt]=q[i];
		}
	}
	for(int i=l;i<=r;i++)
		if(q[i].op==1&&q[i].y<=mid)t.add(q[i].x,-1);
		else if(q[i].op==-1&&q[i].y<=mid)t.add(q[i].x,1);
	for(int i=1;i<=lt;i++)q[i+l-1]=lq[i];
	for(int i=1;i<=rt;i++)q[i+l+lt-1]=rq[i];
	solve(L,mid,l,l+lt-1);solve(mid+1,R,l+lt,r);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),q[++tot]=(node){1,i,a[i],0,0};
	for(int i=1,x,y,k;i<=m;i++)
	{
		char str[5];
		scanf("%s",str);
		if(str[0]=='Q')
		{
			scanf("%d%d%d",&x,&y,&k);
			q[++tot]=(node){0,x,y,k,++cntq};
		}
		else
		{
			scanf("%d%d",&x,&y);
			q[++tot]=(node){-1,x,a[x],0,0};
			a[x]=y;
			q[++tot]=(node){1,x,a[x],0,0};
		}
	}
	solve(0,maxn,1,tot);
	for(int i=1;i<=cntq;i++)printf("%d\n",ans[i]);
	return 0;
}
```

### 算法 4：树状数组套可持久化线段树
由于需要支持修改，在可持久化线段树外套一个树状数组即可。但该算法空间复杂度较大，同时考虑到实现难度，对比上述三种算法也没有明显优势，不建议使用。

正在渲染内容...