题解：P8996 [CEOI2022] Abracadabra

考虑每一次操作的本质是什么，其实就是一个单次归并的过程（这也是模拟赛题面）。

让我们来模拟一下这个过程。记当前左右手牌堆分别为 a 和 b 两个序列，那么当比较的两个数分别为 a_i 和 b_j 时就有这两种情况：

这一次操作结束之后将得到的答案序列在 \frac{n}{2} 的地方分成两半，准备进行下一次操作。

可以发现这样一个性质：对于单次操作，假设当前在 a 中取数，那么取的一段连续的数一定满足第一个数大于剩下后面的数。因为如果当前与 a 比较的 b 中的数大于了 a 中的第一个数，那么肯定也是大于这个数之后比它小的数的。

所以我们不妨将这个序列看成是一段一段的，满足一段中的第一个数是这一段的 \max，每次比较都可以直接操作一段序列，而且段内的数字之间位置相对不变。这样得到的答案序列一定满足每段的第一个数字单调递增。

但是注意到下一次操作会将整个序列分为两部分，而一个段可能刚好被 \frac{n}{2} 这个位置切开，这样就会断成若干段。具体的，我们对于位置 i 记 nxt_i 为下一个比 a_i 大的数的位置，假如说原来这一段为 [l,r]，满足 l\le\frac{n}{2}\le r，那么就会断成 [l,\frac{n}{2}],[\frac{n}{2}+1,nxt_{\frac{n}{2}+1}]\cdots。不难发现最多会这样切 O(n) 次。

考虑如何去维护分出来的这些段以及操作带来的段的修改。由于每次操作结束后的序列满足每段的第一个数字单调递增，所以考虑用第一个数字代表其所在段并记录该段长度，由于段内相对位置不变，所以说可以直接找到原序列中第一个数的位置去确定该段内其他数的位置。

而对于将序列分为两段的操作，需要找到那个 \frac{n}{2} 的位置，可以考虑二分。需要动态修改，可以二分，这时我们所需要的算法就出来了：将每段的第一个数作为下标，放到树状数组上，每个点记录这个点为段首该段的长度，直接树状数组上二分出这个需要修改的位置即可。

对于查询，考虑将询问离线按照 t 从小到大排序，特判 t=0 的时候直接输出原序列上的值，否则增加更新轮数直到到达 t 为止。不难发现，在操作最开始无法分出多的段时，这个序列就已经固定了，所以我们开个 flag 记录是否到了这样的状态，更新下去没有意义了。容易发现更新次数也是 O(n) 的。

一个注意点是，由于加入树状数组之后整个序列都是排好序的，所以说一开始分段加入树状数组就已经算是一次操作了。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5,M = 1e6+5;
inline int rd(){
    int x=0,y=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')y=-1;
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);return x*y;
}struct Day_Tao{int t,i,id;inline bool operator<(const Day_Tao&dt)const{return t<dt.t;}}q[M];
int r[N],s[N],tp,a[N],n,m,ans[M],b[N];bool fl=0;
// b 记录 a 的逆排列
struct BIT{
    int tr[N];inline void ad(int x,int v){for(;x<=n;x+=x&-x)tr[x]+=v;}
    inline int qu(int x){if(x==0)return 0;int y=0;for(;x;x-=x&-x)y+=tr[x];return y;}
    inline int qu_(int v){int x=0,y=0;for(int i=__lg(n)+1;~i;i--)
    if(x+(1<<i)<=n&&y+tr[x+(1<<i)]<v)x+=1<<i,y+=tr[x];return x+1;}// 树状数组上二分
}tr;
inline void upd(){
    int p=tr.qu_(n/2+1),x=tr.qu(p),y=tr.qu(p-1),z=x-y,t=b[p];
    // p 表示包含 n/2+1 这个位置的段的段首的值，x,y 分别表示恰好包含和恰好不包含 n/2+1 的位置
    // z 表示 n/2+1 位置所在段的长度
    if(y==n/2){fl=1;return;}tr.ad(p,-z),tr.ad(p,n/2-y); // 该段变化：[l,r]->[l,n/2]
    for(int i=t+n/2-y;i<=t+z-1;i=r[i]){if(i<=t+z-1)tr.ad(a[i],min(r[i],t+z)-i);}//更新新加入的段
}signed main(){
    n=rd(),m=rd();for(int i=1;i<=n;i++){
        a[i]=rd(),b[a[i]]=i;while(tp&&a[s[tp]]<a[i])r[s[tp--]]=i;s[++tp]=i;//r 即上文所说的 nxt
    }while(tp)r[s[tp--]]=n+1;for(int i=1;i<=m;i++)q[i]={rd(),rd(),i};
    for(int i=1;i<=n/2;i=r[i])tr.ad(a[i],min(r[i],n/2+1)-i);
    for(int i=n/2+1;i<=n;i=r[i])tr.ad(a[i],r[i]-i);sort(q+1,q+m+1); // 初始化第一轮
    q[0].t=1;for(int i=1;i<=m;i++){
        if(q[i].t==0){ans[q[i].id]=a[q[i].i],q[i].t=1;continue;} // 直接考虑从第一轮开始更新
        for(int j=q[i-1].t;j<q[i].t;j++){if(fl)break;upd();}
        int p=tr.qu_(q[i].i);ans[q[i].id]=a[b[p]+q[i].i-tr.qu(p-1)-1];
        // 即把要求的 i 在树状数组中所在段抠出来，根据段首在原序列的位置推出 i 在原序列的位置
    }for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0;
}