SS241115C. 排序（sort）

题意

给你一个长度为 \(n\) 的序列 \(a\)，每次操作对 \([1,\frac{n}{2}],[\frac{n}{2}+1,n]\) 进行归并排序。有 \(q\) 次询问，给出 \(t,x\)，问进行 \(t\) 次操作后 \(a_x\) 的值。

思路

考虑一次操作发生了什么。

假设 \(x<y\)，那么 \(x\) 和它后面的一坨都会排到 \(y\) 前面。

这启发我们把左右两个序列分成若干区间，满足每个区间的开头都比后面那一坨大，比下一个区间开头小。

把一个区间看做一个关于开头的整体，一次操作就是给这些区间排序，区间内部不变。

进行一次操作后，如果有一个块横跨了左右不分，就把这个块拆开，\(\le \frac{n}{2}\) 的为一部分，右边拆成若干块。

这个拆块的操作我们只会做 \(O(n)\) 次，因为拆完就不会合并回去了。

可以使用权值线段树维护。线段树下标表示开头的值，每次线段树二分找出横跨的块，如果没有那么排序就结束了，否则拆块，更新线段树。

因为拆块 \(O(n)\) 次，因此其实排序的操作最多也是 \(O(n)\) 次。

需要预处理每个位置后面第一个比它大的位置，这样才能保证拆一次块时间是 \(O(1)\) 的。

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

code

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace struggle {
	#define isdigit(x) (x>='0'&&x<='9')
	#define gc getchar_unlocked
	#define pc putchar_unlocked
	template <typename T>
	void read(T &x) {
		x=0;
		char ch=gc();
		for(;!isdigit(ch);ch=gc()) ;
		for(;isdigit(ch);ch=gc()) x=(x<<3)+(x<<1)+(ch^48);
	}
	template <typename T>
	void write(T x,char ch) {
		static int st[40];
		int top=0;
		do {
			st[top++]=x%10;
			x/=10;
		}while(x);
		while(top) pc(st[--top]^48);
		pc(ch);
	}
	constexpr int N=2e5+7,M=1e6+7;
	int n,q,t;
	int a[N];
	int c[N];
	int x;
	struct node {
		int id,t,x;
	}b[M];
	bool cmp (node a,node b) { return a.t < b.t; }
	int ne[N];
	int que[N],r;
	int _upper_bound(int x) {
		if(a[que[1]]<x) return n+1;
		int L=1,R=r;
		while(L<R) {
			int mid=(L+R+1)>>1;
			if(a[que[mid]]>x) L=mid;
			else R=mid-1;
		}
		return que[L];
	}
	int ans[M];
	struct segtree {
		int tr[N<<2];
		void pushup(int u) { tr[u]=tr[u<<1]+tr[u<<1|1]; }
		void insert(int u,int l,int r,int x,int w) {
			if(l==r) {
				return tr[u]+=w, void(0);
			}
			int mid=(l+r)>>1;
			if(x<=mid) insert(u<<1,l,mid,x,w);
			else insert(u<<1|1,mid+1,r,x,w);
			pushup(u);
		}
		bool chai(int u,int l,int r,int k) {
			if(l==r) {
				if(tr[u]==k) return 0;
				int len=tr[u]-k;
				tr[u]=k;
				int y=c[l]+k;
				while(len) {
					int p=min(len,ne[y]-y); 
					insert(1,1,n,a[y],p);
					len-=p;
					y+=p;
				}
				return 1;
			}
			int mid=(l+r)>>1;
			bool ans=0;
			if(tr[u<<1]>=k) ans=chai(u<<1,l,mid,k);
			else ans=chai(u<<1|1,mid+1,r,k-tr[u<<1]);
			pushup(u);
			return ans;
		}
		int query(int u,int l,int r,int x) {
			if(l==r) {
				int p=c[l]+x-1;
				return a[p];
			}
			int mid=(l+r)>>1;
			if(tr[u<<1]>=x) return query(u<<1,l,mid,x);
			return query(u<<1|1,mid+1,r,x-tr[u<<1]);
		}
	}T;
	void main() {
		read(n),read(q);
		rep(i,1,n) read(a[i]), c[a[i]]=i;
		rep(i,1,q) {
			read(t),read(x);
			b[i]={i,t-1,x};
		}
		sort(b+1,b+q+1,cmp);
		per(i,n,1) {
			ne[i]=_upper_bound(a[i]);
			while(r&&a[que[r]]<a[i]) --r;
			que[++r]=i;
		}
		int k=1;
		while(k<=(n>>1)) {
			int p=min(ne[k],(n>>1)+1);
			T.insert(1,1,n,a[k],p-k);
			k=p;
		}
		while(k<=n) {
			int p=ne[k];
			T.insert(1,1,n,a[k],p-k);
			k=p;
		}
		int cnt=0;
		int m=0;
		while(m<q&&b[m+1].t==-1) ++m, ans[b[m].id]=a[b[m].x];
		while(m<q&&b[m+1].t==0) ++m, ans[b[m].id]=T.query(1,1,n,b[m].x);
		while(m<q) {
			++cnt;
			if(!T.chai(1,1,n,n>>1)) {
				while(m<q) {
					++m;
					ans[b[m].id]=T.query(1,1,n,b[m].x);
				}
				break;
			}
			while(b[m+1].t==cnt) ++m, ans[b[m].id]=T.query(1,1,n,b[m].x);
		}
		rep(i,1,q) write(ans[i],'\n');
	}
}
int main() {
	#ifdef LOCAL
	freopen("my.out","w",stdout);
	#else 
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	#endif
	struggle :: main();
}