Gemini Boy - ACM之路~
BZOJ 2752: [HAOI2012]高速公路(road) (线段树)
链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2752
概率背景的题，不过稍微想想，稍微推一推，就能得到公式。然后注意到只要用线段树维护3个sum就行了，sum1 费用和， sum2 下标乘以费用的和 sum3下标的平方乘以费用的和
PS：。。。在写线段树的时候被一个傻逼问题bug住了好久，，调了好久。好吧 我就是煞笔
2版线段树的代码。
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100100;
long long sumo[maxn], sump[maxn];
struct SegNode {
int left, right;
long long sum1, sum2, sum3;
long long add;
int mid() {
return (left + right) >> 1;
}
long long 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;
tree[idx].sum2 = tree[idx<<1].sum2 + tree[idx<<1|1].sum2;
tree[idx].sum3 = tree[idx<<1].sum3 + tree[idx<<1|1].sum3;
}
void pushDown(int idx) {
if (tree[idx].add) {
long long add = tree[idx].add;
int right1 = tree[idx<<1].right;
int left1 = tree[idx<<1].left;
int right2 = tree[idx<<1|1].right;
int left2 = tree[idx<<1|1].left;
tree[idx].add = 0;
tree[idx<<1].sum1 += tree[idx<<1].size() * add;
tree[idx<<1|1].sum1 += tree[idx<<1|1].size() * add;
tree[idx<<1].sum2 += (sumo[right1] - sumo[left1-1]) * add;
tree[idx<<1|1].sum2 += (sumo[right2] - sumo[left2-1]) * add;
tree[idx<<1].sum3 += (sump[right1] - sump[left1-1]) * add;
tree[idx<<1|1].sum3 += (sump[right2] - sump[left2-1]) * add;
tree[idx<<1].add += add;
tree[idx<<1|1].add += add;
}
}
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].add = 0;
if (left == right)
return ;
int mid = tree[idx].mid();
build(left, mid, idx<<1);
build(mid+1, right, idx<<1|1);
}
void update(int left, int right, int idx, long long value) {
if (tree[idx].left == left && tree[idx].right == right) {
tree[idx].add += value;
tree[idx].sum1 += tree[idx].size() * value;
tree[idx].sum2 += (sumo[right] - sumo[left-1]) * value;
tree[idx].sum3 += (sump[right] - sump[left-1]) * value;
return ;
}
pushDown(idx);
int mid = tree[idx].mid();
if (right <= mid)
update(left, right, idx<<1, value);
else if (left > mid)
update(left, right, idx<<1|1, value);
else {
update(left, mid, idx<<1, value);
update(mid+1, right, idx<<1|1, value);
}
pushUp(idx);
}
long long query(int left, int right, int idx, int L, int R) {
if (tree[idx].left == left && tree[idx].right == right) {
//printf("%d %d %d\n", idx, left, right);
return (R + L - 1) * tree[idx].sum2 - tree[idx].sum3 -
((long long)L * R - R) * tree[idx].sum1;
}
pushDown(idx);
int mid = tree[idx].mid();
if (right <= mid)
return query(left, right, idx<<1, L, R);
else if (left > mid)
return query(left, right, idx<<1|1, L, R);
else {
return (query(left, mid, idx<<1, L, R) + query(mid+1, right, idx<<1|1, L, R));
}
}
};
SegmentTree tree;
int N, M;
long long gcd(long long a, long long b) {
return b ? gcd(b, a % b) : a;
}
void init() {
memset(sumo, 0, sizeof(sumo));
memset(sump, 0, sizeof(sump));
for (int i = 1; i < maxn; i++)
sumo[i] = sumo[i-1] + i;
for (int i = 1; i < maxn; i++)
sump[i] = sump[i-1] + (long long)i * i;
scanf("%d %d", &N, &M);
tree.build(1, N, 1);
}
void work() {
char op[19];
for (int i = 0; i < M; i++) {
scanf("%s", op);
if (op[0] == 'C') {
int x, y;
long long z;
scanf("%d %d %lld", &x, &y, &z);
tree.update(x, y-1, 1, z);
} else {
int x, y;
scanf("%d %d", &x, &y);
long long tmp = tree.query(x, y, 1, x, y);
long long tem = (long long)(y - x + 1) * (y - x) / 2;
long long ans = gcd(tmp, tem);
printf("%lld/%lld\n", tmp / ans, tem / ans);
}
}
}
int main() {
init();
work();
return 0;
}
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100100;
long long sumo[maxn], sump[maxn];
struct SegNode {
int left, right;
long long sum1, sum2, sum3;
long long add;
};
struct SegmentTree {
SegNode tree[maxn*5];
void pushUp(int idx) {
tree[idx].sum1 = tree[idx<<1].sum1 + tree[idx<<1|1].sum1;
tree[idx].sum2 = tree[idx<<1].sum2 + tree[idx<<1|1].sum2;
tree[idx].sum3 = tree[idx<<1].sum3 + tree[idx<<1|1].sum3;
}
void pushDown(int idx, int left, int right) {
if (tree[idx].add) {
long long add = tree[idx].add;
tree[idx].add = 0;
tree[idx].sum1 += (right - left + 1) * add;
tree[idx].sum2 += (sumo[right] - sumo[left-1]) * add;
tree[idx].sum3 += (sump[right] - sump[left-1]) * add;
if (left == right) return ;
tree[idx<<1].add += add;
tree[idx<<1|1].add += add;
}
}
void update(int L, int R, int left, int right, int idx, long long value) {
pushDown(idx, L, R);
if (L >= left && R <= right) {
tree[idx].add += value;
return ;
}
int mid = (L + R) >> 1;
if (left <= mid)
update(L, mid, left, right, idx<<1, value);
if (right >= mid+1)
update(mid+1, R, left, right, idx<<1|1, 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) {
printf("%d %d %d\n", idx, left, right);
return (right + left - 1) * tree[idx].sum2 - tree[idx].sum3 -
((long long)left * right - right) * tree[idx].sum1;
}
int mid = (L + R) >> 1;
long long ans = 0;
if (left <= mid)
ans += query(L, mid, left, right, idx<<1);
if (right >= mid + 1)
ans += query(mid+1, R, left, right, idx<<1|1);
return ans;
}
};
SegmentTree tree;
int N, M;
long long gcd(long long a, long long b) {
return b ? gcd(b, a % b) : a;
}
void init() {
memset(sumo, 0, sizeof(sumo));
memset(sump, 0, sizeof(sump));
for (int i = 1; i < maxn; i++)
sumo[i] = sumo[i-1] + i;
for (int i = 1; i < maxn; i++)
sump[i] = sump[i-1] + (long long)i * i;
scanf("%d %d", &N, &M);
}
void work() {
char op[19];
for (int i = 0; i < M; i++) {
scanf("%s", op);
if (op[0] == 'C') {
int x, y;
long long z;
scanf("%d %d %lld", &x, &y, &z);
tree.update(1, N, x, y-1, 1, z);
} else {
int x, y;
scanf("%d %d", &x, &y);
long long tmp = tree.query(1, N, x, y, 1);
long long tem = (long long)(y - x + 1) * (y - x) / 2;
long long ans = gcd(tmp, tem);
printf("%lld/%lld\n\n", tmp / ans, tem / ans);
}
}
}
int main() {
init();
work();
return 0;
}
BZOJ 3251: 树上三角形
链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3251
题意就是给一棵树，点权，然后查询一条链上是否有3个点的点权能组成一个三角形。
注意到三角形任意2边之和大于第三边，然后最坏的情况类似于斐波那契数列，大约4 50左右的时候，就会超int。所以当链的长度大于45的时候，返回true，否则就暴力判断是否可行。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 101110;
int N, Q;
vector<int> next[maxn];
long long val[maxn];
int par[maxn], dep[maxn];
void dfs(int u) {
for (int i = 0; i < next[u].size(); i++) {
int v = next[u][i];
//if (dep[v]) continue;
dep[v] = dep[u] + 1;
dfs(v);
}
}
bool check(int x, int y) {
int cnt = 0;
long long num[55];
for ( ; dep[x] > dep[y]; x = par[x]) {
num[cnt++] = val[x];
if (cnt > 45) return true;
}
for ( ; x != y; x = par[x], y = par[y]) {
num[cnt++] = val[x];
num[cnt++] = val[y];
if (cnt > 45) return true;
}
num[cnt++] = val[y];
if (cnt < 3)
return false;
sort(num, num + cnt);
for (int i = 0; i + 2 < cnt; i++) {
if (num[i] + num[i+1] > num[i+2])
return true;
}
return false;
}
void init() {
for (int i = 0; i < maxn; i++) {
next[i].clear();
dep[i] = 0;
val[i] = 0;
par[i] = 0;
}
par[1] = -1;
scanf("%d %d", &N, &Q);
for (int i = 1; i <= N; i++)
scanf("%d", &val[i]);
for (int i = 1; i < N; i++) {
int x, y;
scanf("%d %d", &x, &y);
par[y] = x;
next[x].push_back(y);
}
dep[1] = 1;
dfs(1);
}
void work() {
for (int i = 0; i < Q; i++) {
int opt, x, y;
scanf("%d %d %d", &opt, &x, &y);
if (opt == 1)
val[x] = y;
else {
if (dep[x] < dep[y])
swap(x, y);
if (x == y || x == par[y] || y == par[x]) {
puts("N");
continue;
}
if (check(x, y) == true)
puts("Y");
else puts("N");
}
}
}
int main() {
init();
work();
return 0;
}
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();
}
}