NOIP-EMU-141102-rollcall 点名

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>

using namespace std;
typedef long long lli;
const int maxn = 40010;
const lli infinit = 0x007f7f7f7f7f7f7fll;

/*
class SplayTree
{
public:
    int parent[maxn], ch[maxn][2], root, ncnt, n;
    int size[maxn];
    lli val[maxn];
    #define lc(_x) ch[_x][0]
    #define rc(_x) ch[_x][1]
    #define par(_x) parent[_x]
    int makenode(int q, lli v) {
        int p = ++ncnt; n++;
        lc(p) = rc(p) = 0;
        par(p) = q;
        size[p] = 1;
        val[p] = v;
        return p; }
    void rotate(int p) {
        int q = par(p), g = par(q), x = p == rc(q);
        // Relink connections
        ch[q][x] = ch[p][!x]; if (ch[q][x]) par(ch[q][x]) = q;
        ch[p][!x] = q, par(q) = p;
        par(p) = g; if (g) ch[g][rc(g) == q] = p;
        size[q] = size[lc(q)] + 1 + size[rc(q)];
        size[p] = size[lc(p)] + 1 + size[rc(p)];
        return ; }
    void splay(int p, int t) {
        for (int q = 0; (q = par(p)) && q != t; rotate(p))
            if (par(q) && par(q) != t)
                rotate((p == lc(q)) == (q == lc(par(q))) ? q : p);
        if (t == 0) root = p; }
    int pre(int p) {
        cout << "preing " << p << endl;
        if (!lc(p)) { while (p == lc(par(p))) p = par(p); p = par(p); }
        if  { p = lc(p); while (rc(p)) p = rc(p); }
        return p; }
    int find(int x) {
        int p = root;
        while (true) {
            if (size[lc(p)] >= x) {
                p = lc(p); continue;
            } x -= size[lc(p)];
            if (x == 1) return p; x -= 1;
            p = rc(p);
        } return root; }
    int locate(lli v) {
        int p = root;
        while (true) {
            if (v > val[p] && rc(p)) {
                p = rc(p); continue; }
            if (v == val[p]) return p;
            if (lc(p)) p = lc(p); else return p;
        } return root; }
    lli query(int x) {
        int m = n - 1 - x;
        return val[find(m + 1)]; }
    void dfs(int p)
    {
        if (!p) return ;
        printf("%d %d %d\n", par(p), p, p==rc(par(p)));
        dfs(lc(p));
        dfs(rc(p));
    }
    void dfstree(void)
    {
        dfs(root);
    }
    void insert(lli v) {
        int rp = locate(v), lp = pre(lp);
        cout << rp << ' ' << lp << "*\n";
        splay(rp, 0);
        splay(lp, root);
        int c = makenode(lp, v);
        rc(lp) = c;
        size[lp]++, size[rp]++;
        dfstree();
        return ; }
    void build_tree(void) {
        n = ncnt = 0;
        root = makenode(0, 0);
        rc(root) = makenode(root, infinit);
        par(rc(root)) = root;
        size[root]++; }
} st; */

#define $ if(0)

class XmcpsSplayTree
{
public:
    static const int _N=50007, _I=2147000000;
    int child[_N][2], parent[_N], size[_N];
    lli value[_N];
    int root, graphtop;
    int query[_N];
    int insvalue[_N];
    bool inserted;

    void build_tree(void) {
        root = 1, graphtop = 2;
        inserted = false;
    }
    int flag(int x) {
        return x[parent][child][1]==x;
    }
    void rotate(int self) {
        int flaj=flag(self),
            p=self[parent],
            pp=p[parent],
            ch=self[child][!flaj];
        /****/ self[parent]=pp;
        if(pp) pp[child][flag(p)]=self;
        /****/ p[parent]=self;
        /****/ self[child][!flaj]=p;
        if(ch) ch[parent]=p;
        /****/ p[child][flaj]=ch;
        p[size]=p[child][0][size]+p[child][1][size]+1;
    }
    void splay(int self) {
        int p,pp;
        while((p=self[parent])) {
            if((pp=p[parent]))
                rotate(flag(self)==flag(pp)?p:self);
            rotate(self);
        }
        root=self;
    }
    void insert__(lli val) {
        while(true) {
            int ch=root[child][root[value]<val];
            if(!ch) {
                ch=graphtop++;
                ch[value]=val;
                ch[child][0]=ch[child][1]=0;
                ch[parent]=root;
                ch[size]=1;
                root[child][root[value]<val]=ch;
                splay(ch);
                return;
            }
            root=ch;
        }
    }
    void insert(lli val) {
        if (!inserted) {
            root[value] = val;
            inserted = true;
            return ;
        }
        insert__(val);
    }
    lli queryf(int k)
    {
        // int target = root;
        $ printf("get %d\n",k);
        int self=root,szl;
        while((szl=self[child][0][size])!=k-1) {
            if(szl>k-1) {
                $ puts("goto left");
                self=self[child][0];
            }
            else {
                $ puts("goto right");
                self=self[child][1],
                    k-=szl+1;
            }
            $ printf("now size of left = %d\n",szl);
        }
        $ printf("value is %lld\n",self[value]);
        return self[value];
    }
} st;

int n, m;
lli ins[maxn];
vector<int> qry[maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ins[i]);
    for (int i = 1, a; i <= m; i++) {
        scanf("%d", &a);
        qry[a].push_back(i);
    }
    // Querying while inserting
    st.build_tree();
    for (int i = 1; i <= n; i++) {
        st.insert(ins[i]);
        for (unsigned int j = 0; j < qry[i].size(); j++)
            printf("%lld\n", st.queryf(qry[i][j]));
    }
    return 0;
}