点名

splay treap 主席树

题目

可以去网盘里看。

点名

【题目描述】
在 J 班的体育课上,同学们常常会迟到几分钟,但体育老师的点名却一直很
准时。老师只关心同学的身高,他会一次询问当前最高的身高,次高的身高,第
三高的身高,等等。在询问的过程中,会不时地有人插进队伍里。你需要回答老
师每次的询问。
【输入格式】
第一行两个整数 n,m,表示先后有 n 个人进队,老师询问了 m 次
第二行 n 个整数,第 i 个数 Ai 表示第 i 个进入队伍的同学的身高为 Ai
第三行 m 个整数,第 j 个数 Bj 表示老师在第 Bj 个同学进入队伍后有一次询问
【输出格式】
M 行,每行一个整数,依次表示老师每次询问的答案。数据保证合法
【样例输入】
7 4
9 7 2 8 14 1 8
1 2 6 6
【样例输出】
9
9
7
8
【样例解释】
(9){No.1=9};(9 7){No.2=9};(9 7 2 8 14 1){No.3=7;No.4=8}
【数据范围】
40%的数据保证 n≤1000
100%的数据保证 1≤m≤n≤30000;0≤Ai<2 32

思路

数据结构题，由于数据范围很小。splay、treap、带修改主席树都可以做。
全当复习吧。。

代码

treap

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define maxn 300005
#define lc ch[x][0]
#define rc ch[x][1]
#define ll long long
using namespace std;
ll seq[maxn],ans[maxn],s[maxn];
int cnt,ch[maxn][2],size[maxn],fa[maxn],r[maxn];
struct que
{
    int v,id;
    bool operator<(que x)const
        {
            return v<x.v;
        }
}q[maxn];
void maintain(int x)
{
    size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
void rotate(int &x,int d)
{
    int t=ch[x][d^1];
    ch[x][d^1]=ch[t][d];
    ch[t][d]=x;
    maintain(x);maintain(t);
    x=t;
}
ll query(int x,int k)
{
    if(size[lc]+1==k)return s[x];
    else if(size[lc]>=k)return query(lc,k);
    else return query(rc,k-1-size[lc]);
}
void insert(int &x,ll v,int f)
{
    if(x==0){x=++cnt,s[x]=v,size[x]=1;fa[x]=f;r[x]=rand()%99999999+1;return;}
    else if(s[x]>=v){insert(lc,v,x);if(r[lc]<r[x])rotate(x,1);}
    else {insert(rc,v,x);if(r[rc]<r[x])rotate(x,0);}
    maintain(x);
}
int main()
{
    srand(time(NULL));
    //freopen("rollcall.in","r",stdin);
    //freopen("rollcall.out","w",stdout);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%lld",&seq[i]);
    for(int i=1;i<=m;i++)
        scanf("%d",&q[i].v),q[i].id=i;
    sort(q+1,q+1+m);int rt=1;
    int j=1;rt=++cnt;size[rt]=1;s[rt]=seq[1];
    for(int i=1;i<=m;i++)
    {
        while(j<q[i].v){j++;insert(rt,seq[j],0);}
        ans[q[i].id]=query(rt,q[i].id);
    }
    for(int i=1;i<=m;i++)
        printf("%lld\n",ans[i]);
    return 0;
}

splay

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define maxn 300005
#define lc ch[x][0]
#define rc ch[x][1]
#define ll long long
using namespace std;
ll seq[maxn],ans[maxn],s[maxn];
int cnt,ch[maxn][2],size[maxn],fa[maxn],r[maxn],rt,tar;
struct que
{
    int v,id;
    bool operator<(que x)const
        {
            return v<x.v;
        }
}q[maxn];
void maintain(int x)
{
    size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
void rotate(int &x)
{
    int y=fa[x];
    int z=fa[y];
    int k=ch[y][1]==x;
    ch[z][ch[z][1]==y]=x;
    fa[x]=z;
    ch[y][k]=ch[x][k^1];
    fa[ch[x][k^1]]=y;
    ch[x][k^1]=y;
    fa[y]=x;
    maintain(y);maintain(z);maintain(x);
}
ll query(int x,int k)
{
    if(size[lc]+1==k)return s[x];
    else if(size[lc]>=k)return query(lc,k);
    else return query(rc,k-1-size[lc]);
}
void splay(int x,int goal)
{
    while(fa[x]!=goal)
    {
        int y=fa[x],z=fa[y];
        if(z!=goal)
            (ch[z][0]==y)^(ch[y][0]==x)?rotate(x):rotate(y);
        rotate(x);
    }
    if(goal==0)rt=x;
}
void insert(int &x,ll v)
{
    if(x==0){x=++cnt,s[x]=v,size[x]=1;tar=x;return;}
    else if(s[x]>=v){insert(lc,v);fa[lc]=x;}
    else {insert(rc,v);fa[rc]=x;}
    maintain(x);
}
int main()
{
    srand(time(NULL));
    //freopen("rollcall.in","r",stdin);
    //freopen("rollcall.out","w",stdout);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%lld",&seq[i]);
    for(int i=1;i<=m;i++)
        scanf("%d",&q[i].v),q[i].id=i;
    sort(q+1,q+1+m);
    int j=1;rt=++cnt;size[rt]=1;s[rt]=seq[1];
    for(int i=1;i<=m;i++)
    {
        while(j<q[i].v){j++;insert(rt,seq[j]);splay(tar,rt);}
        ans[q[i].id]=query(rt,q[i].id);
    }
    for(int i=1;i<=m;i++)
        printf("%lld\n",ans[i]);
    return 0;
}