【洛谷P2617】Dynamic Rankings

题目

题目链接：https://www.luogu.com.cn/problem/P2617
给定一个含有 \(n\) 个数的序列 \(a_1,a_2 \dots a_n\)，需要支持两种操作：

• Q l r k 表示查询下标在区间 \([l,r]\) 中的第 \(k\) 小的数
• C x y 表示将 \(a_x\) 改为 \(y\)

思路

经典动态区间第 \(k\) 大问题。我们在做静态区间第 \(k\) 大的问题时，利用类似前缀和的思想求出一个区间值域位于 \([l,r]\) 的数字有多少个。然后为了节省空间将权值线段树“合并”为主席树。
在动态区间第 \(k\) 大的问题中，我们无法再用主席树的方法求前缀和，考虑用树状数组求前缀和，这样每次求 \(log n\) 棵线段树的和。
时间复杂度 \(O(n\log^2 n)\)，空间复杂度 \(O(n\log n)\)。

代码

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

const int N=200010,LG=20;
int n,m,tot,cnt1,cnt2,a[N],b[N],rt[N],q1[LG],q2[LG];
char ch;

struct Query
{
	int l,r,k,opt;
}ask[N];

struct SegTree
{
	int tot,lc[N*4*LG],rc[N*4*LG],size[N*4*LG];
	
	int update(int x,int l,int r,int k,int val)
	{
		if (!x) x=++tot;
		if (l==k && r==k)
		{
			size[x]+=val;
			return x;
		}
		int mid=(l+r)>>1;
		if (k<=mid) lc[x]=update(lc[x],l,mid,k,val);
			else rc[x]=update(rc[x],mid+1,r,k,val);
		size[x]=size[lc[x]]+size[rc[x]];
		return x;
	}
	
	int query(int l,int r,int k)
	{
		if (l==r) return l;
		int mid=(l+r)>>1,sum=0;
		for (int i=1;i<=cnt1;i++) sum-=size[lc[q1[i]]];
		for (int i=1;i<=cnt2;i++) sum+=size[lc[q2[i]]];
		if (sum<k)
		{
			for (int i=1;i<=cnt1;i++) q1[i]=rc[q1[i]];
			for (int i=1;i<=cnt2;i++) q2[i]=rc[q2[i]];
			return query(mid+1,r,k-sum);
		}
		else
		{
			for (int i=1;i<=cnt1;i++) q1[i]=lc[q1[i]];
			for (int i=1;i<=cnt2;i++) q2[i]=lc[q2[i]];
			return query(l,mid,k);
		}
	}
}seg;

void update(int x,int pos,int val)
{
	for (int i=pos;i<=tot;i+=i&-i)
		rt[i]=seg.update(rt[i],1,tot,x,val);
}

int query(int l,int r,int k)
{
	cnt1=cnt2=0;
	for (int i=l-1;i;i-=i&-i) q1[++cnt1]=rt[i];
	for (int i=r;i;i-=i&-i) q2[++cnt2]=rt[i];
	return seg.query(1,tot,k);
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[++tot]=a[i];
	}
	for (int i=1;i<=m;i++)
	{
		while (ch=getchar())
			if (ch=='C' || ch=='Q') break;
		if (ch=='Q')
		{
			scanf("%d%d%d",&ask[i].l,&ask[i].r,&ask[i].k);
			ask[i].opt=1;
		}
		else
		{
			scanf("%d%d",&ask[i].l,&ask[i].k);
			b[++tot]=ask[i].k;
			ask[i].opt=2;
		}
	}
	sort(b+1,b+1+tot);
	tot=unique(b+1,b+1+tot)-b-1;
	for (int i=1;i<=n;i++)
	{
		a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
		update(a[i],i,1);
	}
	for (int i=1;i<=m;i++)
		if (ask[i].opt==2) ask[i].k=lower_bound(b+1,b+1+tot,ask[i].k)-b;
	for (int i=1;i<=m;i++)
	{
		if (ask[i].opt==1)
			printf("%d\n",b[query(ask[i].l,ask[i].r,ask[i].k)]);
		else
		{
			update(a[ask[i].l],ask[i].l,-1); update(ask[i].k,ask[i].l,1);
			a[ask[i].l]=ask[i].k;
		}
	}
	return 0;
}