自动搬运

查看原文

来自洛谷，原作者为

	Miraik 看啊那只蝴蝶 飞过时间 落在心间

搬运于2025-08-24 22:44:26，当前版本为作者最后更新于2023-06-26 21:54:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先你发现归并的本质就是每轮选当前两段数中较小的那个数 $x$，然后在 $x$ 之后的一串 $<x$ 的数会被跟着选上。这启发我们按前缀最大值分段，每一段的第一个元素可以看作一个代表元。

再考虑一轮洗牌会对序列产生什么影响。容易发现，如果第 $\frac{n}{2}$ 和第 $\frac{n}{2}+1$ 个数不在一段那序列就不会再发生改变了，否则它会将这一段在它们中间分开得到新的段，再将后面的那些段向前归并。这也说明有效的洗牌轮数是 $<n$ 的。

那我们暴力维护这个过程每次需要的操作就是找到第 $k$ 个数的所在段，将一个段分裂，将一个段插入。

我们可以考虑用权值树状数组来维护这个过程，每个位置记录以 $i$ 为代表元的段长是多少，找第 $k$ 个数就树状数组二分，其他操作都是单点修改前缀求和。

总时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define lowbit(x) (x&(-x))
using namespace std;
const int N=200005;
const int M=1000005;
int n,Q,top,a[N],nxt[N],pos[N],stc[N],c[N],ans[M]; vector<pii>q[N];
inline void update(int x,int y){ while(x<=n) c[x]+=y,x+=lowbit(x); }
inline int query(int x){ int r=0; while(x) r+=c[x],x-=lowbit(x); return r; }
inline pii find(int x){
	int pos=0,sum=0;
	for(int i=17;~i;i--)
		if((pos|(1<<i))<=n&&sum+c[pos|(1<<i)]<x)
			sum+=c[pos|(1<<i)],pos|=1<<i;
	return mp(pos+1,x-sum);
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>Q;
	for(int i=1;i<=n;i++) cin>>a[i],pos[a[i]]=i; stc[0]=n+1;
	for(int i=n;i;i--){
		while(top&&a[i]>a[stc[top]]) top--;
		nxt[i]=stc[top]; stc[++top]=i;
	}
	for(int i=1;i<=n;i=nxt[i]) update(a[i],nxt[i]-i);
	for(int i=1,t,k;i<=Q;i++){
		cin>>t>>k; t=min(t,n);
		q[t].emplace_back(i,k);
	}
	for(int i=0;i<=n;i++){
		for(pii j:q[i]){
			pii o=find(j.second);
			ans[j.first]=a[pos[o.first]+o.second-1];
		}
		int mid=n/2+1; pii k=find(mid);
		if(k.second==1) continue;
		int len=query(k.first)-query(k.first-1);
		update(k.first,k.second-1-len);
		for(int j=pos[k.first]+k.second-1;j<=pos[k.first]+len-1;j=nxt[j])
			update(a[j],min(pos[k.first]+len,nxt[j])-j);
	}
	for(int i=1;i<=Q;i++) cout<<ans[i]<<'\n';
	return 0;
}