题解 - Gemini Boy - ACM之路~
BZOJ 2733: [HNOI2012]永无乡(平衡树启发式合并)
链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2733
这题我是用treap做的,每个岛代表一个节点,每个节点维护一颗treap,然后节点之间用并查集维护,合并的时候比较俩个节点在并查集中的根的treap的节点个数,从小的向大的暴力insert进去,就行了。0.0
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <map> #include <vector> #include <set> using namespace std; template <class T> inline void scan(T &ret) { char c; ret = 0; while ((c = getchar()) < '0' || c > '9') ; while (c >= '0' && c <= '9') ret = ret * 10 + (c - '0'), c = getchar(); } const int maxn = 100100; struct TreeNode { TreeNode *L, *R; int num; int size; int pri; int key; }; TreeNode nodes[maxn*30], stack[maxn*5]; TreeNode *null; int C, Top; void init() { C = 0; Top = 0; null = &nodes[C++]; null->L = null->R = null; null->pri = -0x7FFFFFFF; null->size = 0; null->key = 0; null->num = 0; } struct Treap { TreeNode* root; vector<TreeNode*> list; void init() { root = null; } void toArrayList(TreeNode* root) { if (root != null) { toArrayList(root->L); list.push_back(root); toArrayList(root->R); } } TreeNode* newNode(int key, int num) { TreeNode* ret; if (Top) ret = &stack[--Top]; else ret = &nodes[++C]; ret->L = ret->R = null; ret->key = key; ret->pri = rand(); ret->num = num; ret->size = num; return ret; } TreeNode* merge(TreeNode* small, TreeNode* large) { if (small == null) return large; if (large == null) return small; if (small->pri < large->pri) { small->R = merge(small->R, large); pushUp(small); return small; } else { large->L = merge(small, large->L); pushUp(large); return large; } } pair<TreeNode*, TreeNode*> split(TreeNode* root, int key) { pair<TreeNode*, TreeNode*> tmp; if (root == null) { tmp = make_pair(null, null); return tmp; } if (key <= root->key) { tmp = split(root->L, key); root->L = tmp.second; pushUp(root); tmp.second = root; return tmp; } else { tmp = split(root->R, key); root->R = tmp.first; pushUp(root); tmp.first = root; return tmp; } } TreeNode* upperBound(TreeNode* root, int key) { TreeNode* ans = null; TreeNode* i = root; while (i != null) { if (key < i->key) { ans = i; i = i->L; } else { i = i->R; } } return ans; } TreeNode* lowerBound(TreeNode* root, int key) { TreeNode* ans = null; TreeNode* i = root; while (i != null) { if (key < i->key) { i = i->L; } else { ans = i; i = i->R; } } return ans; } bool contains(TreeNode* root, int key) { if (root == null) return false; if (key == root->key) return true; else if (key < root->key) return contains(root->L, key); else return contains(root->R, key); } void insert(TreeNode* root, int key, int num) { if (key < root->key) insert(root->L, key, num); else if (key == root->key) root->num += num; else insert(root->R, key, num); pushUp(root); } void insert(int key, int num) { if (contains(root, key)) { insert(root, key, num); return ; } pair<TreeNode*, TreeNode*> tmp = split(root, key); TreeNode* node = newNode(key, num); root = merge(merge(tmp.first, node), tmp.second); } void del(int key) { pair<TreeNode*, TreeNode*> tmp = split(root, key); TreeNode* node = upperBound(tmp.second, key); if (node == null) root = tmp.first; else root = merge(tmp.first, split(tmp.second, node->key).second); } void del(TreeNode* root, int key) { if (!contains(root, key)) return ; if (key < root->key) del(root->L, key); else if (key == root->key) { root->num--; if (root->num == 0) del(key); } else { del(root->R, key); } pushUp(root); } TreeNode* select(TreeNode* root, int k) { if (k <= root->L->size) return select(root->L, k); else if (k >= root->L->size + 1 && k <= root->L->size + root->num) return root; else return select(root->R, k-root->L->size-root->num); } int getMin(TreeNode* root, int key) { if (key < root->key) return getMin(root->L, key); else if (key == root->key) return root->L->size + root->num; else return root->L->size + root->num + getMin(root->R, key); } int getMax(TreeNode* root, int key) { if (key < root->key) return root->R->size + root->num + getMax(root->L, key); else if (key == root->key) return root->R->size + root->num; else return getMax(root->R, key); } int size() { return root->size; } void visit(TreeNode* root) { if (root != null) { printf("key: %d num: %d size: %d\n", root->key, root->num, root->size); visit(root->L); visit(root->R); } } void pushUp(TreeNode* x) { x->size = x->L->size + x->R->size + x->num; } }; Treap tree[maxn]; char op[10]; int n, m, q, hash[maxn], arr[maxn]; int par[maxn]; int find(int x) { if (par[x] != x) par[x] = find(par[x]); return par[x]; } void merge(int x, int y) { int px = find(x); int py = find(y); if (px != py) { if (tree[px].size() < tree[py].size()) { par[px] = py; tree[px].list.clear(); tree[px].toArrayList(tree[px].root); for (int i = 0; i < tree[px].list.size(); i++) { TreeNode* tmp = tree[px].list[i]; tree[py].insert(tmp->key, tmp->num); } } else { par[py] = px; tree[py].list.clear(); tree[py].toArrayList(tree[py].root); for (int i = 0; i < tree[py].list.size(); i++) { TreeNode* tmp = tree[py].list[i]; tree[px].insert(tmp->key, tmp->num); } } } } int query(int x, int k) { int px = find(x); if (tree[px].size() < k) return -1; else return tree[px].select(tree[px].root, k)->key; } void work() { init(); scan(n); scan(m); // scanf("%d %d", &n, &m); for (int i = 0; i <= n; i++) tree[i].init(); for (int i = 0; i <= n; i++) par[i] = i; for (int i = 1; i <= n; i++) { scan(arr[i]); // scanf("%d", &arr[i]); hash[arr[i]] = i; } for (int i = 1; i <= n; i++) tree[i].insert(arr[i], 1); for (int i = 1; i <= m; i++) { int x, y; scan(x); scan(y); // scanf("%d %d", &x, &y); merge(x, y); } } void run() { scanf("%d", &q); for (int i = 1; i <= q; i++) { int x, y; scanf("%s", op); scan(x); scan(y); // scanf("%s %d %d", op, &x, &y); if (op[0] == 'Q') { int ans = query(x, y); if (ans != -1) ans = hash[ans]; printf("%d\n", ans); } else { merge(x, y); } } } int main() { work(); run(); }
BZOJ 1798: [Ahoi2009]Seq 维护序列seq
http://www.lydsy.com/JudgeOnline/problem.php?id=1798
题意很简单,就是维护区间和,然后区间加一个值,区间乘以一个值。
做法就是维护 a * x + b 这个统计量,别的就是普通的线段树~
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; const int maxn = 101000; long long value[maxn], mod; struct SegNode { int left, right; long long sum, add, mul; int mid() { return (left + right) >> 1; } int size() { return right - left + 1; } }; struct SegmentTree { SegNode tree[maxn*5]; void pushUp(int idx) { tree[idx].sum = (tree[idx<<1].sum + tree[idx<<1|1].sum) % mod; } void pushDown(int idx) { tree[idx<<1].add = (tree[idx].mul % mod * tree[idx<<1].add % mod + tree[idx].add) % mod; tree[idx<<1|1].add = (tree[idx].mul % mod * tree[idx<<1|1].add % mod + tree[idx].add) % mod; tree[idx<<1].mul = tree[idx<<1].mul % mod * tree[idx].mul % mod; tree[idx<<1|1].mul = tree[idx<<1|1].mul % mod * tree[idx].mul % mod; tree[idx<<1].sum = (tree[idx<<1].sum % mod * tree[idx].mul % mod + tree[idx<<1].size() * tree[idx].add % mod) % mod; tree[idx<<1|1].sum = (tree[idx<<1|1].sum % mod * tree[idx].mul % mod + tree[idx<<1|1].size() * tree[idx].add % mod) % mod; tree[idx].add = 0; tree[idx].mul = 1; } void build(int left, int right, int idx) { tree[idx].left = left; tree[idx].right = right; tree[idx].sum = 0; tree[idx].mul = 1; tree[idx].add = 0; if (left == right) { tree[idx].sum = value[left] % mod; return ; } int mid = tree[idx].mid(); build(left, mid, idx<<1); build(mid+1, right, idx<<1|1); pushUp(idx); } void update(int left, int right, int idx, int opt, long long val) { if (tree[idx].left == left && tree[idx].right == right) { if (opt == 1) { tree[idx].add = (tree[idx].add + val) % mod; tree[idx].sum = (tree[idx].sum + tree[idx].size() % mod * val) % mod; } else { tree[idx].add = tree[idx].add % mod * val % mod; tree[idx].mul = tree[idx].mul % mod * val % mod; tree[idx].sum = tree[idx].sum % mod * val % mod; } return ; } pushDown(idx); int mid = tree[idx].mid(); if (right <= mid) update(left, right, idx<<1, opt, val); else if (left > mid) update(left, right, idx<<1|1, opt, val); else { update(left, mid, idx<<1, opt, val); update(mid+1, right, idx<<1|1, opt, val); } pushUp(idx); } long long query(int left, int right, int idx) { if (tree[idx].left == left && tree[idx].right == right) { return tree[idx].sum % mod; } pushDown(idx); int mid = tree[idx].mid(); if (right <= mid) return query(left, right, idx<<1); else if (left > mid) return query(left, right, idx<<1|1); else { return (query(left, mid, idx<<1) % mod + query(mid+1, right, idx<<1|1)); } } }; SegmentTree tree; int n, m; void init() { scanf("%d %lld", &n, &mod); for (int i = 1; i <= n; i++) scanf("%lld", &value[i]); tree.build(1, n, 1); } void work() { scanf("%d", &m); for (int i = 1; i <= m; i++) { int opt, x, y; long long val; scanf("%d", &opt); if (opt != 3) { scanf("%d %d %lld", &x, &y, &val); tree.update(x, y, 1, 3-opt, val % mod); } else { scanf("%d %d", &x, &y); printf("%lld\n", tree.query(x, y, 1) % mod); } } } int main() { init(); work(); }
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <vector> using namespace std; const int maxn = 101000; long long value[maxn], mod; struct SegNode { int left, right; long long sum, add, mul; }; struct SegmentTree { SegNode tree[maxn*5]; void pushUp(int idx) { tree[idx].sum = tree[idx<<1].sum + tree[idx<<1|1].sum; } void pushDown(int idx, int left, int right) { long long add = tree[idx].add; long long mul = tree[idx].mul; tree[idx].sum = (tree[idx].sum % mod * tree[idx].mul % mod + (right - left + 1) * tree[idx].add % mod) % mod; tree[idx].add = 0; tree[idx].mul = 1; if (left == right) return ; tree[idx<<1].add = (mul % mod * tree[idx<<1].add % mod + add) % mod; tree[idx<<1|1].add = (mul % mod * tree[idx<<1|1].add % mod + add) % mod; tree[idx<<1].mul = tree[idx<<1].mul % mod * mul % mod; tree[idx<<1|1].mul = tree[idx<<1|1].mul % mod * mul % mod; } void build(int left, int right, int idx) { tree[idx].left = left; tree[idx].right = right; tree[idx].sum = 0; tree[idx].mul = 1; tree[idx].add = 0; if (left == right) { tree[idx].sum = value[left] % mod; return ; } int mid = (tree[idx].right + tree[idx].left) >> 1; build(left, mid, idx<<1); build(mid+1, right, idx<<1|1); pushUp(idx); } void update(int L, int R, int left, int right, int idx, int opt, long long value) { pushDown(idx, L, R); if (L >= left && R <= right) { if (opt == 1) { tree[idx].add = (tree[idx].add + value) % mod; } else { tree[idx].add = tree[idx].add % mod * value % mod; tree[idx].mul = tree[idx].mul % mod * value % mod; } return ; } int mid = (L + R) >> 1; if (left <= mid) update(L, mid, left, right, idx<<1, opt, value); if (right >= mid+1) update(mid+1, R, left, right, idx<<1|1, opt, value); pushDown(idx<<1, L, mid); pushDown(idx<<1|1, mid+1, R); pushUp(idx); } long long query(int L, int R, int left, int right, int idx) { pushDown(idx, L, R); if (L >= left && R <= right) { return tree[idx].sum % mod; } int mid = (L + R) >> 1; long long ans = 0; if (left <= mid) ans = (ans + query(L, mid, left, right, idx<<1)) % mod; if (right >= mid + 1) ans = (ans + query(mid+1, R, left, right, idx<<1|1)) % mod; return ans; } }; SegmentTree tree; int n, m; void init() { scanf("%d %lld", &n, &mod); for (int i = 1; i <= n; i++) { scanf("%lld", &value[i]); } tree.build(1, n, 1); } void work() { scanf("%d", &m); for (int i = 1; i <= m; i++) { int opt, x, y; long long val; scanf("%d", &opt); if (opt != 3) { scanf("%d %d %lld", &x, &y, &val); tree.update(1, n, x, y, 1, 3-opt, val % mod); } else { scanf("%d %d", &x, &y); printf("%lld\n", tree.query(1, n, x, y, 1) % mod); } } } int main() { init(); work(); }
HDU 4578:http://acm.hdu.edu.cn/showproblem.php?pid=4578
这里还有道加强版,维护区间1次方和,2次方和,3次方和,区间加一个数,乘一个数,赋值。
更新的做法类似,要注意特殊处理赋值操作,赋值操作相当于a=1,b=0。
然后对于查询,其实2次方和,3次方和都可以展开来搞~
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; const int maxn = 100100; const int mod = 10007; struct SegNode { int left, right; int sum1, sum2, sum3; int add, mul, set; int mid() { return (left + right) >> 1; } int size() { return right - left + 1; } }; struct SegmentTree { SegNode tree[maxn*5]; void pushUp(int idx) { tree[idx].sum1 = (tree[idx<<1].sum1 + tree[idx<<1|1].sum1) % mod; tree[idx].sum2 = (tree[idx<<1].sum2 + tree[idx<<1|1].sum2) % mod; tree[idx].sum3 = (tree[idx<<1].sum3 + tree[idx<<1|1].sum3) % mod; } void pushDown(int idx) { if (tree[idx].set != 0) { int set1 = tree[idx].set % mod; int set2 = set1 % mod * set1 % mod; int set3 = set2 % mod * set1 % mod; tree[idx<<1].set = set1; tree[idx<<1|1].set = set1; tree[idx<<1].add = 0; tree[idx<<1|1].add = 0; tree[idx<<1].mul = 1; tree[idx<<1|1].mul = 1; tree[idx<<1].sum1 = tree[idx<<1].size() * set1 % mod; tree[idx<<1|1].sum1 = tree[idx<<1|1].size() * set1 % mod; tree[idx<<1].sum2 = tree[idx<<1].size() * set2 % mod; tree[idx<<1|1].sum2 = tree[idx<<1|1].size() * set2 % mod; tree[idx<<1].sum3 = tree[idx<<1].size() * set3 % mod; tree[idx<<1|1].sum3 = tree[idx<<1|1].size() * set3 % mod; tree[idx].set = 0; } int mul1 = tree[idx].mul % mod; int mul2 = mul1 % mod * mul1 % mod; int mul3 = mul2 % mod * mul1 % mod; int add1 = tree[idx].add % mod; int add2 = add1 % mod * add1 % mod; int add3 = add2 % mod * add1 % mod; tree[idx<<1].add = (tree[idx].mul % mod * tree[idx<<1].add % mod + tree[idx].add) % mod; tree[idx<<1|1].add = (tree[idx].mul % mod * tree[idx<<1|1].add % mod + tree[idx].add) % mod; tree[idx<<1].mul = tree[idx<<1].mul % mod * tree[idx].mul % mod; tree[idx<<1|1].mul = tree[idx<<1|1].mul % mod * tree[idx].mul % mod; int sum1 = tree[idx<<1].sum1; int sum2 = tree[idx<<1].sum2; int sum3 = tree[idx<<1].sum3; int size = tree[idx<<1].size(); tree[idx<<1].sum1 = (sum1 % mod * mul1 % mod + size % mod * add1 % mod) % mod; tree[idx<<1].sum2 = (sum2 % mod * mul2 % mod + 2 * add1 % mod * mul1 % mod * sum1 % mod + size % mod * add2 % mod) % mod; tree[idx<<1].sum3 = (mul3%mod*sum3%mod + 3*mul2%mod*add1%mod*sum2%mod + 3*mul1%mod*add2%mod*sum1%mod + size%mod*add3%mod) % mod; sum1 = tree[idx<<1|1].sum1; sum2 = tree[idx<<1|1].sum2; sum3 = tree[idx<<1|1].sum3; size = tree[idx<<1|1].size(); tree[idx<<1|1].sum1 = (sum1 % mod * mul1 % mod + size % mod * add1 % mod) % mod; tree[idx<<1|1].sum2 = (sum2 % mod * mul2 % mod + 2 * add1 % mod * mul1 % mod * sum1 % mod + size % mod * add2 % mod) % mod; tree[idx<<1|1].sum3 = (mul3%mod*sum3%mod + 3*mul2%mod*add1%mod*sum2%mod + 3*mul1%mod*add2%mod*sum1%mod + size%mod*add3%mod) % mod; tree[idx].add = 0; tree[idx].mul = 1; } void build(int left, int right, int idx) { tree[idx].left = left; tree[idx].right = right; tree[idx].sum1 = 0; tree[idx].sum2 = 0; tree[idx].sum3 = 0; tree[idx].set = 0; tree[idx].mul = 1; tree[idx].add = 0; if (left == right) return ; int mid = tree[idx].mid(); build(left, mid, idx<<1); build(mid+1, right, idx<<1|1); pushUp(idx); } void update(int left, int right, int idx, int opt, int val) { if (tree[idx].left == left && tree[idx].right == right) { int val1 = val % mod; int val2 = val1 % mod * val1 % mod; int val3 = val2 % mod * val1 % mod; int sum1 = tree[idx].sum1; int sum2 = tree[idx].sum2; int sum3 = tree[idx].sum3; int size = tree[idx].size(); if (opt == 1) { tree[idx].add = (tree[idx].add + val1 % mod) % mod; tree[idx].sum1 = (sum1 + size * val1 % mod) % mod; tree[idx].sum2 = (sum2 + 2 * sum1 % mod * val1 % mod + size % mod * val2 % mod) % mod; tree[idx].sum3 = (sum3 + 3 * sum2 % mod * val1 % mod + 3 * sum1 % mod * val2 % mod + size % mod * val3 % mod) % mod; } else if (opt == 2) { tree[idx].add = tree[idx].add * val1 % mod; tree[idx].mul = tree[idx].mul * val1 % mod; tree[idx].sum1 = sum1 % mod * val1 % mod; tree[idx].sum2 = sum2 % mod * val2 % mod; tree[idx].sum3 = sum3 % mod * val3 % mod; } else { tree[idx].add = 0; tree[idx].mul = 1; tree[idx].set = val1; tree[idx].sum1 = size % mod * val1 % mod; tree[idx].sum2 = size % mod * val2 % mod; tree[idx].sum3 = size % mod * val3 % mod; } return ; } pushDown(idx); int mid = tree[idx].mid(); if (right <= mid) update(left, right, idx<<1, opt, val); else if (left > mid) update(left, right, idx<<1|1, opt, val); else { update(left, mid, idx<<1, opt, val); update(mid+1, right, idx<<1|1, opt, val); } pushUp(idx); } int query(int left, int right, int idx, int opt) { if (tree[idx].left == left && tree[idx].right == right) { if (opt == 1) return tree[idx].sum1; else if (opt == 2) return tree[idx].sum2; else return tree[idx].sum3; } pushDown(idx); int mid = tree[idx].mid(); if (right <= mid) return query(left, right, idx<<1, opt); else if (left > mid) return query(left, right, idx<<1|1, opt); else { return (query(left, mid, idx<<1, opt) % mod + query(mid+1, right, idx<<1|1, opt)) % mod; } } }; SegmentTree tree; int N, M; void work() { tree.build(1, N, 1); int x, y, val, opt; for (int i = 0; i < M; i++) { scanf("%d %d %d %d", &opt, &x, &y, &val); if (opt == 4) printf("%d\n", tree.query(x, y, 1, val)); else tree.update(x, y, 1, opt, val); } } int main() { while (scanf("%d %d", &N, &M) != EOF) { if (N == 0 && M == 0) break; work(); } }
POI X
Codeforces有质量水题集锦
Codeforces 280B: Maximum Xor Secondary
链接:http://codeforces.com/problemset/problem/280/B
题意:给定一个序列,求对于任意L,R,在LR之间最大值与严格次大值异或值最大是多少。
做法:维护一个优先序列,可以证明每个元素最多只会进队一次出队一次,所以复杂度是O(n)的。
代码君:http://codeforces.com/contest/280/submission/3852565
Codeforces 280C: Game on Tree
链接:http://codeforces.com/contest/280/problem/C
题意:给一棵树,每次随机的删除一个结点和这个结点的子树,问删除整个树期望要删多少次
做法:每个结点的depth的倒数和即为最终结果,(不会证明)
代码君:http://codeforces.com/contest/280/submission/3852624
线段树水题集锦
SPOJ GSS1 && SPOJ GSS3
链接:http://www.spoj.com/problems/GSS1/ http://www.spoj.com/problems/GSS3/
题意:GSS1和GSS3一样query都是区间最大连续和,只不过GSS3有个单点update罢了
做法:维护sum(区间和),maxSum(区间最大连续和),maxLeft(左儿子区间最大连续和),maxRight(右儿子区间最大连续和)
代码君:GSS1:http://ideone.com/5tepgk GSS3:http://ideone.com/MsopAu
SPOJ FREQUENT
链接:http://www.spoj.com/problems/FREQUENT/
题意:给个不下降序列,无update,query是求区间重复出现最多的数
做法:注意到是不下降序列,那么这个问题就转化成求区间连续相同序列的长度,因为是不下降的,所以不用维护区间最左和最右的值,可以只维护maxLen,leftLen,rightLen。
SPOJ