数据结构复习1
线段树、主席树、平衡树、树链剖分
update【2018.7.23】我放弃指针版的了它欺负我呜呜呜
线段树
标记
多个标记考虑优先级
满足区间加法就可以用线段树
主席树
细节：
- x和y是节点编号，所以是root[i]不是i
- 每次复制原来的节点，再新建
平衡树
Treap
满足平衡树的性质，同时随机附加域维护一个小根堆
- rturn，左儿子成为根 c=t[x].l t[x].l=t[c].r t[c].r=x
- lturn，右儿子成为根
- 插入
- !x 新建节点
- 判断向哪走，递归结束时维护堆性质
- 删除
- !x 返回
- 判断有几个，1个的话左右儿子谁继承他。注意先旋转再删自己的技巧
- 还不到就走
- rnk, kth, pre, suf
#include#include #include #include using namespace std;#define lc t[x].l#define rc t[x].rconst int N = 1e5+5;inline int read() { int x=0, f=1; char c=getchar(); while(c<'0' || c>'9') {if(c=='-') f=-1; c=getchar();} while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();} return x*f;}struct meow { int x, l, r, v, w, size, rnd; meow() {} meow(int a) {l=r=0; v=a; w=size=1; rnd=rand();}} t[N];int sz, root;inline void update(int x) { t[x].size = t[lc].size + t[rc].size + t[x].w;}inline void rturn(int &x) { int c = lc; lc = t[c].r; t[c].r = x; t[c].size = t[x].size; update(x); x=c;}inline void lturn(int &x) { int c = rc; rc = t[c].l; t[c].l = x; t[c].size = t[x].size; update(x); x=c;}void insert(int &x, int v) { if(!x) { x = ++sz; t[x] = meow(v); } else { t[x].size++; if(v == t[x].v) t[x].w++; else if(v < t[x].v) { insert(lc, v); if(t[lc].rnd < t[x].rnd) rturn(x); } else { insert(rc, v); if(t[rc].rnd < t[x].rnd) lturn(x); } }}void erase(int &x, int v) { if(!x) return; if(v == t[x].v) { if(t[x].w > 1) t[x].w--, t[x].size--; else if(!lc || !rc) x = lc|rc; else if(t[lc].rnd < t[rc].rnd) rturn(x), erase(x, v); else lturn(x), erase(x, v); } else { t[x].size--; if(v < t[x].v) erase(lc, v); else erase(rc, v); }}int rnk(int x, int v) { if(!x) return 0; if(v == t[x].v) return t[lc].size + 1; else if(v < t[x].v) return rnk(lc, v); else return t[lc].size + t[x].w + rnk(rc, v);}int kth(int x, int k) { if(!x) return 0; if(k <= t[lc].size) return kth(lc, k); else if(k <= t[lc].size + t[x].w) return t[x].v; else return kth(rc, k - t[lc].size - t[x].w);}int ans = 0;void pre(int x, int v) { if(!x) return; if(t[x].v < v) ans = x, pre(rc, v); else pre(lc, v);}void suf(int x, int v) { if(!x) return; if(t[x].v > v) ans = x, suf(lc, v); else suf(rc, v);}int n;int main() { freopen("in", "r", stdin); srand(2333); n = read(); for(int i=1; i<=n; i++) { int c = read(), x = read(); if(c == 1) insert(root, x); else if(c == 2) erase(root, x); else if(c == 3) printf("%d\n", rnk(root, x)); else if(c == 4) printf("%d\n", kth(root, x)); else if(c == 5) pre(root, x), printf("%d\n", t[ans].v); else if(c == 6) suf(root, x), printf("%d\n", t[ans].v); }}
Splay
伸展树。插入、查询后将该节点splay到根
- rotate 将x转到父亲的位置 注意fa信息的维护
- splay 将x伸展到父亲为tar的位置 共线时先转父亲
- 插入
- !root 新节点是根
- 已存在v
- 不存在v，记录last信息，找到后处理
- 寻找 将v找到并splay到根
- 删除
- splay到根
- 多个
- 没有儿子，一个儿子
- 两个儿子，找左子树最大节点，splay到左儿子，右儿子接在左儿子右边
- rnk, kth, pre, suf
- 区间操作 [l,r] 将l-1对应的节点splay到左子树，r+1对应的节点splay到柚子树，r+1的左儿子子树就是区间[l,r]
#include#include #include #include using namespace std;#define lc t[x].ch[0]#define rc t[x].ch[1]#define pa t[x].faconst int N = 1e5+5;inline int read() { int x=0, f=1; char c=getchar(); while(c<'0' || c>'9') {if(c=='-') f=-1; c=getchar();} while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();} return x*f;}struct meow { int ch[2], fa, v, w, size; meow() {} meow(int a) {ch[0]=ch[1]=fa=0; v=a; w=size=1;}} t[N];int sz, root;inline void update(int x) { t[x].size = t[lc].size + t[rc].size + t[x].w;}inline int wh(int x) {return t[pa].ch[1] == x;}inline void rotate(int x) { int f = t[x].fa, g = t[f].fa, c = wh(x); if(g) t[g].ch[wh(f)] = x; t[x].fa = g; t[f].ch[c] = t[x].ch[c^1]; t[t[f].ch[c]].fa = f; t[x].ch[c^1] = f; t[f].fa = x; update(f); update(x);}inline void splay(int x, int tar) { for(; pa != tar; rotate(x)) if(t[pa].fa != tar) rotate(wh(x) == wh(pa) ? pa : x); if(!tar) root = x;}void insert(int v) { if(!root) {root = ++sz; t[root] = meow(v); return;} int x = root, last = 0; while(x) { if(v == t[x].v) { t[x].w++; t[x].size++; splay(x, 0); return; } last = x; if(v < t[x].v) x = lc; else x = rc; } x = ++sz; t[x] = meow(v); if(v < t[last].v) t[last].ch[0] = x; else t[last].ch[1] = x; t[x].fa = last; splay(x, 0);}int find(int v) { int x = root; while(x) { if(v == t[x].v) {splay(x, 0); break;} else if(v < t[x].v) x = lc; else x = rc; } return x;}void erase(int v) { int x = find(v); if(t[x].w > 1) t[x].w--, t[x].size--; else if(!lc && !rc) root = 0; else if(!rc) t[lc].fa = 0, root = lc; else if(!lc) t[rc].fa = 0, root = rc; else { int _ = lc; while(t[_].ch[1]) _ = t[_].ch[1]; splay(_, x); t[_].ch[1] = rc; t[rc].fa = _; t[_].fa = 0; root = _; update(root); }}int rnk(int v) { int x = root, lsize = 0; while(x) { if(v == t[x].v) { int ans = lsize + t[lc].size + 1; splay(x, 0); return ans; } else if(v < t[x].v) x = lc; else lsize += t[lc].size + t[x].w, x = rc; } return -1;}int kth(int k) { int x = root; while(x) { if(k <= t[lc].size) x = lc; else if(k <= t[lc].size + t[x].w) return t[x].v; else k -= t[lc].size + t[x].w, x = rc; } return -1;}int pre(int v) { int x = root, ans = 0; while(x) { if(t[x].v < v) ans = x, x = rc; else x = lc; } return ans;}int suf(int v) { int x = root, ans = 0; while(x) { if(t[x].v > v) ans = x, x = lc; else x = rc; } return ans;}int n, ans;int main() { freopen("in", "r", stdin); n = read(); for(int i=1; i<=n; i++) { int c = read(), x = read(); if(c == 1) insert(x); else if(c == 2) erase(x); else if(c == 3) printf("%d\n", rnk(x)); else if(c == 4) printf("%d\n", kth(x)); else if(c == 5) ans = pre(x), printf("%d\n", t[ans].v); else if(c == 6) ans = suf(x), printf("%d\n", t[ans].v); }}
Splay维护序列
不再看v从左到右从小到大，而是从左到右看成一个序列
提取区间，进行操作
资瓷区间翻转等一系列线段树不能做的操作
#include#include #include #include using namespace std;#define lc t[x].ch[0]#define rc t[x].ch[1]#define pa t[x].faconst int N = 1e5+5;inline int read() { int x=0, f=1; char c = getchar(); while(c < '0' || c > '9') {if(c=='-') f=-1;c=getchar();} while(c >= '0' && c <= '9') {x=x*10+c-'0'; c=getchar();} return x * f;}int n, m;struct meow { int ch[2], fa, w, size, rev;} t[N];int sz, root;inline void update(int x) { t[x].size = t[lc].size + t[rc].size + t[x].w;}inline int wh(int x) {return t[pa].ch[1] == x;}inline void paint(int x) { t[x].rev ^= 1; swap(lc, rc);}inline void push_down(int x) { if(t[x].rev) { paint(lc); paint(rc); t[x].rev = 0; }}void rotate(int x) { int f = t[x].fa, g = t[f].fa, c = wh(x); if(g) t[g].ch[wh(f)] = x; t[x].fa = g; t[f].ch[c] = t[x].ch[c^1]; t[t[f].ch[c]].fa = f; t[x].ch[c^1] = f; t[f].fa = x; update(f); update(x);}void splay(int x, int tar) { for(; pa != tar; rotate(x)) if(t[pa].fa != tar) rotate(wh(x) == wh(pa) ? pa : x); if(!tar) root = x;}void build(int &x, int l, int r) { if(l > r) return; x = (l+r) >> 1; build(lc, l, x-1); build(rc, x+1, r); t[lc].fa = t[rc].fa = x; t[x].w = 1; update(x);}int kth(int k) { int x = root; while(x) { push_down(x); if(k <= t[lc].size) x = lc; else if(k <= t[lc].size + t[x].w) return x; else k -= t[lc].size + t[x].w, x = rc; } return -1;}void print(int x) { if(!x) return; push_down(x); print(lc); if(x != 1 && x != n+2) printf("%d ", x-1); print(rc);}int main() { freopen("in", "r", stdin); n = read(); m = read(); build(root, 1, n+2); for(int i=1; i<=m; i++) { int l = read(), r = read(), f, x; f = kth(l); splay(f, 0); x = kth(r+2); splay(x, root); paint(lc); } print(root);}
树链剖分
轻重链剖分
dfs1 维护size deep fa heavy
dfs2 维护dfn top
重链的dfs序为一段
子树的dfs序也为一段
求一段的时候在重链上处理，跳轻边
#include#include #include #include using namespace std;#define mid ((l+r) >> 1)#define lc x<<1#define rc x<<1|1#define lson lc, l, mid#define rson rc, mid+1, rtypedef long long ll;const int N = 1e5+5;int n, m, root, P;inline int read() { int x=0, f=1; char c = getchar(); while(c < '0' || c > '9') {if(c=='-') f=-1;c=getchar();} while(c >= '0' && c <= '9') {x=x*10+c-'0'; c=getchar();} return x * f;}struct edge {int v, ne;} e[N<<1];int cnt, h[N];inline void ins(int u, int v) { e[++cnt] = (edge) {v, h[u]}; h[u] = cnt; e[++cnt] = (edge) {u, h[v]}; h[v] = cnt;}int deep[N], size[N], fa[N], hea[N], dfn[N], dfc, top[N], L[N], R[N];void dfs1(int u) { size[u] = 1; for(int i=h[u]; i; i=e[i].ne) { int v = e[i].v; if(v == fa[u]) continue; fa[v] = u; deep[v] = deep[u]+1; dfs1(v); size[u] += size[v]; if(size[v] > size[hea[u]]) hea[u] = v; }}void dfs2(int u, int anc) { dfn[u] = L[u] = ++dfc; top[u] = anc; if(hea[u]) dfs2(hea[u], anc); for(int i=h[u]; i; i=e[i].ne) { int v = e[i].v; if(v != hea[u] && v != fa[u]) dfs2(v, v); } R[u] = dfc;}int ow[N], w[N];namespace seg {struct meow { int sum, add;} t[N<<2];inline void paint(int x, int l, int r, int v) { t[x].sum = (t[x].sum + (ll) v * (r-l+1) %P) %P; t[x].add = (t[x].add + v) %P;}inline void push_down(int x, int l, int r) { if(t[x].add) { paint(lson, t[x].add); paint(rson, t[x].add); t[x].add = 0; }}inline void merge(int x) { t[x].sum = (t[lc].sum + t[rc].sum) %P;}void build(int x, int l, int r) { if(l == r) t[x].sum = w[l]; else { build(lson); build(rson); merge(x); }}void add(int x, int l, int r, int ql, int qr, int v) { if(ql <= l && r <= qr) paint(x, l, r, v); else { push_down(x, l, r); if(ql <= mid) add(lson, ql, qr, v); if(mid < qr) add(rson, ql, qr, v); merge(x); }}int que(int x, int l, int r, int ql, int qr) { if(ql <= l && r <= qr) return t[x].sum; else { push_down(x, l, r); int ans = 0; if(ql <= mid) ans = (ans + que(lson, ql, qr)) %P; if(mid < qr) ans = (ans + que(rson, ql, qr)) %P; return ans; }}}void add(int x, int y, int v) { while(top[x] != top[y]) { if(deep[top[x]] < deep[top[y]]) swap(x, y); seg::add(1, 1, n, dfn[top[x]], dfn[x], v); x = fa[top[x]]; } if(dfn[x] > dfn[y]) swap(x, y); seg::add(1, 1, n, dfn[x], dfn[y], v);}int que(int x, int y) { int ans = 0; while(top[x] != top[y]) { if(deep[top[x]] < deep[top[y]]) swap(x, y); ans = (ans + seg::que(1, 1, n, dfn[top[x]], dfn[x])) %P; x = fa[top[x]]; } if(dfn[x] > dfn[y]) swap(x, y); ans = (ans + seg::que(1, 1, n, dfn[x], dfn[y])) %P; return ans;}int main() { freopen("in", "r", stdin); n = read(); m = read(); root = read(); P = read(); for(int i=1; i<=n; i++) ow[i] = read(); for(int i=1; i