【洛谷 P3165】 [CQOI2014]排序机械臂（Splay）

题目链接

debug了\(N\)天没debug出来，原来是找后继的时候没有pushdown。。。

众所周知，，Splay中每个编号对应的节点的值是永远不会变的，因为所有旋转、翻转操作改变的都是父节点和子节点的指针。

于是记录每个数在\(Splay\)中的位置，然后按大小升序排序，每次把第\(i\)个数转到根，然后其左儿子的大小就是本次的答案（为什么不是左儿子大小+1？因为有个哨兵节点啊）。

然后区间翻转就不用说了，基本操作。

#include <cstdio>

#include <algorithm>

using namespace std;

inline int read(){

    int s = 0, w = 1;

    char ch = getchar();

    while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}

    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();

    return s * w;

}

const int MAXN = 100010;

struct Map{

    int val, pos, id;

    int operator < (const Map A) const{

        return val < A.val || (val == A.val && id < A.id);

    }

}p[MAXN];

struct SplayTree{

    int ch[2], fa, val, lazy, size, pos;

    Map Min;

}t[MAXN];

int num, root, n, m;

void pushdown(int u){

    if(t[u].lazy){

      swap(t[u].ch[0], t[u].ch[1]);

      t[t[u].ch[0]].lazy ^= 1;

      t[t[u].ch[1]].lazy ^= 1;

      t[u].lazy = 0;

    }

}

void pushup(int u){

    t[u].size = t[t[u].ch[0]].size + t[t[u].ch[1]].size + 1;

}

void rotate(int x){

    int y = t[x].fa; int z = t[y].fa; int k = t[y].ch[1] == x;

    pushdown(y); pushdown(x);

    t[z].ch[t[z].ch[1] == y] = x; t[x].fa = z;

    t[y].ch[k] = t[x].ch[k ^ 1]; t[t[x].ch[k ^ 1]].fa = y;

    t[x].ch[k ^ 1] = y; t[y].fa = x;

    pushup(y); pushup(x);

}

void Splay(int x, int goal){

    while(t[x].fa != goal){

      int y = t[x].fa; int z = t[y].fa;

      if(z) pushdown(z); pushdown(y); pushdown(x);

      if(z != goal)

        (t[z].ch[0] == y) ^ (t[y].ch[0] == x) ? rotate(x) : rotate(y);

      rotate(x);

    }

    if(goal == 0) root = x;

}

int build(int l, int r){

    int id = ++num;

    int mid = (l + r) >> 1;

    t[id].val = p[mid].val; p[mid].pos = id;

    if(mid > l){

      t[id].ch[0] = build(l, mid - 1);

      t[t[id].ch[0]].fa = id;

    }

    if(mid < r){

      t[id].ch[1] = build(mid + 1, r);

      t[t[id].ch[1]].fa = id;

    }

    pushup(id);

    return id;

}

inline int findKth(int k){

    int u = root;

    while(1){

      pushdown(u);

      if(t[t[u].ch[0]].size >= k) u = t[u].ch[0];

      else if(t[t[u].ch[0]].size == k - 1) return u;

      else k -= t[t[u].ch[0]].size + 1, u = t[u].ch[1];

    }

}

int next(int x){

    Splay(x, 0);

    pushdown(x);

    int u = t[x].ch[1];

    pushdown(u);

    while(t[u].ch[0]){

      u = t[u].ch[0];

      pushdown(u);

    }

    return u;

}

int main(){

    n = read();

    for(int i = 1; i <= n; ++i)

       p[i].val = read(), p[i].id = i;

    p[n + 1].val = 2147483647; p[n + 1].id = n + 1; p[0].val = -2147483646;

    root = build(0, n + 1);

    sort(p + 1, p + n + 1);

    for(int i = 1; i <= n; ++i){

        int l = findKth(i);

        int r = p[i].pos;

        Splay(r, 0);

        printf("%d ", t[t[root].ch[0]].size);

        r = next(r);

        Splay(l, 0);

        Splay(r, l);

        t[t[t[root].ch[1]].ch[0]].lazy ^= 1;

    }

    return 0;

}

巴特西

【洛谷 P3165】 [CQOI2014]排序机械臂（Splay）

最新文章

热门文章

巴特西

【洛谷 P3165】 [CQOI2014]排序机械臂 （Splay）

最新文章

热门文章

【洛谷 P3165】 [CQOI2014]排序机械臂（Splay）