CQOI2014 排序机械臂

用 Splay 来模拟题目中的操作,注意旋转某个结点至根之前要将到根路径上的所有标记下放。

#include <iostream>
#include <cstdio>
#include <algorithm>

const int MAXN = 1e5;

int n, tot;
int we[MAXN | 1], p[MAXN | 1];

struct Num {
  int num, id;
  Num() {}
  friend bool operator < (const Num &lhs, const Num &rhs) {
    return lhs.num < rhs.num || (lhs.num == rhs.num && lhs.id < rhs.id);
  }
} a[MAXN | 1];

inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar(); while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}

namespace Splay {
  struct Node {
    int val, size, lazy;
    Node *ch[2], *father;
    Node() {
      ch[0] = ch[1] = NULL;
      father = NULL;
    }
  } *root, *w[MAXN | 1];
  inline int size(Node *o) {
    return o ? o -> size : 0;
  }
  inline int relation(Node *o) {
    return o -> father ? o -> father -> ch[1] == o : 0; 
  }
  inline void pushup(Node *o) {
    o -> size = size(o -> ch[0]) + 1 + size(o -> ch[1]);
  }
  inline void pushdown(Node *o) {
    if (o -> lazy) {
      if (o -> ch[0]) o -> ch[0] -> lazy ^= 1;
      if (o -> ch[1]) o -> ch[1] -> lazy ^= 1;
      std::swap(o -> ch[0], o -> ch[1]);
      o -> lazy = 0;
    }
  }
  inline void connect(Node *x, Node *y, int wson) {
    if (x) x -> father = y;
    if (y) y -> ch[wson] = x;
  }
  inline void rotate(Node *o) {
    Node *p = o -> father, *q = p -> father;
    int wson = relation(o);    
    connect(o, q, relation(p));
    connect(o -> ch[wson ^ 1], p, wson);
    connect(p, o, wson ^ 1);
    pushup(p);
    pushup(o);
  }
  inline void splay(Node *o, Node *goal, int bug) {
    if (!goal) root = o;
    while (o -> father != goal) {
      Node *p = o -> father, *q = p -> father;
      if (q != goal) relation(o) ^ relation(p) ? rotate(o) : rotate(p);
      rotate(o);
    }
  }
  void pushTag(Node *o) {
    if (o == NULL) return;
    pushTag(o -> father);
    pushdown(o);
  }
  Node *kth(int k) {
    Node *o = root;
    while (o != NULL) {
      pushdown(o);
      if (size(o -> ch[0]) + 1 == k) return o;
      else if (size(o -> ch[0]) >= k) o = o -> ch[0];
      else {
        k -= size(o -> ch[0]) + 1;
        o = o -> ch[1];
      }
    }
    return NULL;
  }
  void reverse(int l, int r) {
    Node *o1 = kth(l), *o2 = kth(r + 2);
    splay(o1, NULL, 1);
    splay(o2, o1, 2);
    root -> ch[1] -> ch[0] -> lazy ^= 1;
  }
  int query(int x) {
    pushTag(w[x]);
    splay(w[x], NULL, x + 5);
    int res = size(root -> ch[0]);
    reverse(x, res);
    return res;
  }
  void build(Node *&o, Node *fa, int l, int r) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    o = new Node;
    o -> val = 0;
    o -> father = fa;
    if (mid != 0 && mid != n + 1) {
      w[we[mid]] = o;    
      o -> val = p[mid];
    }
    build(o -> ch[0], o, l, mid - 1);
    build(o -> ch[1], o, mid + 1, r);
    pushup(o);
  }
}

using namespace Splay;

int main() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    p[i] = a[i].num = read();
    a[i].id = i;
  }
  std::sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; ++i) {
    we[a[i].id] = i;
  }
  build(root, NULL, 0, n + 1);
  for (int i = 1; i <= n; ++i) {
    printf("%d ", query(i));    
  }
  return 0;
}
最后修改:2019 年 08 月 16 日 10 : 57 AM

发表评论