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();
	}
}