【题解】picks loves segment tree I & II 吉司机线段树

DimitryL 讲的好啊

偷懒警告

对于 picks loves segment tree II：

代码（似乎 Remmina 的代码都跑得挺快的）：

picks loves segment tree I

#include <bits/stdc++.h>

#define NS (500005)
#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, A[NS];

struct N {int m1, m2, cnt; LL sum;} e[NS << 2];

void tag(int a, int d)
{
    e[a].sum -= 1ll * (e[a].m1 - d) * e[a].cnt, e[a].m1 = d;
}

void pup(int a)
{
    int l = LS(a), r = RS(a);
    e[a].sum = e[l].sum + e[r].sum;
    if (e[l].m1 == e[r].m1)
    {
        e[a].m1 = e[l].m1, e[a].cnt = e[l].cnt + e[r].cnt;
        e[a].m2 = max(e[l].m2, e[r].m2);
        return;
    }
    if (e[l].m1 < e[r].m1) swap(l, r);
    e[a].m1 = e[l].m1, e[a].cnt = e[l].cnt, e[a].m2 = max(e[r].m1, e[l].m2);
}

void pdown(int a)
{
    int l = LS(a), r = RS(a);
    if (e[a].m1 < e[l].m1) tag(l, e[a].m1);
    if (e[a].m1 < e[r].m1) tag(r, e[a].m1);
}

void Build(int l, int r, int a)
{
    if (l == r)
    {
        e[a].sum = e[a].m1 = A[l], e[a].m2 = INT_MIN, e[a].cnt = 1;
        return;
    }
    int mid = (l + r) >> 1;
    Build(l, mid, LS(a)), Build(mid + 1, r, RS(a)), pup(a);
}

void Update(int l, int r, int d, int L, int R, int a)
{
    if (d >= e[a].m1) return;
    if (l <= L && R <= r && d > e[a].m2) {tag(a, d); return;}
    pdown(a);
    int Mid = (L + R) >> 1;
    if (l <= Mid) Update(l, r, d, L, Mid, LS(a));
    if (r > Mid) Update(l, r, d, Mid + 1, R, RS(a));
    pup(a);
}

LL Query(int l, int r, int L, int R, int a)
{
    if (l <= L && R <= r) return e[a].sum;
    pdown(a);
    LL res = 0; int Mid = (L + R) >> 1;
    if (l <= Mid) res = Query(l, r, L, Mid, LS(a));
    if (r > Mid) res += Query(l, r, Mid + 1, R, RS(a));
    return res;
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    for (int i = 1; i <= n; i += 1) IN(A[i]);
    Build(1, n, 1);
    for (int C = 1, o, a, b, c; C <= m; C += 1)
    {
        IN(o), IN(a), IN(b);
        if (o) IN(c), Update(a, b, c, 1, n, 1);
        else printf("%lld\n", Query(a, b, 1, n, 1));
    }
    return 0;
}

picks loves segment tree II

#include <bits/stdc++.h>

#define NS (500005)
#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, A[NS];

struct N {LL m1, m2, sum, tag; int cnt;} e[NS << 2];

void tmin(int a, LL d)
{
    e[a].sum -= 1ll * (e[a].m1 - d) * e[a].cnt, e[a].m1 = d;
}

void tadd(int a, int l, LL d)
{
    e[a].m1 += d, e[a].m2 += d;
    e[a].sum += 1ll * l * d, e[a].tag += d;
}

void pup(int a)
{
    int l = LS(a), r = RS(a);
    e[a].sum = e[l].sum + e[r].sum;
    if (e[l].m1 == e[r].m1)
    {
        e[a].m1 = e[l].m1, e[a].cnt = e[l].cnt + e[r].cnt;
        e[a].m2 = max(e[l].m2, e[r].m2);
        return;
    }
    if (e[l].m1 < e[r].m1) swap(l, r);
    e[a].m1 = e[l].m1, e[a].cnt = e[l].cnt, e[a].m2 = max(e[r].m1, e[l].m2);
}

void pdown(int L, int R, int a)
{
    int l = LS(a), r = RS(a);
    if (e[a].tag)
    {
        int Mid = (L + R) >> 1;
        tadd(l, Mid - L + 1, e[a].tag), tadd(r, R - Mid, e[a].tag);
        e[a].tag = 0;
    }
    if (e[a].m1 < e[l].m1) tmin(l, e[a].m1);
    if (e[a].m1 < e[r].m1) tmin(r, e[a].m1);
}

void Build(int l, int r, int a)
{
    if (l == r)
    {
        e[a].sum = e[a].m1 = A[l], e[a].m2 = -1e17, e[a].cnt = 1;
        return;
    }
    int mid = (l + r) >> 1;
    Build(l, mid, LS(a)), Build(mid + 1, r, RS(a)), pup(a);
}

void Up_Min(int l, int r, int d, int L, int R, int a)
{
    if (d >= e[a].m1) return;
    if (l <= L && R <= r && d > e[a].m2) {tmin(a, d); return;}
    pdown(L, R, a);
    int Mid = (L + R) >> 1;
    if (l <= Mid) Up_Min(l, r, d, L, Mid, LS(a));
    if (r > Mid) Up_Min(l, r, d, Mid + 1, R, RS(a));
    pup(a);
}

void Up_Add(int l, int r, int d, int L, int R, int a)
{
    if (l <= L && R <= r) {tadd(a, R - L + 1, d); return;}
    pdown(L, R, a);
    int Mid = (L + R) >> 1;
    if (l <= Mid) Up_Add(l, r, d, L, Mid, LS(a));
    if (r > Mid) Up_Add(l, r, d, Mid + 1, R, RS(a));
    pup(a);
}

LL Query(int l, int r, int L, int R, int a)
{
    if (l <= L && R <= r) return e[a].sum;
    pdown(L, R, a);
    LL res = 0; int Mid = (L + R) >> 1;
    if (l <= Mid) res = Query(l, r, L, Mid, LS(a));
    if (r > Mid) res += Query(l, r, Mid + 1, R, RS(a));
    return res;
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    for (int i = 1; i <= n; i += 1) IN(A[i]);
    Build(1, n, 1);
    for (int C = 1, o, a, b, c; C <= m; C += 1)
    {
        IN(o), IN(a), IN(b);
        if (o == 1) IN(c), Up_Min(a, b, c, 1, n, 1);
        else if (o == 2) IN(c), Up_Add(a, b, c, 1, n, 1);
        else printf("%lld\n", Query(a, b, 1, n, 1));
    }
    return 0;
}