此题FHQ-Treap居然跑得比Splay还快?

回复帖子

@longlongzhu123 2019-04-24 08:55 回复

RT,用Splay进行启发式合并不是一个log的吗?

就算常数再大也不可能抵消掉这个log的差距吧,更何况是慢上200ms(LCT vs. 树剖???)

附上提交记录

还是我写的有问题?(代码放二楼)

@longlongzhu123 2019-04-24 08:56 回复 举报

代码如下:

Splay

#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 300000 + 10;
const int kMaxLog = 20;
const int kInf = 2000000000;
struct SplayTree {
  struct Node {
    int son[2], fa;
    int val;
    int cnt;
    int siz;
  };
  Node tree[kMaxN * kMaxLog];
  int top;
  inline int NewNode(int val) {
    tree[++top] = (Node) {0, 0, 0, val, 1, 1};
    return top;
  }
  inline int NewTree(int val) {
    int root = NewNode(val);
    Insert(root, -kInf);
    Insert(root, kInf);
    return root;
  }
  inline bool GetPos(int x) { return tree[tree[x].fa].son[1] == x; }
  inline bool GetDir(int x, int val) { return tree[x].val < val; }
  inline void PushUp(int x) {
    tree[x].siz = tree[tree[x].son[0]].siz +
                  tree[tree[x].son[1]].siz + tree[x].cnt;
  }
  inline void Connect(int son, int fa, bool pos) {
    if (fa) tree[fa].son[pos] = son;
    if (son) tree[son].fa = fa;
  }
  inline void Rotate(int x) {
    int y = tree[x].fa;
    int z = tree[y].fa;
    bool k = GetPos(x);
    if (z) tree[z].son[GetPos(y)] = x;
    tree[x].fa = z;
    Connect(tree[x].son[!k], y, k);
    Connect(y, x, !k);
    PushUp(y);
  }
  inline void Splay(int x, int target = 0) {
    while (tree[x].fa != target) {
      int y = tree[x].fa;
      if (tree[y].fa != target) Rotate(GetPos(x) == GetPos(y) ? y : x);
      Rotate(x);
    }
    PushUp(x);
  }
  inline int Find(int& root, int val) {
    int x = root;
    while (tree[x].val != val && tree[x].son[GetDir(x, val)])
      x = tree[x].son[GetDir(x, val)];
    Splay(x);
    root = x;
    return x;
  }
  inline void Insert(int& root, int val) {
    int x = root, y = 0;
    while (x && tree[x].val != val) {
      tree[x].siz++;
      y = x;
      x = tree[x].son[GetDir(x, val)];
    }
    if (!x) {
      x = NewNode(val);
      Connect(x, y, GetDir(y, val));
    } else {
      tree[x].siz++;
      tree[x].cnt++;
    }
    Splay(x);
    root = x;
  }
  inline int GetRank(int& root, int val) { // Bug!!!
    // 不能直接这样做!!!若val不存在则会WA
    /*int x = Find(val);
    return tree[tree[x].son[0]].siz + 1;*/
    int x = root;
    int ans = 0;
    while (1) {
      if (tree[x].val <= val) ans += tree[tree[x].son[0]].siz;
      if (tree[x].val < val) ans += tree[x].cnt;
      if (tree[x].val == val || !tree[x].son[GetDir(x, val)]) {
        Splay(x);
        root = x;
        return ans + 1;
      } else {
        x = tree[x].son[GetDir(x, val)];
      }
    }
  }
  inline int GetKth(int& root, int k) {
    k++;
    int x = root;
    if (tree[x].siz <= k) return -1;
    while (1) {
      int lson = tree[x].son[0];
      if (k <= tree[lson].siz) {
        x = lson;
      } else if (k <= tree[lson].siz + tree[x].cnt) {
        Splay(x);
        root = x;
        return tree[x].val;
      } else {
        k -= tree[lson].siz + tree[x].cnt;
        x = tree[x].son[1];
      }
    }
  }
  void Merge(int& root, int x) {
    if (!x) return;
    Merge(root, tree[x].son[0]);
    if (tree[x].val != kInf && tree[x].val != -kInf)
      Insert(root, tree[x].val);
    Merge(root, tree[x].son[1]);
  }
  void Print(int x) {
    if (!x) return;
    Print(tree[x].son[0]);
    printf("%d ", tree[x].val);
    Print(tree[x].son[1]);
  }
  void PrintTree(const char* message, int root) {
    printf("%s[ ", message);
    Print(root);
    printf("]\n");
  }
};
struct UnionSet {
  int father[kMaxN];
  UnionSet() {
    for (int i = 0; i < kMaxN; i++) father[i] = i;
  }
  int Find(int x) {
    if (father[x] == x) {
      return x;
    } else {
      return father[x] = Find(father[x]);
    }
  }
  bool Union(int x, int y) {
    int i = Find(x);
    int j = Find(y);
    father[j] = i;
    return i != j;
  }
};
SplayTree T;
UnionSet S;
int n, m, q;
int root[kMaxN];
int island[kMaxN];
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    int a;
    scanf("%d", &a);
    root[i] = T.NewTree(a);
    island[a] = i;
  }
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    u = S.Find(u);
    v = S.Find(v);
    if (u != v) {
      // T.PrintTree("Splay u = ", root[u]);
      // T.PrintTree("Splay v = ", root[v]);
      if (T.tree[root[u]].siz < T.tree[root[v]].siz) {
        swap(root[u], root[v]);
      }
      T.Merge(root[u], root[v]);
      // T.PrintTree("Splay u + v = ", root[u]);
      S.father[v] = u;
    }
  }
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    char opt;
    int x, y;
    scanf("%s %d %d", &opt, &x, &y);
    if (opt == 'Q') {
      int ans = T.GetKth(root[S.Find(x)], y);
      if (ans == -1) {
        printf("-1\n");
      } else {
        printf("%d\n", island[ans]);
      }
    } else {
      assert(opt == 'B');
      x = S.Find(x);
      y = S.Find(y);
      if (x != y) {
        // T.PrintTree("Splay x = ", root[x]);
        // T.PrintTree("Splay y = ", root[y]);
        if (T.tree[root[x]].siz < T.tree[root[y]].siz) {
          swap(root[x], root[y]);
        }
        T.Merge(root[x], root[y]);
        // T.PrintTree("Splay x + y = ", root[x]);
        S.father[y] = x;
      }
    }
  }
  return 0;
}

Treap

#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 300000 + 10;
const int kMaxLog = 20;
const int kInf = 2000000000;
struct FhqTreap {
  struct Node {
    int val;
    int l,r;
    int siz;
    int pri;
  };
  Node tree[kMaxN * kMaxLog];
  int top;
  inline int NewNode(int val) {
    top++;
    tree[top].val = val;
    tree[top].l = tree[top].r = 0;
    tree[top].siz = 1;
    tree[top].pri = rand();
    return top;
  }
  inline void PushUp(int x) {
    tree[x].siz = tree[tree[x].l].siz + tree[tree[x].r].siz + 1;
  }
  int Merge(int x, int y) {
    if (!x || !y) {
      return x | y;
    } else if (tree[x].pri < tree[y].pri) {
      tree[x].r = Merge(tree[x].r, y);
      PushUp(x);
      return x;
    } else {
      tree[y].l = Merge(x, tree[y].l);
      PushUp(y);
      return y;
    }
  }
  void SplitByVal(int node, int& x, int& y, int k) {
    if (!node) {
      x = y = 0;
    } else if (tree[node].val <= k) {
      x = node;
      SplitByVal(tree[x].r, tree[x].r, y, k);
      PushUp(x);
    } else {
      y = node;
      SplitByVal(tree[y].l, x, tree[y].l, k);
      PushUp(y);
    }
  }
  void SplitBySiz(int node, int& x, int& y, int k) {
    if (!node) {
      x = y = 0;
    } else if (tree[tree[node].l].siz + 1 <= k) {
      x = node;
      SplitBySiz(tree[x].r, tree[x].r, y, k - tree[tree[x].l].siz - 1);
      PushUp(x);
    } else {
      y = node;
      SplitBySiz(tree[y].l, x, tree[y].l, k);
      PushUp(y);
    }
  }
  inline void Insert(int& root, int val) {
    int x, y;
    SplitByVal(root, x, y, val);
    root = Merge(Merge(x, NewNode(val)), y);
  }
  inline int GetKth(int& root, int k) {
    if (k > tree[root].siz) return -1;
    int x, y;
    SplitBySiz(root, x, y, k);
    int node = x;
    while (tree[node].r) node = tree[node].r;
    root = Merge(x, y);
    return tree[node].val;
  }
  void MergeTree(int& root, int x) {
    if (!x) return;
    MergeTree(root, tree[x].l);
    Insert(root, tree[x].val);
    MergeTree(root, tree[x].r);
  }
};
struct UnionSet {
  int father[kMaxN];
  UnionSet() {
    for (int i = 0; i < kMaxN; i++) father[i] = i;
  }
  int Find(int x) {
    if (father[x] == x) {
      return x;
    } else {
      return father[x] = Find(father[x]);
    }
  }
  bool Union(int x, int y) {
    int i = Find(x);
    int j = Find(y);
    father[j] = i;
    return i != j;
  }
};
FhqTreap T;
UnionSet S;
int n, m, q;
int root[kMaxN];
int island[kMaxN];
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    int a;
    scanf("%d", &a);
    root[i] = T.NewNode(a);
    island[a] = i;
  }
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    u = S.Find(u);
    v = S.Find(v);
    if (u != v) {
      // T.PrintTree("Splay u = ", root[u]);
      // T.PrintTree("Splay v = ", root[v]);
      if (T.tree[root[u]].siz < T.tree[root[v]].siz) {
        swap(root[u], root[v]);
      }
      T.MergeTree(root[u], root[v]);
      // T.PrintTree("Splay u + v = ", root[u]);
      S.father[v] = u;
    }
  }
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    char opt;
    int x, y;
    scanf("%s %d %d", &opt, &x, &y);
    if (opt == 'Q') {
      int ans = T.GetKth(root[S.Find(x)], y);
      if (ans == -1) {
        printf("-1\n");
      } else {
        printf("%d\n", island[ans]);
      }
    } else {
      assert(opt == 'B');
      x = S.Find(x);
      y = S.Find(y);
      if (x != y) {
        // T.PrintTree("Splay x = ", root[x]);
        // T.PrintTree("Splay y = ", root[y]);
        if (T.tree[root[x]].siz < T.tree[root[y]].siz) {
          swap(root[x], root[y]);
        }
        T.MergeTree(root[x], root[y]);
        // T.PrintTree("Splay x + y = ", root[x]);
        S.father[y] = x;
      }
    }
  }
  return 0;
}
@The_KOG  2019-04-24 09:10 回复 举报

哪来的这么多操作,我就四个函数

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int Ins(int &k,int l,int r,int val){
    if(!k)k=++sz;
    if(l==r)return nd[k].sum=1;
    if((val<=mid&&Ins(nd[k].ls,l,mid,val))||Ins(nd[k].rs,mid+1,r,val));
    return nd[k].sum=nd[nd[k].ls].sum+nd[nd[k].rs].sum,1;
}
int Ask(int k,int l,int r,int rk){
    if(l==r)return l;
    return nd[nd[k].ls].sum>=rk?Ask(nd[k].ls,l,mid,rk):Ask(nd[k].rs,mid+1,r,rk-nd[nd[k].ls].sum);
}
int Mrg(int a,int b){
    if(!a||!b)return a|b;
    nd[a].ls=Mrg(nd[a].ls,nd[b].ls),nd[a].rs=Mrg(nd[a].rs,nd[b].rs);
    nd[a].sum=nd[nd[a].ls].sum+nd[nd[a].rs].sum;
    return a;
}
@142857cs  2019-04-24 09:24 回复 举报

我看了一下原论文,看不懂,但是结论中出现了上万的常数和超过1e9的低次项。。。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。