数据结构模板整合

(Updated: )
(22 mins to read)

替罪羊树

维护权值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
const int N = 1e5 + 5;
const double alpha = 0.7;
struct node
{
  int ls, rs;
  int val, sz, cnt;
}t[N];
int rt, tot;
void up(int p) { t[p].sz = t[t[p].ls].sz + t[t[p].rs].sz + t[p].cnt; }
bool bad(int p) { return t[p].cnt && t[p].sz*alpha<max(t[t[p].ls].sz, t[t[p].rs].sz); }
int ord[N], top;
void dfs(int p)
{
  if(!p) return;
  dfs(t[p].ls);
  if(t[p].cnt) ord[++top] = p;
  dfs(t[p].rs);
}
int build(int l, int r)
{
  if(l>r) return 0;
  int mid = (l+r)>>1, p = ord[mid];
  t[p].ls = build(l, mid-1);
  t[p].rs = build(mid+1, r);
  up(p);
  return p;
}
void rebuild(int &p)
{
  top = 0;
  dfs(p);
  p = build(1, top);
}
void newnode(int &p, int v)
{
  p = ++tot;
  t[p].val = v, t[p].ls = t[p].rs = 0;
  t[p].cnt = t[p].sz = 1;
}
void ins(int &p, int v)
{
  if(!p) newnode(p, v);
  else
  {
    if(v==t[p].val) t[p].cnt++;
    else if(v<t[p].val) ins(t[p].ls, v);
    else ins(t[p].rs, v);
    up(p);
    if(bad(p)) rebuild(p);
  }
}
void del(int &p, int v)
{
  if(v==t[p].val) t[p].cnt--;
  else if(v<t[p].val) del(t[p].ls, v);
  else del(t[p].rs, v);
  up(p);
  if(bad(p)) rebuild(p);
}
int Less(int p, int v, bool eq)
{
  if(!p) return 0;
  if(t[p].cnt&&v==t[p].val) return t[t[p].ls].sz + t[p].cnt*eq;
  else if(v<t[p].val) return Less(t[p].ls, v, eq);
  else return t[t[p].ls].sz + t[p].cnt + Less(t[p].rs, v, eq);
}
int kth(int p, int k)
{
  if(k<=t[t[p].ls].sz) return kth(t[p].ls, k);
  else if(t[t[p].ls].sz+t[p].cnt>=k) return t[p].val;
  else return kth(t[p].rs, k-t[p].cnt-t[t[p].ls].sz);
}

fhq treap

维护区间的（按size分裂），带有up、down以及fa的维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
int rt, tot;
int rnd() { return rand()<<15|rand(); }
struct node
{
  int ls, rs;
  int fa, key, sz;
}t[N];
int newnode(int c)
{
  int p = ++tot;
  t[p].ls = t[p].rs = t[p].fa = 0;
  t[p].key = rnd();
  t[p].sz = 1;
  return p;
}
void up(int p)
{
  t[p].sz = t[t[p].ls].sz + t[t[p].rs].sz + 1;
}
void down(int p)
{
}
void split(int p, int &x, int &y, int k, int fx=0, int fy=0)
{
  if(!p) { x = y = 0; return; }
  down(p);
  if(k<=t[t[p].ls].sz)
  {
    y = p;
    split(t[p].ls, x, t[p].ls, k, fx, p);
  }
  else
  {
    x = p;
    split(t[p].rs, t[p].rs, y, k-t[t[p].ls].sz-1, p, fy);
  }
  if(x) t[x].fa = fx;
  if(y) t[y].fa = fy;
  up(p);
}
void merge(int &p, int x, int y)
{
  if(!x||!y) { p = x|y; return; }
  if(t[x].key<t[y].key)
  {
    down(x);
    p = x;
    merge(t[p].rs, t[p].rs, y);
    t[t[p].rs].fa = p;
  }
  else
  {
    down(y);
    p = y;
    merge(t[p].ls, x, t[p].ls);
    t[t[p].ls].fa = p;
  }
  up(p);
}
void downall(int p)
{
  if(!p) return;
  downall(t[p].fa);
  down(p);
}
int get(int p)
{
  downall(p);
  int rk = t[t[p].ls].sz + 1;
  while(t[p].fa)
  {
    if(t[t[p].fa].rs==p) rk += t[t[p].fa].sz - t[p].sz;
    p = t[p].fa;
  }
  return rk;
}
int kth(int p, int k)
{
  down(p);
  if(k<=t[t[p].ls].sz) return kth(t[p].ls, k);
  else if(k==t[t[p].ls].sz+1) return t[p].c;
  else return kth(t[p].rs, k-t[t[p].ls].sz-1);
}

splay

维护区间，注意及时up，只需要在kth中down即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int rt;
int ch[N][2], sz[N], fa[N];
bool rs(int x) { return ch[fa[x]][1]==x; }
void up(int p)
{
  if(!p) return;
  int l = ch[p][0], r = ch[p][1];
}
void down(int p)
{
}
void build(int l, int r, int f)
{
  if(l>r) return;
  int p = (l+r)>>1;
  sz[p] = 1, fa[p] = f, ch[f][p>f] = p;
  if(l==r) return;
  build(l, p-1, p); build(p+1, r, p);
  up(p);
}
void rotate(int x)
{
  int y = fa[x], z = fa[y], k = rs(x), w = ch[x][k^1];
  ch[y][k] = w; fa[w] = y;
  ch[z][rs(y)] = x; fa[x] = z;
  ch[x][k^1] = y; fa[y] = x;
  up(y); up(x);
}
void splay(int x, int g=0)
{
  while(fa[x]!=g)
  {
    int y = fa[x];
    if(fa[y]!=g) (rs(x)==rs(y) ? rotate(y) : rotate(x));
    rotate(x);
  }
  if(!g) rt = x;
}
int kth(int p, int k)
{
  down(p);
  if(ch[p][0]&&sz[ch[p][0]]>=k) return kth(ch[p][0], k);
  else if(sz[ch[p][0]]+1==k) return p;
  else return kth(ch[p][1], k-sz[ch[p][0]]-1);
}
int split(int l, int r)
{
  int x = kth(rt, l-1), y = kth(rt, r+1);
  splay(x); splay(y, x);
  return ch[y][0];
}

LCT

维护边权：拆点维护边双：每次加边，如果两端点已经连通，则用并查集缩起来，然后在access的时候，x=fa[x]=find(fa[x])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
int ch[N][2], fa[N], rev[N];
bool rs(int x) { return ch[fa[x]][1]==x; }
int notrt(int x) { return ch[fa[x]][0]==x || ch[fa[x]][1]==x; }
void up(int x)
{
}
void reverse(int x)
{
  swap(ch[x][0], ch[x][1]);
  rev[x] ^= 1;
}
void down(int x)
{
  if(rev[x])
  {
    if(ch[x][0]) reverse(ch[x][0]);
    if(ch[x][1]) reverse(ch[x][1]);
    rev[x] = 0;
  }
}
void pushall(int x)
{
  if(notrt(x)) pushall(fa[x]);
  down(x);
}
void rotate(int x)
{
  int y = fa[x], z = fa[y], k = rs(x);
    if(notrt(y)) ch[z][ch[z][1]==y] = x;
    ch[y][k] = ch[x][!k]; fa[ch[x][!k]] = y;
    ch[x][!k] = y, fa[y] = x, fa[x] = z;
    up(y), up(x), up(z);
}
void splay(int x)
{
  pushall(x);
  for(int f=fa[x]; f=fa[x], notrt(x); rotate(x))
    if(notrt(f)) rotate(rs(x) == rs(f) ? f : x);
}
void access(int x)
{
  for(int y=0; x; y=x, x=fa[x])
    splay(x), ch[x][1] = y, up(x);
}
void makert(int x)
{
  access(x); splay(x);
  reverse(x);
}
int findrt(int x)
{
  access(x); splay(x);
  while(ch[x][0]) down(x), x = ch[x][0];
  splay(x);
  return x;
}
void split(int x, int y)
{
  makert(x);
  access(y); splay(y);
}
void link(int x, int y)
{
  makert(x);
  if(findrt(y)!=x) fa[x] = y;
}
void cut(int x, int y)
{
  makert(x);
  if(findrt(y)==x&&fa[y]==x&&!ch[y][0])
  {
    fa[y] = ch[x][1] = 0;
    up(x);
  }
}

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int M = 2174729;
struct HashTable
{
  struct node { int next, v; ull k; }e[M+5];
  int head[M], st[N], tp, sz;
  int f(ull k) { return k % M; }
  void clear() { sz = 0; while(tp) head[st[tp--]] = 0; }
  int get(ull k)
  {
    int t = f(k);
    for(int p = head[t]; p; p = e[p].next)
      if(e[p].k==k) return e[p].v;
    ++sz;
    e[sz] = {head[t], sz, k};
    head[t] = sz; st[++tp] = t;
    return sz;
  }
};

哈希set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct HashSet
{
  struct node { int next; ull k; }e[M+5];
  int head[M], st[N], tp, sz;
  int f(ull k) { return k % M; }
  void clear() { sz = 0; while(tp) head[st[tp--]] = 0; }
  bool get(ull k)
  {
    for(int p = head[f(k)]; p; p = e[p].next)
      if(e[p].k==k) return true;
    return false;
  }
  void ins(ull k)
  {
    if(get(k)) return;
    int t = f(k);
    e[++sz] = {head[t], k};
    head[t] = sz; st[++tp] = t;
  }
};

gp_hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct custom_hash {
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return x + FIXED_RANDOM;
  }
};
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
gp_hash_table<ull, int, custom_hash>
gp_hash_table<ull, bool>
gp_hash_table<ull, null_type>

bitset压位(64位和32位速度差不多)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
struct Bitset
{
  using uint = uint32_t;
  static const int B = 32;
  static const uint up = numeric_limits<uint>::max();
  vector<uint> b; int sz;
  Bitset(int _sz=0) { sz = _sz; b.resize((sz+B-1)/B, 0); }
  Bitset operator | (const Bitset &oth) const
  {
    Bitset res(sz);
    int i;
    for(i=0; i+3<(int)b.size(); i+=4)
    {
      res.b[i] = b[i] | oth.b[i];
      res.b[i+1] = b[i+1] | oth.b[i+1];
      res.b[i+2] = b[i+2] | oth.b[i+2];
      res.b[i+3] = b[i+3] | oth.b[i+3];
    }
    while(i<(int)b.size())
      res.b[i] = b[i] | oth.b[i], i++;
    return res;
  }
  void set(int p) { b[p/B] |= (1ull<<(p%B)); }
  void reset(int p) { b[p/B] &= (up^(1ull<<(p%B))); }
  void setv(int p, int v) { (v ? set(p) : reset(p)); }
  bool get(uint x, int bit) { return (x>>bit)&1; }
  int getf0(uint x) { for(int i=0; i<B; i++) if(!get(x, i)) return i; }
  int getf1(uint x) { for(int i=0; i<B; i++) if(get(x, i)) return i; }
  int getl0(uint x) { for(int i=B-1; i>=0; i--) if(!get(x, i)) return i; }
  int getl1(uint x) { for(int i=B-1; i>=0; i--) if(get(x, i)) return i; }
  int findr0(int x)
  {
    int p = x/B, q = x%B;
    for(int i=q; i<B; i++) if(!get(b[p], i)) return x+i-q;
    for(int i=p+1; i<(int)b.size(); i++)
      if(b[i]!=up) return x+B-1-q+(i-p-1)*B+getf0(b[i])+1;
    return sz + 1;
  }
  int findr1(int x)
  {
    int p = x/B, q = x%B;
    for(int i=q; i<B; i++) if(get(b[p], i)) return x+i-q;
    for(int i=p+1; i<(int)b.size(); i++)
      if(b[i]) return x+B-1-q+(i-p-1)*B+getf1(b[i])+1;
    return sz + 1;
  }
  int findl0(int x)
  {
    int p = x/B, q = x%B;
    for(int i=q; i>=0; i--) if(!get(b[p], i)) return x+i-q;
    for(int i=p-1; i>=0; i--)
      if(b[i]!=up) return x-q-(p-1-i)*B-(B-getl0(b[i]));
    return -1;
  }
  int findl1(int x)
  {
    int p = x/B, q = x%B;
    for(int i=q; i>=0; i--) if(get(b[p], i)) return x+i-q;
    for(int i=p-1; i>=0; i--)
      if(b[i]) return x-q-(p-1-i)*B-(B-getl1(b[i]));
    return -1;
  }
};