本文共 4143 字，大约阅读时间需要 13 分钟。

题目

题目概要

• 询问一个区间的第 $k$ 小值。
• 修改一个数。
• 插入一个数。

数据范围与约定

• 原序列长度 $N\le 3.5\times 10^4$ 。
• 插入的数字个数$\le 3.5\times 10^4$ 。
• 修改操作与询问操作均不超过 $7\times 10^4$ 次。
• 数字大小总是一个不超过 $7\times 10^4$ 的自然数。

强制在线。

思路

解决区间第 $k$ 大靠什么？划分树。当然，也可以是权值线段树。

带修改怎么办？划分树中 $toL$ 数组用平衡树维护就行了。

划分树自身可能不平衡，套一个替罪羊即可（子树大小为 $x$ 时，一共有 $2x$ 个数字，不会让复杂度变劣）。

复杂度 $\mathcal{O}(n{\log }^{2}n)$ 。如果你比较懒（像我一样），就可以把外层改成权值线段树，复杂度 $\mathcal{O}(n\log n\log V)$ 。

代码

注意权值可以为零。

#include <cstdio>#include <iostream>#include <cstring>#include <cstdlib>using namespace std;# define rep(i,a,b) for(int i=(a); i<=(b); ++i)inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}namespace Treap{   	const int MaxN = 5000005;	int son[MaxN][2], siz[MaxN];	int val[MaxN], data[MaxN];	int cntNode, prio[MaxN];	inline int newNode(int v){   		int &id = ++ cntNode;		son[id][0] = son[id][1] = 0;		data[id] = val[id] = v;		prio[id] = (rand()<<16)|rand();		siz[id] = 1; return id;	}	void pushUp(int o){   		val[o] = val[son[o][0]]+			val[son[o][1]]+data[o];		siz[o] = siz[son[o][0]]+			siz[son[o][1]]+1;	}	struct PII{   		int first, second; PII(){    }		PII(int F,int S){   			first = F, second = S;		}		int& operator[](const int &x){   			return x ? second : first;		}	};	PII split(int o,int k){   		PII p; if(!o) return PII(o,o);		if(k <= siz[son[o][0]]){   			p = split(son[o][0],k);			son[o][0] = p[1], p[1] = o;		}		else{   			k -= siz[son[o][0]];			p = split(son[o][1],k-1);			son[o][1] = p[0], p[0] = o;		}		pushUp(o); return p;	}	int merge(int a,int b){   		if(!a || !b) return a^b;		if(prio[a] > prio[b]){   			son[a][1] = merge(son[a][1],b);			pushUp(a); return a;		}		else{   			son[b][0] = merge(a,son[b][0]);			pushUp(b); return b;		}	}}using namespace Treap;struct treap{   	int rt; treap(){    rt = 0; }	/* insert x after k-th element */	void insert(int k,int x){   		PII p = split(rt,k);		p[0] = merge(p[0],newNode(x));		rt = merge(p[0],p[1]);	}	/* erase k-th element */	void erase(int k){   		PII pl = split(rt,k-1);		rt = merge(pl[0],split(pl[1],1).second);	}	int find(int k){   		PII pl = split(rt,k-1);		PII pr = split(pl[1],1);		int res = data[pr[0]];		rt = merge(pl[0],merge(pr[0],pr[1]));		return res;	}	int query(int k){   		PII p = split(rt,k);		int res = val[p[0]];		rt = merge(p[0],p[1]);		return res;	}};const int MaxM = 70005;namespace SgTree{   	treap tre[MaxM<<1|1];	# define __index(l,r) (((l)+(r))|1)	/* insert v after x-th element */	void insert(int x,int v,int l=0,int r=MaxM){   		if(l == r) return ; // leaf		int id = __index(l,r);		int p = tre[id].query(x);		if(v <= ((l+r)>>1)){   			insert(p,v,l,(l+r)>>1);			tre[id].insert(x,1);		}		else{   			insert(x-p,v,(l+r)/2+1,r);			tre[id].insert(x,0);		}	}	/* erase x-th element whose value = v */	void erase(int x,int v,int l=0,int r=MaxM){   		if(l == r) return ;		int id = __index(l,r);		int p = tre[id].query(x-1);		if(v <= ((l+r)>>1))			erase(p+1,v,l,(l+r)>>1);		else erase(x-p,v,(l+r)/2+1,r);		tre[id].erase(x); // always do it	}	/* k-th smallest element in range [ql,qr] */	int query(int ql,int qr,int k,int l=0,int r=MaxM){   		if(l == r) return l;		int id = __index(l,r);		int pl = tre[id].query(ql-1);		int pr = tre[id].query(qr);		if(pr-pl >= k) // in left part			return query(pl+1,pr,k,l,(l+r)>>1);		k -= (pr-pl); pl = ql-pl; pr = qr-pr;		return query(pl,pr,k,(l+r)/2+1,r);	}	# undef __index}treap ori; char opt[10];int main(){   	srand(5201314);	int n = readint();	for(int i=0,v; i<n; ++i){   		v = readint();		ori.insert(i,v);		SgTree::insert(i,v);	}	int q = readint();	for(int x,y,ans=0; q; --q){   		scanf("%s",opt);		x = readint()^ans;		y = readint()^ans;		if(*opt == 'I'){   			SgTree::insert(x-1,y);			ori.insert(x-1,y);		}		if(*opt == 'M'){   			SgTree::erase(x,ori.find(x));			SgTree::insert(x-1,y);			ori.erase(x); ori.insert(x-1,y);		}		if(*opt == 'Q'){   			ans = SgTree::query(x,y,readint()^ans);			printf("%d\n",ans);		}	}	return 0;}