洛谷P3850/TJOI2007 书架

@Pelom  November 6, 2019

题意

给出一个序列,$2$种操作

  • 指定位置插入
  • 询问第$k$个

数据范围:$1 \le n \le 200,1 \le m \le 10^5,1 \le q \le 10^4$

题解

$\text{fhq-Treap}$,按排名分割

代码:

#include<iostream>
#include<cstdio>
using namespace std;
const int N=200+1e5+10;
const int L=10+5;
int n,m,q,a;
char c[N][L];
int rt,sz,x,y,z,cnt;
struct node{
    int val,rnd,siz,ch[2];
} T[N];
inline int rand(){
    static int seed=233;
    return seed=(int)seed*0x75d97LL%0x7fffffff;
}
inline int newNode(int v){
    T[++sz]=(node){v,rand(),1};
    return sz;
}
inline void pushUp(int u){
    T[u].siz=T[T[u].ch[0]].siz+T[T[u].ch[1]].siz+1;
}
void split(int u,int k,int& x,int& y){
    if(!u){
        x=y=0;
        return ;
    }
    if(k<=T[T[u].ch[0]].siz){
        y=u;
        split(T[u].ch[0],k,x,T[u].ch[0]);
    }
    else{
        x=u;
        split(T[u].ch[1],k-T[T[u].ch[0]].siz-1,T[u].ch[1],y);
    }
    pushUp(u);
}
int merge(int x,int y){
    if(!x || !y)
        return x|y;
    if(T[x].rnd<T[y].rnd){
        T[x].ch[1]=merge(T[x].ch[1],y);
        pushUp(x);
        return x;
    }
    else{
        T[y].ch[0]=merge(x,T[y].ch[0]);
        pushUp(y);
        return y;
    }
}
inline void insert(int k,int v){
    split(rt,k,x,y);
    rt=merge(merge(x,newNode(v)),y);
}
inline int kth(int k){
    split(rt,k,x,y);
    split(y,1,y,z);
    printf("%s\n",c[T[y].val]);
    rt=merge(merge(x,y),z);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",c[++cnt]);
        insert(i-1,cnt);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%s%d",c[++cnt],&a);
        insert(a,cnt);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%d",&a);
        kth(a);
    }
    return 0;
}

添加新评论