BZOJ 1798: [Ahoi2009]Seq 维护序列seq - Gemini Boy - ACM之路~
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();
}
}
2021年9月05日 18:23
We have sell some products of different custom boxes.it is very useful and very low price please visits this site thanks and please share this post with your friends. m4ufree.tv
2021年9月28日 01:33
Howdy, I discovered your blog per Google bit searching for such really enlightening concerning other than your show sees genuinely goliath for me. ไฮโลออนไลน์
2021年9月30日 02:22
Howdy, I discovered your blog per Google bit searching for such really enlightening concerning other than your show sees genuinely goliath for me. star vegas slot
2021年10月01日 00:24
This is colossally goliath, yet focal towards as shown by a general viewpoint snap this baffling backlink: บาคาร่า sagaming
2021年10月02日 18:42
I can propose on an inconceivably key level bobbling and astoundingly gifted tips, fittingly see it: metamorphosis literary agency
2021年10月03日 00:05
I'm enthused about such subjects so I will address page where it is cool portrayed. หวยฮานอย
2021年10月06日 20:22
An fascinating discussion is value comment. I think that it is best to write extra on this matter, it won’t be a taboo topic however generally people are not enough to talk on such topics. To the next. Cheers สล็อตออนไลน์
2021年10月07日 22:02
Thank you for the update, very nice site.. soaptoday
2021年10月09日 22:20
Wow, cool post. I'd like to write like this too - taking time and real hard work to make a great article... but I put things off too much and never seem to get started. Thanks though. สล็อต 888
2021年10月22日 12:04
I truly respect this focal post that you have obliged us. I ensure this would be monster for a goliath part of people. 카지노사이트
2022年1月21日 02:07
After a short time you'll find what is head, everything gives a url to the pulling in page: https://twitchviral.com/blog/what-is-twitch/
2022年2月17日 01:55
Would by far have the choice to make on faint spot interests! Welcome to here you'll find how it should look. lottery post
2022年6月13日 18:25
Howdy, I discovered your blog per Google bit searching for such really enlightening concerning other than your show sees genuinely goliath for me. home goods