比较有价值
#include#include #include #include #include #include using namespace std;const int N = 1e5 + 10;#define oo 1423333339#define LL long long#define gg 465432477#define lson jd << 1#define rson jd << 1 | 1struct 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[lson].w + T[rson].w; T[jd].mx = max(T[lson].mx, T[rson].mx); T[jd].mi = min(T[lson].mi, T[rson].mi);}void down(LL jd) { if(T[jd].qs) { T[lson].f = 0; T[lson].qs = 1; T[lson].fg = T[jd].fg; T[lson].w = (T[lson].r - T[lson].l + 1) * T[jd].fg; T[rson].f = 0; T[rson].qs = 1; T[rson].fg = T[jd].fg; T[rson].w = (T[rson].r - T[rson].l + 1) * T[jd].fg; T[lson].mi = T[lson].mx = T[rson].mi= T[rson].mx=T[jd].fg; T[jd].fg = 0; T[jd].qs = 0; } if(T[jd].f) { T[lson].f += T[jd].f; T[lson].w += (T[lson].r - T[lson].l + 1) * T[jd].f; T[lson].mi += T[jd].f; T[lson].mx += T[jd].f; T[rson].f += T[jd].f; T[rson].w += (T[rson].r - T[rson].l + 1) * T[jd].f; T[rson].mi += T[jd].f; T[rson].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, lson); build_tree(mid + 1, r, rson); 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, lson, x, y, yj); if(y > mid) Sec_g(mid + 1, r, rson, 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, lson, x, y, k); if(y > mid) Sec_set(mid + 1, r, rson, 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, lson, x, y); if(y > mid) Sec_calc(mid + 1, r, rson, 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, lson, x, y); if(y > mid) Sec_min(mid + 1, r, rson, 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, lson, x, y); if(y > mid) Sec_max(mid + 1, r, rson, 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;}