猫史档案馆

离线维护的整体分治算法是一类复杂分治，能够处理二维数据结构和可持久化线段树维护的一些信息，并且代码量相对而言较小，易于理解，是一个好的算法。

 

 

 

什么是离线算法

 

 

很多需要处理的信息可以抽象为两类操作。第一类操作是修改，第二类操作则是查询。

 

如果一些需要处理的信息中，所有的修改操作都在查询操作之后，或者只需要查询操作，则称这类问题为静态的。其余问题被称作动态的。

离线算法是指，将所有的操作统一写入之后，经过一系列计算，一次性回答所有的询问操作。

 

基于值域的整体分治算法就是一个能够动态维护信息的离线算法。

 

 

 

前置数据结构：树状数组

 

 

这里先略微介绍一下树状数组。

 

树状数组用于维护序列的前缀和，其基本思想为对区间结尾进行二进制分解，将区间划分为2次幂的长度的小区间。

分成的区间是 O (log x) 级别的，能够保证其时间复杂度。

我们可以使用 Lowbit(x) 运算进行快速划分。

 

树状数组查询前缀和

//树状数组查询前缀和
int ask(int x){
	int ans=0;
	for(;x;x-=x&-x)ans+=c[x];
	return ans;
}

 

树状数组单点修改

// 树状数组单点修改
void add(int x,int y){
	for (;x<=N;x+=x&-x)c[x]+=y;
}

 

 

 

基于值域的整体分治算法

 

 

这类离线分治算法对整个操作序列进行分治，使操作序列在保持时间顺序的基础上和值域一起被划分为独立的子问题，从而维护信息。

故称之为基于值域的整体分治算法，或曰整体分治。

 

 

K-th问题

 

动态区间Kth是一个经典问题。我们将其抽象为两类操作。

2 x y k 表示查询区间 [x,y] 内的第 k 小数。

1 x y 表示将位置为 x 的数修改为 y。

我们要求时间复杂度应在 O(m log n) 内解决。

 

 

基本思想

 

对于一操作 1，选取一个值 mid。我们如果能够快速求出 [x,y] 中 <=mid 的数的个数，记为 cnt，则我们就能够知道 Kth 在哪一个值域的范围内了。具体而言：

1. 若 cnt>=k，说明 <= mid 的数大于 k 个，因此 Kth 的值 <=mid；

2. 若 cnt<k，说明 <=mid 的数大于 k 个，因此 Kth 的值 >mid。

 

因此我们二分这个值域。

因此我们将操作序列按其操作的数的值，在二分的过程中分别放到两个子操作序列中，和值域一起二分。

 

 

算法流程

 

我们得到如下算法：

1. 对于一个修改操作，将其与值域的 mid 比较，如果其值 <=mid 则在原序列的位置上 +1，并放到子操作序列 lq 中。否则直接放到 rq 中。

2. 对于一个询问操作，我们获得在 [x,y] 中 <=mid 的个数 cnt，按照前述方法操作。

3. 对操作序列划分完成之后，用两个子序列去更新原操作序列，并还原树状数组。

4. 分治求解两个值域。

5. 分治的边界为 lval=rval，此时我们就得到了 [st,ed] 这一段操作的询问的结果。

 

其中我们需要支持单点修改、区间查值，这用前面提到的树状数组维护即可。

 

 

操作处理

 

我们将输入序列视作一次插入操作。

修改单点视作两次修改操作，一次为删除，一次为插入。

 

上述算法就是值域上整体分治的基本思想和一类解决流程。

 

struct rec{int op,x,y,z;}q[N],lq[N],rq[N];
int T,n,m,t,p,a[N],c[N],ans[N];
int ask(int x){
	int y=0;
	for(;x;x-=x&-x)y+=c[x];
	return y;
}
void change(int x,int y){
	for(;x<=n;x+=x&-x)c[x]+=y;
}
void solve(int lval,int rval,int st,int ed){
	if(st>ed)return;
	if(lval==rval){
		for(int i=st;i<=ed;i++)
			if(q[i].op>0)ans[q[i].op]=lval;
		return;
	}
	int mid=lval+rval>>1,lt=0,rt=0;
	for(int i=st;i<=ed;i++){
		if(q[i].op<=0){
			if(q[i].y<=mid)
				change(q[i].x,q[i].z),lq[++lt]=q[i];
			else rq[++rt]=q[i];
		}
		else{
			int cnt=ask(q[i].y)-ask(q[i].x-1);
			if(cnt>=q[i].z)lq[++lt]=q[i];
			else q[i].z-=cnt,rq[++rt]=q[i];
		}
	}
	for(int i=ed;i>=st;i--)
		if(q[i].op<=0&&q[i].y<=mid)
			change(q[i].x,-q[i].z);
	for(int i=1;i<=lt;i++)q[st+i-1]=lq[i];
	for(int i=1;i<=rt;i++)q[st+lt+i-1]=rq[i];
	solve(lval,mid,st,st+lt-1);
	solve(mid+1,rval,st+lt,ed);
}

//主函数中
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		int val=read();
		q[++t].op=0,q[t].x=i,q[t].y=val,
		q[i].z=1,a[i]=val;
	}
	for(int i=1;i<=m;i++){
		char op[5];scanf("%s",op);
		if(op[0]=='Q'){
			int l=read(),r=read(),k=read();
			q[++t].op=++p,q[t].x=l,q[t].y=r,q[t].z=k;
		}
		else{
			int x=read(),y=read();
			q[++t].op=-1,q[t].x=x,q[t].y=a[x],q[t].z=-1,
			q[++t].op=0,q[t].x=x,q[t].y=y,q[t].z=1,a[x]=y;
		}
	}
	solve(0,INF,1,t);

#include<bits/stdc++.h>
#define endl ('\n')
using namespace std;
const int maxn = 2 * 1e5 + 1e2;
int iiiii,root,n,m,a[maxn],u[maxn],size,t[maxn][2],key[maxn],siz[maxn];
void insert(int &u,int x){
	if(u == 0){
		u = ++size,key[u] = x,siz[u] = 1;
		return;
	}
	int d = (x > key[u]);
	insert(t[u][d],x);
	siz[u]++;
}
int find(int u,int k){
	int s = siz[t[u][0]];
	if(k < s) return find(t[u][0],k);
	if(k == s) return key[u];
	return find(t[u][1],k - s - 1);
}
int order(int u,int x){
	if(u == 0) return 0;
	if(x <= key[u]) return order(t[u][0],x);
	return siz[t[u][0]] + 1 + order(t[u][1],x);
}
int qq(int root,int x){
	return find(root,order(root,x) - 1);
}
int hj(int root,int x){
	return find(root,order(root,x + 1));
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	int now = 1;
	for(int i = 1;i <= m;i++){
		cin>>a[i];
	}
	for(int i = 1;i <= n;i++){
		cin>>u[i];
	}
	for(int i = 1;i <= m;i++){
		insert(root,a[i]);
		while(u[now] == i){
			now++;
			cout<<find(root,iiiii++)<<endl;
		}
	}
	return 0;
}