「bsoj3539」区间第k大问题 EXT - 主席树套主席树

题目大意

    给出向量$a=(a_1,a_2,a_3,\ldots,a_N)$，保证任意时刻$ai\in[0, 2^{31})\bigcap Z$，实现两个操作：
    $1)\,$将$a_i$重新赋值；
    $2)\,$第$t$次操作结束时，将$a_l\ldots a_r$中第$k$小的元素求出。

---

题目分析

陈立杰《可持久化数据结构研究》中的$6.4$区间第$K$大EXT原题。

如果不是在历史版本上询问，我们有树状数组套主席树的方法：用树状数组提取出每个主席树的根结点，并对提取的根结点对应的主席树进行操作。

因为在历史版本上询问，因此外层数据结构不能再采用树状数组，不妨使用主席树。

外层按照以时间作历史版本按坐标建主席树，内部建立权值线段树，顺便对修改可持久化。

对于修改操作，在外层主席树中定位找到修改点，并将其到根路径上的所有内层主席树全部修改该权值。
对于询问操作，在外层主席树中拆分询问区间，提取出所用到的内部主席树的根结点，并统一二分解决询问。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=50005;

struct Tree1 {
	int l,r,size;
};

struct President_Tree_in { //内部的权值线段树（顺便可持久化）
	Tree1 tree[maxn*750];
	int size=0;
	int insert(int Left,int Right,int pre,int v,int delta) {
		int now=++size;
		tree[now]=tree[pre];
		tree[now].size+=delta;
		if(Left==Right)return now;
		int mid=(Left+Right)>>1;
		if(v<=mid)tree[now].l=insert(Left,mid,tree[pre].l,v,delta);
		else tree[now].r=insert(mid+1,Right,tree[pre].r,v,delta);
		return now;
	}
} ptin;

struct Tree2 {
	int root,l,r;
};

int n,cnt,tot,q,a[maxn],b[maxn+10000],c[maxn+10000];

struct President_Tree_out { //外部的以时间作历史版本按坐标建主席树
	Tree2 tree[maxn*100];
	int size;
	int insert(int Left,int Right,int pre,int x,int delta) {
		int now=++size;
		tree[now]=tree[pre];
		tree[now].root=ptin.insert(1,tot,tree[now].root,a[x],delta);
		if(Left==Right)return now;
		int mid=(Left+Right)>>1;
		if(x<=mid)tree[now].l=insert(Left,mid,tree[pre].l,x,delta);
		else tree[now].r=insert(mid+1,Right,tree[pre].r,x,delta);
		return now;
	}
	vector<int>root;
	int find(int Left,int Right,int k) {
		if(Left==Right)return Left;
		int sum=0;
		for(int rt:root)sum+=ptin.tree[ptin.tree[rt].l].size;
		int mid=(Left+Right)>>1;
		if(k<=sum) {
			for(int& rt:root)rt=ptin.tree[rt].l;
			return find(Left,mid,k);
		} else {
			for(int& rt:root)rt=ptin.tree[rt].r;
			return find(mid+1,Right,k-sum);
		}
	}
	void interval(int now,int Left,int Right,int left,int right) {
		if(right<Left||left>Right)return;
		if(left<=Left&&right>=Right) {
			root.push_back(tree[now].root);
			return;
		}
		int mid=(Left+Right)>>1;
		interval(tree[now].l,Left,mid,left,right);
		interval(tree[now].r,mid+1,Right,left,right);
	}
	int query(int now,int left,int right,int k) {
		root.clear();
		interval(now,1,n,left,right);
		return find(1,tot,k);
	}
} pt;

map<int,int>M,fM;
int root[maxn];
int Discretization(int* a) {
	for(int i=1; i<=cnt; i++)M[a[i]]=1; 
	int i=1;
	for(auto it=M.begin(); it!=M.end(); it++,i++)it->second=i;
	for(int i=1; i<=cnt; i++)c[i]=M[a[i]],fM[c[i]]=a[i];
	return i;
}

struct Question {
	int opt,x,y,t,k;
} Q[maxn];

int main() {
	cnt=n=Get_Int();
	q=Get_Int();
	for(int i=1; i<=n; i++)a[i]=b[i]=Get_Int();
	for(int i=1; i<=q; i++) {
		char opt=' ';
		while(!isalpha(opt))opt=getchar();
		if(opt=='C') {
			Q[i].opt=1;
			Q[i].x=Get_Int();
			b[++cnt]=Q[i].y=Get_Int();
		} else {
			Q[i].opt=2;
			Q[i].t=Get_Int();
			Q[i].x=Get_Int();
			Q[i].y=Get_Int();
			Q[i].k=Get_Int();
		}
	}
	tot=Discretization(b);
	for(int i=1; i<=n; i++)a[i]=c[i];
	cnt=n;
	for(int i=1; i<=q; i++)
		if(Q[i].opt==1)Q[i].y=c[++cnt];
	for(int i=1; i<=n; i++)root[0]=pt.insert(1,n,root[0],i,1);
	for(int i=1; i<=q; i++) {
		root[i]=root[i-1];
		if(Q[i].opt==1) {
			int x=Q[i].x,y=Q[i].y;
			root[i]=pt.insert(1,n,root[i],x,-1);
			a[x]=y;
			root[i]=pt.insert(1,n,root[i],x,1);
		} else printf("%d\n",fM[pt.query(root[Q[i].t],Q[i].x,Q[i].y,Q[i].k)]);
	}
	return 0;
}