欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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;
}