题解 | #小红的字符移动#

对题EF,这里提供一种根号平衡的算法,我们知道莫队的板子小Z的袜子上,是使用莫队维护区间每个数的数量,而我们又发现中位数,本质上是查询一个区间中第k位的值[k=(r-l+1)向上取整]。于是我们通过莫队已经可以得到每个区间的每个的数量，那么只要找到一个快速查询的方法即可。

那么此时问题就变成，如何在i~n的坐标索引中如何找到cnt的和,为(r-l+1)/2向上取整处的索引。我们发现，这个需求可以靠分块很好的实现[只需要掌握小z的袜子,和使用分块通过线段树1即可]。最后，我们分析复杂度，对于莫队而言，维护一个区间上的cnt[N]的单次的时间复杂度是sqrt(n)；而对于被维护好了的cnt数组，做分块查询的时间复杂度也是sqrt(n)。

这个操作便是根号平衡。即我们的分块查询操作，不会增加莫队的时间复杂度；同时莫队维护的cnt数组又可以作为切合当前区间的素材，给分块做查询。最后，不要忘记离散化，代码如下：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define AII array<int,3>
/*
根号平衡。
莫队维护每个区间状态下,每个数的数量,分块查询第k小。
*/
const int N=1e5+10;
int bsiz_mo,bcnt_mo,bel_mo[N];
int bsiz_fk,bcnt_fk,bel_fk[N],bl_fk[N],br_fk[N],cnt_fk[N],s_cnt_fk[N];
inline void init_fk(int n){
	bsiz_fk=sqrt(n);
	bcnt_fk=(bsiz_fk-1+n)/bsiz_fk;
	for(int b=1;b<=bcnt_fk;b++){
		bl_fk[b]=(b-1)*bsiz_fk,br_fk[b]=min(n,b*bsiz_fk);
		for(int s=bl_fk[b];s<=br_fk[b];s++) bel_fk[s]=b;
	}
}
inline void init_mo(int n){
	bsiz_mo=sqrt(n);
	bcnt_mo=(bsiz_mo-1+n)/bsiz_mo;
	for(int b=1;b<=bcnt_mo;b++){
		for(int s=(b-1)*bsiz_mo;s<=min(n,b*bsiz_mo);s++) bel_mo[s]=b;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,q;cin>>n>>q;
	init_mo(n);init_fk(N-5);
	int a[n+1],b[n+1],c[n+1];
	for(int i=1;i<=n;i++) {
		cin>>a[i];b[i]=a[i];
	}sort(b+1,b+n+1);
	int ln=unique(b+1,b+n+1)-(b+1);
	for(int i=1;i<=n;i++){
		c[i]=lower_bound(b+1,b+ln+1,a[i])-b;
	}vector<AII> ask(q+1);
	for(int i=1;i<=q;i++){
		auto &[l,r,j]=ask[i];
		cin>>l>>r;j=i;
	}sort(ask.begin()+1,ask.end(),[&](AII x,AII y){
		if(bel_mo[x[0]]^bel_mo[y[0]]) return bel_mo[x[0]]<bel_mo[y[0]];
		if(bel_mo[x[0]]%2==0) return bel_mo[x[1]]>bel_mo[y[1]];
		return bel_mo[x[1]]<bel_mo[y[1]];
	});vector<int> ans(q+1);
	auto add=[&](int id)->void{
		cnt_fk[c[id]]++;s_cnt_fk[bel_fk[c[id]]]++;
	};
	auto del=[&](int id)->void{
		cnt_fk[c[id]]--;s_cnt_fk[bel_fk[c[id]]]--;
	};
	auto qry=[&](int l,int r)->int{
		int k=(r-l+2)/2;
		for(int b=1;b<=bcnt_fk;b++){
			if(k>s_cnt_fk[b]) k-=s_cnt_fk[b];
			else{
				for(int s=bl_fk[b];s<=br_fk[b];s++){
					if(k>cnt_fk[s]) k-=cnt_fk[s];
					else return s;
				}
			}
		}return -1;
	};int tl=1,tr=0;
	for(int i=1;i<=q;i++){
		auto [l,r,j]=ask[i];
		while(tl>l) add(--tl);
		while(tr<r) add(++tr);
		while(tl<l) del(tl++);
		while(tr>r) del(tr--);
		ans[j]=b[qry(l,r)];
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<"\n";
	}
	return 0;
}

其实线段树合并也可以过,就是把主席树的合并拆在外面。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int INF=1e9;
#define ls(x) tre[x].ls
#define rs(x) tre[x].rs
#define cnt(x) tre[x].cnt
struct STR{
	int ls,rs,cnt;
}tre[N*40];
int idx,rt[N],a[N];
inline void pushup(int u){
	cnt(u)=cnt(ls(u))+cnt(rs(u));
}
inline void update(int &u,int tl,int tr,int id){
	if(!u) u=++idx;
	if(tl==tr){
		cnt(u)++;return;
	}int mid=(tl+tr)>>1;
	if(id<=mid) update(ls(u),tl,mid,id);
	else update(rs(u),mid+1,tr,id);
	pushup(u);
}
inline void merge(int &u,int v){
	if(u && v){
		cnt(u)+=cnt(v);
		merge(ls(u),ls(v));
		merge(rs(u),rs(v));
	}
	else u|=v;
}
inline int kth(int u,int v,int tl,int tr,int k){
	if(tl==tr) return k>cnt(u)-cnt(v) ? -1 : tl;
	int mid=(tl+tr)>>1;
	if(k<=cnt(ls(u))-cnt(ls(v))) return kth(ls(u),ls(v),tl,mid,k);
	return kth(rs(u),rs(v),mid+1,tr,k-cnt(ls(u))+cnt(ls(v)));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    int n,m;cin>>n>>m;int b[n+1];
    for(int i=1;i<=n;i++) cin>>a[i];
    
	for(int i=1;i<=n;i++) b[i]=a[i];
	sort(b+1,b+n+1);int ln=unique(b+1,b+n+1)-(b+1);
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(b+1,b+ln+1,a[i])-b;
	}
    for(int i=1;i<=n;i++){
    	update(rt[i],1,ln,a[i]);
    }
    for(int i=2;i<=n;i++){
    	merge(rt[i],rt[i-1]);
    }
    while(m--){
    	int l,r;cin>>l>>r;
    	int k=(r-l)/2+1;
    	int id=kth(rt[r],rt[l-1],1,ln,k);
    	cout<<b[id]<<"\n";
    }
    return 0;
}