P8996 [CEOI2022] Abracadabra Solution

流水行船CCD · 2024-01-22 21:09:26 · 题解

fhq-treap 好闪，拜谢 fhq-treap。

题解有了权值线段树和树状数组，写发平衡树算是补齐了。

思路1

考场思路，直接模拟，期望 O(n^2)。但是加入了启发式优化后实测可以跑到只有少数点超时，但是通过不了。

记录

思路2

引理零：最多洗 \min\{n,\max\{t_i\}\} 次牌。

证明：每次至少交换两个牌的相对位置，之后一定会被卡死或是有序。

洗牌次数不是瓶颈，考虑加速洗牌。

引理一：一个值只会跟着它的前缀最大值走，不会发生相对移动。所以可以把序列看成一个个块，而且这些块的前缀最大值成升序排列。

证明：因为如果 x 的前缀最大值 q 被一个更大的值 p 扔到牌堆当中，即 x<q<p 那么 x 肯定也会被 p 扔到牌堆中，而如果 x<q>p 则 x 根本就不会与 p 比较，仍会在前缀最大值后。

此时，看到下标和前缀最大值都是有序的，而且不是偏序，元素之间有相对顺序，可以考虑用同一棵平衡树维护相对顺序。然后就过了连样例都过不了。

观察样例，发现块与块的相对顺序并不是一成不变的。

引理二：只有跨越 \frac{n}{2} 的块会修改。

证明：跨越 \frac{n}{2} 的块会被强制切割成两部分，前一部分前缀最大值不变，后一部分会失去原有的前缀最大值，从而分裂成多个新的块，每一个新块都有独立的最大值，其他块依然是完整的。

如果没有块跨越中轴线，不用更改。

发现切割块的过程就是反复去找到最大值，然后把最大值 x 以及以后的部分全部切割出来，前缀最大值改为 x，这里可以使用懒标记修改前缀最大值的值，然后插入到前半部分平衡树合适的地方,这里可以把相同前缀最大值的块看作一个点，平衡树看作这些点构成的按权值排序的平衡树，在这里进行插入操作。

可见时间复杂度只和块的个数 D 相关，而 D \le n，整体时间复杂度可以接受。

提醒：注意平衡树实现时的常数。

其余的看注释理解吧。

AC Code

#include<bits/stdc++.h>

#define in inline
#define re register
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define pb emplace_back
#define sort stable_sort
#define REP(i,l,r) for(register int i=l;i<=r;++i)
#define PER(i,r,l) for(register int i=r;i>=l;--i)

using namespace std;

random_device R;    
mt19937 G(R());
inline int rd(int l,int r){return uniform_int_distribution<int>(l,r)(G);}

const int inf=1e9+7;
const ll INF=1e18+7;

char buf[1<<19],*p1=buf,*p2=buf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<19,stdin),p1==p2)?EOF:*p1++)
static inline int read() {
    register int x=0,w=1;
    register char ch=gc();
    while((ch<48||ch>57)&&ch!='-') ch=gc();
    if(ch=='-')w=-1,ch=gc();
    while(ch>=48&&ch<=57) x=(x<<3)+(x<<1)+(ch^48),ch=gc();
    return x*w;
}
static inline char readc(){
    register char ch=gc();
    while(isspace(ch))ch=gc();
    return ch;
}

namespace Code{
    const int N=2e5+7; 
    const int Q=1e6+7;
    int n,q;
    int arr[N],pri[N],pmax[N];
    int Ans[Q];
    struct lyt{int t,ith,id;}In[Q];
    bool cmp(lyt a,lyt b){return a.t<b.t;}

    struct box{
        int son[2];
        int pri;//随机堆权值
        int sz,val,pmax;//子树大小，当前点权值，前缀最大值
        int ma,maid;//最大值，最大值原序列编号
        int id,tg;//当前值原序列编号，覆盖前缀最大值的标记
        box(){son[0]=son[1]=pri=sz=val=pmax=id=ma=maid=tg=0;}
    }tr[N];
    int rt=0,trc=0;
#define ls tr[x].son[0]
#define rs tr[x].son[1]
    inline void pu(int x){//更新最大值和最大值编号
        tr[x].sz=tr[ls].sz+tr[rs].sz+1;
        tr[x].ma=std::max(tr[x].val,std::max(tr[ls].ma,tr[rs].ma));
        if(tr[x].ma==tr[x].val)     tr[x].maid=tr[x].id;
        else if(tr[x].ma==tr[ls].ma)tr[x].maid=tr[ls].maid;
        else if(tr[x].ma==tr[rs].ma)tr[x].maid=tr[rs].maid;
    }
    inline void pd(int x){
        if(tr[x].tg){//更新前缀最大值
            tr[ls].pmax=tr[x].tg,tr[rs].pmax=tr[x].tg;
            tr[ls].tg=tr[rs].tg=tr[x].tg;
            tr[x].tg=0;
        }
    }
    void splitsz(int x,int &l,int &r,int key){//按相对排名分裂
        if(!x){l=r=0;return;}
        if(tr[ls].sz+1<=key){l=x,pd(x),splitsz(rs,tr[l].son[1],r,key-tr[ls].sz-1),pu(x);}
        else                {r=x,pd(x),splitsz(ls,l,tr[r].son[0],key),pu(x);}
    }
    void splitpm(int x,int &l,int &r,int key){//按前缀最大值分裂
        if(!x){l=r=0;return;}
        if(tr[x].pmax<=key){l=x,pd(x),splitpm(rs,tr[l].son[1],r,key),pu(x);}
        else               {r=x,pd(x),splitpm(ls,l,tr[r].son[0],key),pu(x);}
    }
    void merge(int &x,int l,int r){
        if(!l||!r){x=l|r;return;}
        if(tr[l].pri<tr[r].pri){x=l,pd(x),merge(rs,tr[l].son[1],r),pu(x);}
        else                   {x=r,pd(x),merge(ls,l,tr[r].son[0]),pu(x);}
    }
    int Build(int l,int r){//建树
        if(l>r)return 0;
        int node=++trc,mid=(l+r)>>1;
        tr[node]=box();
        tr[node].id=mid;
        tr[node].pri=pri[node];
        tr[node].val=arr[mid],tr[node].pmax=pmax[mid],tr[node].sz=1;
        tr[node].son[0]=Build(l,mid-1);
        tr[node].son[1]=Build(mid+1,r);
        pu(node);return node;
    }
    int now=0;
    int ask_kth(int x,int key){//递归找 k 大值
        pd(x);
//      cout<<x<<' '<<key<<"ASK\n";
        if(tr[ls].sz>=key)       return ask_kth(ls,key);
        else if(tr[ls].sz+1>=key)return x;
        else                     return ask_kth(rs,key-tr[ls].sz-1);
    }
    void Wash(){//一次洗牌
        int lr=ask_kth(rt,(n>>1)),rl=ask_kth(rt,(n>>1)+1),rr=ask_kth(rt,n);
        if(tr[lr].pmax!=tr[rl].pmax)return;//没有块被切开
        int ma,maid;
        int ltr=0,rtr=0,fhq=0,node=0;
        splitsz(rt,ltr,rtr,(n>>1));//沿中轴线切割块
        splitpm(rtr,rtr,fhq,tr[rl].pmax);//切割出要改变的块rtr
        int L=tr[rl].id,R=tr[rl].id+tr[rtr].sz-1;
        do{
            maid=tr[rtr].maid,ma=tr[rtr].ma;//块中最大值编号，值
            splitsz(rtr,rtr,node,maid-L);//块中新的最大值作为前缀最大值的块
            tr[node].tg=ma,tr[node].pmax=ma;//更新前缀最大值
            int ltrl=0,ltrr=0;
            splitpm(ltr,ltrl,ltrr,tr[node].pmax);
            merge(ltrl,ltrl,node),merge(ltr,ltrl,ltrr);//把新块按照前缀最大值中序遍历插入到前半部分
            R=maid-1;
        }while(maid!=L);
        merge(rtr,rtr,fhq);
        merge(rt,ltr,rtr);//合并回去
    }
    int solve(int ti,int kth){
        ti=std::min(ti,n);//最多洗 n 次牌
//      cout<<ti<<" "<<kth<<"Solve:\n";
        while(now!=ti)Wash(),++now; //模拟洗牌
//      cout<<"SOVLE:"<<ask_kth(rt,kth)<<' '<<tr[ask_kth(rt,kth)].val<<'\n';
        return tr[ask_kth(rt,kth)].val;//此时平衡树的中序遍历就是牌堆
    }
    signed main(){
        n=read(),q=read();
        REP(i,1,n)arr[i]=read(),
        pmax[i]=std::max(pmax[i-1],arr[i]),
        pri[i]=rd(pri[i-1],10000*i);
        rt=Build(1,n);
//      Treer("YU",rt);
        REP(i,1,q)In[i].t=read(),
        In[i].ith=read(),
        In[i].id=i;
        stable_sort(In+1,In+q+1,cmp);
        REP(i,1,q){Ans[In[i].id]=solve(In[i].t,In[i].ith);}//离线处理询问
        REP(i,1,q)cout<<Ans[i]<<'\n';
        return 0;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    Code::main();
    return 0;
}