hdu

vj

code:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

const int N = 4e6 + 50;
const int M = 1e5 + 50;
const int Mod = 1e9 + 7;

#define int long long

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int sum[N], ma[N], se[N], num[N], a[N];

int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }
void push_up(int p)
{
    sum[p] = sum[ls(p)] + sum[rs(p)];
    ma[p] = max(ma[ls(p)], ma[rs(p)]);
    if (ma[ls(p)] == ma[rs(p)])
    {
        se[p] = max(se[ls(p)], se[rs(p)]);
        num[p] = num[ls(p)] + num[rs(p)];
    }
    else
    {
        se[p] = max(se[ls(p)], se[rs(p)]);
        se[p] = max(se[p], min(ma[ls(p)], ma[rs(p)]));
        num[p] = ma[ls(p)] > ma[rs(p)] ? num[ls(p)] : num[rs(p)];
    }
}

void build(int p, int l, int r)
{
    if (l == r)
    {
        sum[p] = a[l];
        ma[p] = a[l];
        se[p] = -1;
        num[p] = 1;
        return;
    }
    int mid = l + r >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    push_up(p);
}

void change(int p, int k)
{
    if (k >= ma[p])
        return;
    sum[p] -= num[p] * (ma[p] - k);
    ma[p] = k;
}

void push_down(int p)
{
    change(ls(p), ma[p]);
    change(rs(p), ma[p]);
}

void update(int nx, int ny, int l, int r, int p, int k)
{
    if (k >= ma[p])
        return;
    if (nx <= l && r <= ny && k > se[p])
    {
        change(p, k);
        return;
    }
    push_down(p);
    int mid = l + r >> 1;
    if (nx <= mid)
        update(nx, ny, l, mid, ls(p), k);
    if (ny > mid)
        update(nx, ny, mid + 1, r, rs(p), k);
    push_up(p);
}

int query_sum(int nx, int ny, int l, int r, int p)
{
    int res = 0;
    if (nx <= l && r <= ny)
        return sum[p];
    push_down(p);
    int mid = l + r >> 1;
    if (nx <= mid)
        res += query_sum(nx, ny, l, mid, ls(p));
    if (ny > mid)
        res += query_sum(nx, ny, mid + 1, r, rs(p));
    return res;
}

int query_max(int nx, int ny, int l, int r, int p)
{
    int res = 0;
    if (nx <= l && r <= ny)
        return ma[p];
    push_down(p);
    int mid = l + r >> 1;
    if (nx <= mid)
        res = max(res, query_max(nx, ny, l, mid, ls(p)));
    if (ny > mid)
        res = max(res, query_max(nx, ny, mid + 1, r, rs(p)));
    return res;
}

int t, n, m;

signed main()
{
    t = read();
    while (t--)
    {
        n = read(), m = read();
        for (int i = 1; i <= n; ++i)
            a[i] = read();
        build(1, 1, n);
        while (m--)
        {
            int opt = read(), l = read(), r = read(), k;
            if (opt == 0)
            {
                k = read();
                update(l, r, 1, n, 1, k);
            }
            else if (opt == 1)
            {
                printf("%lld\n", query_max(l, r, 1, n, 1));
            }
            else
            {
                printf("%lld\n", query_sum(l, r, 1, n, 1));
            }
        }
    }
    return 0;
}