P8996 [CEOI2022] Abracadabra

Miraik · 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;
}