Gemini Boy - ACM之路~
HDU 4699: Editor
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4699
题意就是模拟打字，要求支持以下操作：
- I x：在当前光标后面插入x
- D：删除光标前面一个字符
- L：光标向左移动一步
- R：光标向右移动一步
- Q k：插入前k个数字中子段和最大是多少。
这题可以用splay维护，比较简单的办法是用双向链表，维护一个ans数组，记录前i个ss数字中子段和最大是多少。对于L，R，D，I操作的时候记得更新ans数组就行了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
#include <list>
using namespace std;
const int maxn = 1001010;
const int inf = 0x3f3f3f3f;
struct ListNode {
ListNode *next;
ListNode *pre;
int key, sum;
};
ListNode nodes[maxn*2];
ListNode *p;
int C, id, ans[maxn];
int n, x;
char op[100];
void add(int key) {
ListNode *q = &nodes[C++];
q->sum = p->sum + key;
q->key = key;
q->pre = p;
q->next = p->next;
if (q->next != 0)
q->next->pre = q;
p->next = q;
p = p->next;
id++;
ans[id] = max(p->sum, ans[id-1]);
}
void del() {
if (p->pre == 0)
return ;
id--;
ListNode *q = &nodes[C++];
q = p->next;
p = p->pre;
if (q != 0)
q->pre = p;
p->next = q;
}
void left() {
if (p->pre == 0)
return ;
id--;
p = p->pre;
}
void right() {
if (p->next == 0)
return ;
int tmp = p->sum;
id++;
p = p->next;
p->sum = tmp + p->key;
ans[id] = max(p->sum, ans[id-1]);
}
void init() {
for (int i = 0; i < maxn; i++)
ans[i] = -inf;
C = 1; id = 0;
p = &nodes[0];
p->pre = 0;
p->next = 0;
p->sum = 0;
p->key = 0;
}
void work() {
for (int i = 0; i < n; i++) {
scanf("%s", op);
if (op[0] == 'I') {
scanf("%d", &x);
add(x);
} else if (op[0] == 'D') {
del();
} else if (op[0] == 'L') {
left();
} else if (op[0] == 'R') {
right();
} else {
scanf("%d", &x);
printf("%d\n", ans[x]);
}
}
}
int main() {
while (scanf("%d", &n) != EOF) {
init();
work();
}
return 0;
}
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 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();
}
}
坑向~
zoj 2334
bzoj 1293
bzoj 2752
bzoj 1782
bzoj 2783
bzoj 2762
bzoj 1935
bzoj 3411
bzoj 3686
bzoj 2653
bzoj 2116
bzoj 2584
bzoj 1018
bzoj 2827
bzoj 2658
poj 3580
bzoj 1758
bzoj 2329