loj#6029. 「雅礼集训 2017 Day1」市场(线段树)
程序员文章站
2022-04-28 14:04:22
题意 "链接" Sol 势能分析。 除法是不能打标记的,所以只能暴力递归。这里我们加一个剪枝:如果区间内最大最小值的改变量都相同的话,就变成区间减。 这样复杂度是$(n + mlogn) logV$的。 简单的证明一下:如果没有加的话,每个节点会被除至多log次, 总会除4nlogn次,每次区间加会 ......
题意
sol
势能分析。
除法是不能打标记的,所以只能暴力递归。这里我们加一个剪枝:如果区间内最大最小值的改变量都相同的话,就变成区间减。
这样复杂度是\((n + mlogn) logv\)的。
简单的证明一下:如果没有加的话,每个节点会被除至多log次, 总会除4nlogn次,每次区间加会恢复log个点的势能函数,这样总递归次数就是\(nlog^2n\)。
下传标记的时候别忘了把min和max都更新一下
#include<bits/stdc++.h> #define pair pair<int, int> #define mp(x, y) make_pair(x, y) #define fi first #define se second #define ll long long #define ull unsigned long long #define fin(x) {freopen(#x".in","r",stdin);} #define fout(x) {freopen(#x".out","w",stdout);} using namespace std; const int maxn = 1e6 + 10, inf = 1e9 + 1; const double eps = 1e-9, pi = acos(-1); inline int read() { char c = getchar(); int x = 0, f = 1; 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; } int n, q, a[maxn]; ll mx[maxn], mn[maxn], add[maxn], sum[maxn], ll[maxn], rr[maxn]; #define ls k << 1 #define rs k << 1 | 1 void update(int k) { mx[k] = max(mx[ls], mx[rs]); mn[k] = min(mn[ls], mn[rs]); sum[k] = sum[ls] + sum[rs]; } void ps(int k, int v) { sum[k] += (rr[k] - ll[k] + 1) * v; mn[k] += v; mx[k] += v; add[k] += v; } void pushdown(int k) { if(!add[k]) return ; ps(ls, add[k]); ps(rs, add[k]); add[k] = 0; } void build(int k, int l, int r) { ll[k] = l; rr[k] = r; if(l == r) {sum[k] = mx[k] = mn[k] = a[l]; return ;} int mid = l + r >> 1; build(ls, l, mid); build(rs, mid + 1, r); update(k); } void add(int k, int l, int r, int ql, int qr, ll v) { if(ql <= l && r <= qr) {ps(k, v); return ;} int mid = l + r >> 1; pushdown(k); if(ql <= mid) add(ls, l, mid, ql, qr, v); if(qr > mid) add(rs, mid + 1, r, ql, qr, v); update(k); } ll get(ll x, int d) { return (x >= 0 ? x / d : (x - d + 1) / d); } void div(int k, int l, int r, int ql, int qr, ll v) { if(ql <= l && r <= qr && (mx[k] - get(mx[k], v) == mn[k] - get(mn[k], v))) { ps(k, get(mx[k], v) - mx[k]); return ; } pushdown(k); int mid = l + r >> 1; if(ql <= mid) div(ls, l, mid, ql, qr, v); if(qr > mid) div(rs, mid + 1, r, ql, qr, v); update(k); } ll min(int k, int l, int r, int ql, ll qr) { if(ql <= l && r <= qr) return mn[k]; int mid = l + r >> 1; pushdown(k); if(ql > mid) return min(rs, mid + 1, r, ql, qr); else if(qr <= mid) return min(ls, l, mid, ql, qr); else return min(min(ls, l, mid, ql, qr), min(rs, mid + 1, r, ql, qr)); } ll sum(int k, int l, int r, int ql, int qr) { if(ql <= l && r <= qr) return sum[k]; int mid = l + r >> 1; pushdown(k); if(ql > mid) return sum(rs, mid + 1, r, ql, qr); else if(qr <= mid) return sum(ls, l, mid, ql, qr); else return sum(ls, l, mid, ql, qr) + sum(rs, mid + 1, r, ql, qr); } signed main() { n = read(); q = read(); for(int i = 1; i <= n; i++) a[i] = read(); build(1, 1, n); while(q--) { int opt = read(), l = read() + 1, r = read() + 1; if(opt == 1) { int c = read(); add(1, 1, n, l, r, c); } else if(opt == 2) { int d = read(); div(1, 1, n, l, r, d); } else if(opt == 3) { cout << min(1, 1, n, l, r) << '\n'; } else { cout << sum(1, 1, n, l, r) << '\n'; } } return 0; }