P8996 题解

P8996

思路

当有 \(a_i<a_j\) 时，先放 \(a_i\)，再放 \(i\) 之后连续的 \(a_k<a_i\)。设 \(i\) 后第一个比 \(a_i\) 大的位置是 \(nxt_i\)，对于一个前缀最大值位置 \(i\)，合并后 \([i,nxt_i)\) 的顺序不变且依然连续。让前缀最大值 \(a_l\) 代表整个区间，可以看做合并是将两个序列的前缀最大值排序。

每次合并相当于在 \(\frac{n}{2}\) 处断开跨过序列中点的区间 \([l,r]\)，生成 \([l,\frac{n}{2}]\) 和 \([\frac{n}{2}+1,nxt_{\frac{n}{2}+1}-1],[nxt_{\frac{n}{2}+1},nxt_{nxt_{\frac{n}{2}+1}}-1],\dotsb,[pos,r]\)，然后再重新按区间左端点的值排序。每个区间不会扩大，只会被分割；每次操作如果没有区间跨过序列中点就不会再操作，否则区间数量至少加 \(1\)。所以最多操作 \(n\) 次，最多 \(n\) 种区间。

将询问离线，维护每次合并后的区间信息。建权值线段树表示前缀最大值 \(l\) 代表的区间长度之和。询问时线段树上二分出包含 \(p\) 的区间的最大值和 \(p\) 在区间中的位置，对应回初始时最大值的位置加 \(p\) 在区间中的位置得到 \(p\) 初始时的位置。进行合并操作时二分出包含 \(\frac{n}{2}\) 的区间的最大值 \(l\)，将这个区间 \([l,l+len_l-1]\) 断开为 \([l,\frac{n}{2}]\)。从 \(\frac{n}{2}+1\) 开始不断跳 \(nxt_i\)，形成新的区间加入权值线段树。

复杂度 \(O(n\log n+q\log n)\)。

code

int n,q,a[maxn];
#define mid (l+r>>1)
#define ls nd<<1
#define rs nd<<1|1
int tree[maxn<<2];
void updata(int nd,int l,int r,int p,int w){
	if(l==r){tree[nd]=w;return ;}
	if(p<=mid)updata(ls,l,mid,p,w);
	else updata(rs,mid+1,r,p,w);
	tree[nd]=tree[ls]+tree[rs];
}
pii query(int nd,int l,int r,int w){
	if(l==r){return {l,w};}
	if(tree[ls]>=w)return query(ls,l,mid,w);
	else return query(rs,mid+1,r,w-tree[ls]);
}
vector<pii> que[maxn];int ans[maxn*5];
int st[maxn],tp,nxt[maxn],len[maxn],pos[maxn];
void work(){
	n=read();q=read();
	for(int i=1;i<=n;i++)a[i]=read(),pos[a[i]]=i;
	a[n+1]=n+1;st[++tp]=n+1;
	for(int i=n;i;i--){
		while(a[st[tp]]<a[i])tp--;st[++tp]=i;
		nxt[i]=st[tp-1];
	}
	for(int i=1;i<=n/2;i=nxt[i]){
		len[i]=min(n/2,nxt[i]-1)-i+1;
		updata(1,1,n,a[i],len[i]);
	}
	for(int i=n/2+1;i<=n;i=nxt[i]){
		len[i]=nxt[i]-1-i+1;
		updata(1,1,n,a[i],len[i]);
	}
	for(int i=1;i<=q;i++){
		int t=read(),d=read();
		if(!t)ans[i]=a[d];
		else que[min(t,n)].push_back({i,d});
	}
	for(int t=1;t<=n;t++){
		for(auto[id,d]:que[t]){
			pii p=query(1,1,n,d);
			// cout<<p.fi<<" "<<p.se<<"\n";
			ans[id]=a[pos[p.fi]+p.se-1];
		}
		pii p=query(1,1,n,n/2);
		int lst=pos[p.fi],r=lst+len[lst]-1,x=lst+p.se;
		len[lst]=p.se;updata(1,1,n,p.fi,p.se);
		while(x<=r){
			len[x]=min(r,nxt[x]-1)-x+1;updata(1,1,n,a[x],len[x]);
			x=nxt[x];
		}
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
}