UOJ#164

$UOJ$#$164$

本文部分摘自：

题解-$WerKeyTom$_$FTD$

另:漂亮的代码（借鉴了一下（逃-$lcf2000$

题意

要求支持以下操作：

$1.$区间加

$2.$区间值取$max(x_i-a,0)$

$3.$区间变成$a$

$4.$询问点值

$5.$询问点的历史最大值

$So\;How?$

发现区间减比较难维护。

如果是四个标记，我们没法规定优先级。

我们试图将标记简化。

正解标记长这样：$max(a+x_i,b)$

表示对于区间的每一个$x_i+a$，再与$b$取大。

怎么维护前三种操作呢？

区间加：$(x,-INF)$

区间减: $(-x,0)$

区间变成某个数: $(-INF,x)$

$Pushdown?$

我们让$(c,d)$覆盖到的$(a,b)$

$max(max(x_i+a,b)+c,d)$

$=max(x_i+a+c,b+c,d)$

$=max(x_i+a+c,max(b+c,d))$

表示成不带未知数的形式：$(a+c,max(b+c,d))$

历史最大标记的 $Pushdown?$

历史$(a,b)$和当前~~并即将成为历史的~~$(c,d)$互不影响

$realx_i=max(x_i+a,b,max(xi+c,d))$

$=max(xi+a,xi+c,b,d)$

表示成不带未知数的形式：$(max(a,c),max(b,d))$

综上所述，整道题的$Pushdown:$

合并顺序：（比较绕，尽量在草稿纸上写下$abcd$的对应变量）

$1.$父亲的历史与儿子的当前合并，得到儿子的历史

$PreA[now]=max(PreA[now],PreA[fa]+A[now])$

$PreB[now]=max(PreB[now],max(B[now]+PreA[fa],preB[fa]))$

$2.$父亲的当前与儿子的当前合并，得到儿子的当前。

$A[now]=A[fa]+A[now]$

$B[now]=max(B[now]+A[fa],B[fa])$

一个小细节

所有你以为可以直接加的标记都要与$INF$取$max$，否则会爆。

比如两个负无穷不幸相加.....

为这道仙人题目的完结撒花!

#include<cstdio>
#include<iostream>
#define ll long long
using std::max;

const int MAXN = 5e5 + 10;
const long long INF = 1e15;
ll A[MAXN * 4], B[MAXN * 4], preA[MAXN * 4], preB[MAXN * 4], x[MAXN];
int N, M;

void Build(int l, int r, int k)
{
    if (l == r) 
    { 
        A[k] = preA[k] = x[l], B[k] = preB[k] = -INF;
        return;
    }
    int mid = (l + r) >> 1;
    Build(l, mid, k << 1);
    Build(mid + 1, r, k << 1 | 1);
}

void Pushdown(int fa, int l, int r)
{
    for (int i = 0; i < 2; i++)
    {
        int now = fa << 1 | i;
        preA[now] = max(preA[now], preA[fa] + A[now]);
        preB[now] = max(preB[now], max(B[now] + preA[fa], preB[fa]));
        A[now] = max(A[fa] + A[now], -INF);
        B[now] = max(B[now] + A[fa], B[fa]);
    }
    preA[fa] = A[fa] = 0;
    preB[fa] = B[fa] = -INF;
}

void Update(int stdl, int stdr, int l, int r, int k, long long a, long long b)
{
    if (l > stdr || r < stdl) return;
    if (l >= stdl && r <= stdr) 
    {
        A[k] = max(A[k] + a, -INF);
        B[k] = max(B[k] + a, b);
        preA[k] = max(preA[k], A[k]);
        preB[k] = max(preB[k], B[k]);
        return;
    }
    Pushdown(k, l, r);
    int mid = (l + r) >> 1;
    Update(stdl, stdr, l, mid, k << 1, a, b);
    Update(stdl, stdr, mid + 1, r, k << 1 | 1, a, b);
}

int Query(int std, int l, int r, int k)
{
    if (l == r) return k;
    Pushdown(k, l, r);
    int mid = (l + r) >> 1;
    if (std <= mid) return Query(std, l, mid, k << 1);
    return Query(std, mid + 1, r, k << 1 | 1);
}

ll rd()
{
    char ch = getchar(); long long ret = 0;
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch <= '9' && ch >= '0') ret = ret * 10 + (int)ch - 48, ch = getchar();
    return ret;
}

int main()
{
    N = rd(), M = rd();
    for (int i = 1; i <= N; i++) x[i] = rd();
    Build(1, N, 1);
    for (int i = 1; i <= M; i++)
    {
        int opt; opt = rd();
        if (opt <= 3)
        {
            int l = rd(), r = rd(), delt = rd();
            if (opt == 1) Update(l, r, 1, N, 1, delt, -INF);
            if (opt == 2) Update(l, r, 1, N, 1, -delt, 0);
            if (opt == 3) Update(l, r, 1, N, 1, -INF, delt);
        }
        else
        {
            int k = rd(), pos = Query(k, 1, N, 1);
            long long now = max(A[pos], B[pos]);
            if (opt == 4) printf("%lld\n", now);
            long long pre = max(preA[pos], preB[pos]);
            if (opt == 5) printf("%lld\n", pre);
        }
    }
    return 0;
}

ATURIC的博客

博客

题意