「BZOJ3600」没有人的算术 替罪羊树+线段树
题目描述
过长……不想发图也不想发文字,所以就发链接吧……
没有人的算术
题解
\(orz\)神题一枚
我们考虑如果插入的数不是数对,而是普通的数,这就是一道傻题了——直接线段树一顿乱上就可以了。
于是我们现在只需要解决一个问题——维护这些数的大小关系。
由于这些数具有有序性,我们可以将这些数的值重记为一个数,这样就可以无脑地比较了。并且,由于这些值的大小可能会随着插入而更改,所以要用一棵平衡树来维护。
那么问题来了,这个数取什么值比较好呢?
首先当然可以是排名,不过如果使用排名,每次访问值的时候都要重新在平衡树中查一次,复杂度肯定是\(O(nlog^2n)\)的,基本不现实。
换一个角度可以发现,我们只需要知道大小关系,不需要排名,于是我们可以用实数维护一个数的大小,虽然相邻的数差值大小不同,只要相对大小是正确的就不必担心了……
那么我们可以这样看,在平衡树中每个节点维护一个区间\((l,r)\),表示这棵子树中所有数值都在\((l,r)\)之中,而这棵子树的根的值为\(mid=\frac{(l+r)}{2}\)递归左右子树的时候,将区间分成\((l,mid)\)和\((mid,r)\),完全满足二叉搜索树的性质,并且可以随时在任何位置新增一个数而不影响已有的数的数值。
那么问题就得到了解决,我们用一棵平衡树维护出现过的所有数对,节点上保存这个数对的两个父亲和\((l,r)\),并用\(mid=\frac{(l+r)}{2}\)表示这个节点的数值,然后无脑做插入和询问即可。
但是我们忽略了一个问题,我们应该使用什么样的平衡树?发现那些基于旋转的平衡树在旋转后都会出现一个致命的问题,\((l,r)\)无法维护!因为一次旋转会使得它以及它的子树全部的\((l,r)\)都被改变,复杂度难以承受。于是我们想到了替罪羊树,基于重构的它反正都要全部拍扁了重来,重新为区间赋值不就可以在重构时顺便一起做了吗?
于是,这道题就这么被切掉了……
(内心:哪有说的这么简单)
总结:
替罪羊树的维护方式与\(AVL\)、\(SBT\)、\(Splay\)都不一样,后几种算法都是通过旋转维护平衡,然而替罪羊树却是用重构维护平衡,重构的时候可以重新计算值,不需要通过原来的值进行改变。所以替罪羊树可以维护的信息更加灵活,并且拍扁重建很欢乐常数小。于是替罪羊树非常适合套其他的数据结构……树套树时也要想一想能不能用替罪羊树……
\(Code:\)
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define N 100005 #define M 800005 #define eps 1e-10 #define inf 1e20 #define equal(a, b) (fabs((a) - (b)) < eps) #define val(a) (a == -1 ? -inf :(ls[a] + rs[a])/ 2) #define lim 0.77 char opt[10]; int n, m; void Insert(int q, int l, int r, int k, int a); int getint() { int p=0; char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')p=p*10+c-'0',c=getchar(); return p; } struct SCT { int root, cnt, sz[M]; int num, arr[M]; int lc[M], rc[M]; int lf[M], rf[M]; double ls[M], rs[M]; bool Equal(int u, int l, int r) { return equal(val(lf[u]), val(l)) && equal(val(rf[u]), val(r)); } bool Less(int u, int l, int r) { return equal(val(lf[u]), val(l)) ? val(rf[u]) < val(r) : val(lf[u]) < val(l); } void Pushup(int q) { sz[q] = sz[lc[q]] + sz[rc[q]] + 1; } void Getarray(int q) { if (lc[q]) Getarray(lc[q]); arr[++num] = q; if (rc[q]) Getarray(rc[q]); } void Rebuild(int &q, int l, int r, double L, double R) { if (l > r) { q = 0; return; } int mid = (l + r) >> 1; double Mid = (L + R) / 2; q = arr[mid]; ls[q] = L; rs[q] = R; Rebuild(lc[q], l, mid - 1, L, Mid); Rebuild(rc[q], mid + 1, r, Mid, R); Pushup(q); } void Maintain(int &q) { num = 0; Getarray(q); Rebuild(q, 1, num, ls[q], rs[q]); } void Add(int &q, int l, int r, double L, double R, int k) { if (!q) { q = ++cnt; lf[q] = l, rf[q] = r; ls[q] = L, rs[q] = R; sz[q] = 1; Insert(1, 1, n, k, cnt); return; } if (Equal(q, l, r)) { Insert(1, 1, n, k, q); return; } if (Less(q, l, r)) Add(rc[q], l, r, (L + R) / 2, R, k); else Add(lc[q], l, r, L, (L + R) / 2, k); Pushup(q); } void Check(int &q, int l, int r) { if (sz[q] * lim < sz[lc[q]] || sz[q] * lim < sz[rc[q]]) { Maintain(q); return; } if (Equal(q, l, r)) return; if (Less(q, l, r)) Check(rc[q], l, r); else Check(lc[q], l, r); } }T; struct data { int plc, num; data(){} data(int a, int b){plc = a, num = b;} double Val(){return (T.ls[num] + T.rs[num])/ 2;} data operator + (data b) { if (num == 1 && b.num == 1) return plc < b.plc ? *this : b; if (num == 1) return b; if (b.num == 1) return *this; if (equal(Val(), b.Val())) return plc < b.plc ? *this : b; if (Val() > b.Val()) return *this; return b; } }; struct SGT { data a[N << 2]; }S; void Insert(int q, int l, int r, int k, int a) { if (l == k && r == k) { S.a[q] = data(k, a); return; } int mid = (l + r) >> 1; if (k <= mid) Insert(q << 1, l, mid, k, a); else Insert(q << 1 | 1, mid + 1, r, k, a); S.a[q] = S.a[q << 1] + S.a[q << 1 | 1]; } data Query(int q, int l, int r, int L, int R) { if (l == L && r == R) return S.a[q]; int mid = (l + r) >> 1; if (R <= mid) return Query(q << 1, l, mid, L, R); if (L > mid) return Query(q << 1 | 1, mid + 1, r, L, R); return Query(q << 1, l, mid, L, mid) + Query(q << 1 | 1, mid + 1, r, mid + 1, R); } int main() { n = getint(), m = getint(); T.root = T.cnt = 1; T.lf[1] = T.rf[1] = -1; T.ls[1] = 0, T.rs[1] = 1; for (int i = 1; i <= n; i++) Insert(1, 1, n, i, 1); for (int i = 1; i <= m; i++) { scanf("%s", opt); if (opt[0] == 'Q') { int l = getint(), r = getint(); printf("%d\n", Query(1, 1, n, l, r).plc); } else { int l = getint(), r = getint(), k = getint(); l = Query(1, 1, n, l, l).num; r = Query(1, 1, n, r, r).num; T.Add(T.root, l, r, 0, 1, k); T.Check(T.root, l, r); } } }
上一篇: 长的稀奇古怪的胡萝卜图片