对于一个排列 \(a[1...n]\) ，进行一趟冒泡排序的代码为：

for(inti=1;i<n;++i){
	if(a[i]>a[i+1])swap(a[i],a[i+1]);
}

在进行 \(n-1\) 趟冒泡排序之后，数组变为有序。

给一个长度为 \(n\) 的排列 \(a[1...n]\) 和 \(q\) 次询问，每次询问形如 \((k,x)\) ：代表询问这个数在趟排序之后的位置下标。

\(1\leq n,q\leq 5\times 10^5,\ 1\leq k<n,\ 1\leq x\leq n\)

保证 \(a[1...n]\) 是一个排列.

如果在 \(x\) 之前有数 \(y\) 大于 \(x\) ，那么必然 \(y\) 必然先后移过 \(x\) ，在 \(y\) 后移的时候 \(x\) 会往前进一位.

那么，记 \(cnt(i)\) 为在 \(i\) 前面大于 \(i\) 的数的个数 .

如果 \(cnt(x)\geq k\) ，那么，\(x\) 的位置就是 \(pos(x)-k\) .

否则，\(x\) 就会后移，那么，对于 \(cnt(y)\geq k\) 的数的位置是固定的 ，都是往前移动了 \(k\) 个位置，现在需要考虑 \(cnt(y)<k\) 的 . 单独拎出 \(cnt(y)<k\) 的数，发现他们必定是有序的 . 既然相对顺序固定，$cnt(y)\geq k $ 的位置固定，每个数的位置也固定了，从小到大依次填入空格中 .

可以考虑离线，用一个线段树维护那些 \(cnt(x)< k\) 的位置，查询时如果 \(cnt(x_0)<k\) ，可以预处理 \(x_0\) 在 \(cnt(x)<k\) 的 \(x\) 中的大小 \(i\) .然后在线段数上二分 .

维护起来细节还是蛮多的 .

时间复杂度 : \(O(q\log n+n\log n)\)

空间复杂度 : \(O(n)\)

code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	int res=0;
	while(ch>='0'&&ch<='9'){
		res=res*10+ch-'0';
		ch=getchar();
	}
	return res;
}
inline void print(int res){
	if(res==0){
		putchar('0');
		return;
	}
	int a[10],len=0;
	while(res>0){
		a[len++]=res%10;
		res/=10;
	}
	for(int i=len-1;i>=0;i--)
		putchar(a[i]+'0');
}
int n,q;
int a[500010],b[500010],cnt[500010];
vector<pair<int,int> >query[500010];
vector<int>v[500010];
int pos[500010];
int tree[1000010<<2];
void init(int x,int l,int r){
	if(l==r){
		tree[x]=0;
		return;
	}
	int mid=(l+r)>>1;
	init(x<<1,l,mid);
	init(x<<1|1,mid+1,r);
	tree[x]=0;
}
void upd(int x,int l,int r,int pos,int val){
	if(l==r){
		tree[x]+=val;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid)upd(x<<1,l,mid,pos,val);
	else upd(x<<1|1,mid+1,r,pos,val);
	tree[x]=tree[x<<1]+tree[x<<1|1];
}
int qry(int x,int l,int r,int cl,int cr){
	if(l==cl&&r==cr)return tree[x];
	int mid=(l+r)>>1;
	int sum=0;
	if(cl<=mid)sum+=qry(x<<1,l,mid,cl,min(cr,mid));
	if(mid+1<=cr)sum+=qry(x<<1|1,mid+1,r,max(cl,mid+1),cr);
	return sum;
}
pair<int,int>qry(int x,int l,int r,int cl,int cr,int val){
	if(l==cl&&r==cr){
		if(tree[x]<val)return make_pair(tree[x],-1);
		if(l==r)return make_pair(0,l);
		int mid=(l+r)>>1;
		if(tree[x<<1]>=val)return qry(x<<1,l,mid,cl,mid,val);
		else return qry(x<<1|1,mid+1,r,mid+1,cr,val-tree[x<<1]);
	}
	int mid=(l+r)>>1;
	int res=0;
	if(cl<=mid){
		pair<int,int>tmp=qry(x<<1,l,mid,cl,min(cr,mid),val);
		if(tmp.second!=-1)return tmp;
		res+=tmp.first;
	}
	if(mid+1<=cr){
		pair<int,int>tmp=qry(x<<1|1,mid+1,r,max(mid+1,cl),cr,val-res);
		if(tmp.second!=-1)return tmp;
		res+=tmp.first;
	}
	return make_pair(res,-1);
}
int ans[500010];
int main(){
	freopen("bubble.in","r",stdin);
	freopen("bubble.out","w",stdout);
	n=read();
	for(int i=0;i<n;i++)a[i]=read(),b[a[i]]=i;
	q=read();
	for(int i=0;i<q;i++){
		int k=read(),x=read();
		query[k-1].push_back(make_pair(x,i));
	}
	init(1,0,n-1);
	for(int i=0;i<n;i++){
		cnt[i]=qry(1,0,n-1,a[i],n-1);
		v[cnt[i]].push_back(i);
		upd(1,0,n-1,a[i]-1,1);
	}
	init(1,0,n-1);
	for(int i=0;i<(int)v[0].size();i++)upd(1,0,n-1,a[v[0][i]]-1,1);
	for(int i=0;i<n-1;i++){
		for(int j=0;j<(int)query[i].size();j++){
			int x=query[i][j].first,id=query[i][j].second;
			pos[id]=qry(1,0,n-1,0,x-1);
		}
		for(int j=0;j<v[i+1].size();j++){
			upd(1,0,n-1,a[v[i+1][j]]-1,1);
		}
	}
	init(1,0,2*n-1);
	for(int i=n;i<2*n;i++)upd(1,0,2*n-1,i,1);
	for(int i=0;i<(int)v[0].size();i++)upd(1,0,2*n-1,v[0][i],1);
	for(int i=0;i<n-1;i++){
		for(int j=0;j<(int)query[i].size();j++){
			int x=query[i][j].first,id=query[i][j].second;
			if(cnt[b[x]]>=i+1)ans[id]=b[x]-i-1;
			else{
				ans[id]=qry(1,0,2*n-1,i+1,2*n-1,pos[id]).second-i-1;
				if(ans[id]==-1)ans[id]=n-i-1;
			}
		}
		for(int j=0;j<(int)v[i+1].size();j++){
			int id=v[i+1][j];
			upd(1,0,2*n-1,id,1);
		}
	}
	for(int i=0;i<q;i++){
		print(ans[i]+1);
		putchar('\n');
	}
	return 0;
}
/*inline? ll or int? size? min max?*/
/*
5
4 3 5 1 2
3
2 1
4 4
1 5
*/
/*
5
4 5 2 3 1
5
3 1
4 2
3 3
2 4
1 5
*/