题目描述 Description
有n个数和5种操作
add a b c：把区间[a,b]内的所有数都增加c
set a b c：把区间[a,b]内的所有数都设为c
sum a b：查询区间[a,b]的区间和
max a b：查询区间[a,b]的最大值
min a b：查询区间[a,b]的最小值
输入描述 Input Description
第一行两个整数n，m，第二行n个整数表示这n个数的初始值
接下来m行操作，同题目描述
输出描述 Output Description
对于所有的sum、max、min询问，一行输出一个答案
样例输入 Sample Input
10 6
3 9 2 8 1 7 5 0 4 6
add 4 9 4
set 2 6 2
add 3 8 2
sum 2 10
max 1 7
min 3 6
样例输出 Sample Output
49
11
4
数据范围及提示 Data Size & Hint
10%:1<n,m<=10
30%:1<n,m<=10000
100%:1<n,m<=100000
保证中间结果在long long(C/C++)、int64(pascal)范围内
长代码看了好理解
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <string>using namespace std; const int N = 1e5 + 10;#define oo 1423333339 #define LL long long #define gg 465432477struct Node{LL l, r, w, f, mx, mi, fg;bool qs; }T[N << 2]; LL n, m, answer, maxn, minn;inline LL read() {LL x = 0, f = 1; char c = getchar();while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f; }void imp(LL jd) {T[jd].w = T[jd << 1].w + T[jd << 1 | 1].w;T[jd].mx = max(T[jd << 1].mx, T[jd << 1 | 1].mx);T[jd].mi = min(T[jd << 1].mi, T[jd << 1 | 1].mi); }void down(LL jd) {if(T[jd].qs){T[jd << 1].f = 0;T[jd << 1].qs = 1;T[jd << 1].fg = T[jd].fg;T[jd << 1].w = (T[jd << 1].r - T[jd << 1].l + 1) * T[jd].fg;T[jd << 1 | 1].f = 0;T[jd << 1 | 1].qs = 1; T[jd << 1 | 1].fg = T[jd].fg; T[jd << 1 | 1].w = (T[jd << 1 | 1].r - T[jd << 1 | 1].l + 1) * T[jd].fg; T[jd << 1].mi = T[jd << 1].mx = T[jd << 1 | 1].mi= T[jd << 1 | 1].mx=T[jd].fg;T[jd].fg = 0; T[jd].qs = 0;}if(T[jd].f){T[jd << 1].f += T[jd].f;T[jd << 1].w += (T[jd << 1].r - T[jd << 1].l + 1) * T[jd].f;T[jd << 1].mi += T[jd].f; T[jd << 1].mx += T[jd].f;T[jd << 1 | 1].f += T[jd].f;T[jd << 1 | 1].w += (T[jd << 1 | 1].r - T[jd << 1 | 1].l + 1) * T[jd].f;T[jd << 1 | 1].mi += T[jd].f; T[jd << 1 | 1].mx += T[jd].f;T[jd].f = 0; }return ; }void build_tree(LL l, LL r, LL jd) {T[jd].l = l; T[jd].r = r;if(l == r){T[jd].w = read();T[jd].mx = T[jd].w;T[jd].mi = T[jd].w;return ;}LL mid = (l + r) >> 1;build_tree(l, mid, jd << 1);build_tree(mid + 1, r, jd << 1 | 1);imp(jd); }void Sec_g(LL l, LL r, LL jd, LL x, LL y, LL yj) {if(x <= l && r <= y) {T[jd].f += yj; T[jd].w += (T[jd].r - T[jd].l + 1) * yj; T[jd].mi += yj; T[jd].mx += yj;return ;}if(T[jd].f || T[jd].qs) down(jd);LL mid = (l + r) >> 1;if(x <= mid) Sec_g(l, mid, jd << 1, x, y, yj);if(y > mid) Sec_g(mid + 1, r, jd << 1 | 1, x, y, yj);imp(jd); }void Sec_set(LL l, LL r, LL jd, LL x, LL y, LL k) {if(x <= l && r <= y){T[jd].fg = k;T[jd].qs = 1;T[jd].w = (T[jd].r - T[jd].l + 1) * T[jd].fg; T[jd].mx = k; T[jd].mi = k; T[jd].f = 0;return ;}LL mid = (l + r ) >> 1;if(T[jd].f || T[jd].qs) down(jd);if(x <= mid)Sec_set(l, mid, jd << 1, x, y, k);if(y > mid)Sec_set(mid + 1, r, jd << 1 | 1, x, y, k);imp(jd); }void Sec_calc(LL l, LL r, LL jd, LL x, LL y) {if(x <= l && r <= y) {answer += T[jd].w; return;}if(T[jd].f || T[jd].qs) down(jd);LL mid = (l + r) >> 1;if(x <= mid)Sec_calc(l, mid, jd << 1, x, y);if(y > mid)Sec_calc(mid + 1, r, jd << 1 | 1, x, y); }void Sec_min(LL l, LL r, LL jd, LL x, LL y) {if(x <= l && r <= y){minn = min(minn, T[jd].mi); return ;}if(T[jd].f || T[jd].qs) down(jd);LL mid = (l + r) >> 1;if(x <= mid) Sec_min(l, mid, jd << 1, x, y);if(y > mid) Sec_min(mid + 1, r, jd << 1 | 1, x, y); }void Sec_max(LL l, LL r, LL jd, LL x, LL y) {if(x <= l && r <= y){maxn = max(maxn, T[jd].mx); return ;}if(T[jd].f || T[jd].qs) down(jd);LL mid = (l + r) >> 1;if(x <= mid) Sec_max(l, mid, jd << 1, x, y);if(y > mid) Sec_max(mid + 1, r, jd << 1 | 1, x, y); }int main() {n = read();m = read();build_tree(1, n, 1);for(LL i = 1; i <= m; i ++){string s;cin >> s;LL x = read();LL y = read();if(s == "add") {LL k = read();Sec_g(1, n, 1, x, y, k);continue;}if(s == "set"){LL k = read();Sec_set(1, n, 1, x, y, k);continue;}if(s == "sum"){answer = 0; Sec_calc(1, n, 1, x, y);printf("%lld\n", answer);continue;}if(s == "min"){minn = oo;Sec_min(1, n, 1, x, y);printf("%lld\n", minn);continue;}if(s == "max"){maxn = -oo;Sec_max(1, n, 1, x, y);printf("%lld\n", maxn);continue;}}return 0; } /* 10 6 3 9 2 8 1 7 5 0 4 6 add 4 9 4 set 2 6 2 add 3 8 2 sum 2 10 max 1 7 min 3 649 11 4 */
