BZOJ3064 Tyvj1518 CPU监控

2015.01.29 19:52 Thu| 8 visits oi_2015| 2015_刷题日常| Text

Solution

这不是一道裸线段树么?没错!请欣赏我们勤劳努力的 ygy 童鞋的交题记录:

这还真是废寝忘食呢!请允许我致以敬意!

其实这还真是一道裸得不行的线段树,给高一的小伙伴们一点也不超纲 -_-||,不过是维护 6 个标记而已~

  • p[i] 表示节点 i 表示的区间内增加的值;
  • ph[i] 表示节点 i 表示的区间内历史上最多增加的值;
  • q[i] 表示节点 i 表示的区间内被覆盖为 q[i];
  • qh[i] 表示节点 i 表示的区间内最大时被覆盖为 qh[i];
  • maxt[i] 表示节点 i 表示的区间内最大数;
  • maxh[i] 表示节点 i 表示的区间内历史上的最大数。

按照懒人的想法,访问到一个节点的时候,直接 nc 地把当前节点值下传,然后直接打一个标记就可以了嘛~ 子节点下传后的标记又可以直接传给孙子节点……一代一代,无穷尽也,于是单次询问时间复杂度就变为了 $\mathcal O(n)$ T^T。

看来是免不了恶心的讨论了,细心谨慎,慢慢写就好 QoQ

另外如果访问到叶子节点,可能还会继续访问叶子节点。可是要是再判断是不是叶子节点,我感觉我一定把持不住了。。空间开大二倍,初值标记为 -inf。这样就能 AC 此题。(能不能更麻烦一点

最后祝 ygy 童鞋晚安~~~

Code

#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define S 800005
#define inf -1061109568
#define lson (pos << 1)
#define rson (pos << 1 | 1)

int n, m, a[N], maxt[S], maxh[S], p[S], ph[S], q[S], qh[S];

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 * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void build(int pos, int l, int r)
{
    q[pos] = qh[pos] = inf;
    if (l == r) { maxt[pos] = maxh[pos] = a[l]; return ; }
    int mid = (l + r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
    maxt[pos] = maxh[pos] = max(maxt[lson], maxt[rson]);
}

inline void update1(int pos, int par)
{
    if (q[pos] != inf)
        qh[pos] = max(qh[pos], max(q[pos] + ph[par], qh[par]));
    else
        ph[pos] = max(ph[pos], p[pos] + ph[par]),
        qh[pos] = qh[par], p[pos] = 0;
    q[pos] = q[par];
}

inline void update2(int pos, int par)
{
    if (q[pos] != inf)
        qh[pos] = max(qh[pos], q[pos] + ph[par]), q[pos] += p[par];
    else
        ph[pos] = max(ph[pos], p[pos] + ph[par]), p[pos] += p[par];
}

void pushdown(int pos, int l, int r)
{
    if (q[pos] != inf)
        maxh[pos] = max(maxh[pos], max(maxt[pos] + ph[pos], qh[pos])),
        maxt[pos] = q[pos];
    else maxh[pos] = max(maxh[pos], maxt[pos] + ph[pos]), maxt[pos] += p[pos];
    if (q[pos] != inf) update1(lson, pos), update1(rson, pos);
    else update2(lson, pos), update2(rson, pos);
    p[pos] = ph[pos] = 0;
    q[pos] = qh[pos] = inf;
}

void pushup(int pos, int l, int r)
{
    int mid = (l + r) >> 1;
    pushdown(pos, l, r);
    pushdown(lson, l, mid); pushdown(rson, mid + 1, r);
    maxt[pos] = max(maxt[lson], maxt[rson]);
    maxh[pos] = max(maxh[lson], maxh[rson]);
}

void modify_1(int pos, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y)
    {
        if (q[pos] != inf) q[pos] += z, qh[pos] = max(qh[pos], q[pos]);
        else p[pos] += z, ph[pos] = max(ph[pos], p[pos]);
        return ;
    }
    pushdown(pos, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid) modify_1(lson, l, mid, x, y, z);
    if (y > mid) modify_1(rson, mid + 1, r, x, y, z);
    pushup(pos, l, r);
}

void modify_2(int pos, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y)
    {
        if (q[pos] != inf) q[pos] = z, qh[pos] = max(qh[pos], q[pos]);
        else p[pos] = 0, q[pos] = qh[pos] = z;
        return ;
    }
    pushdown(pos, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid) modify_2(lson, l, mid, x, y, z);
    if (y > mid) modify_2(rson, mid + 1, r, x, y, z);
    pushup(pos, l, r);
}

int query_1(int pos, int l, int r, int x, int y)
{
    pushdown(pos, l, r);
    if (x <= l && r <= y) return maxt[pos];
    int mid = (l + r) >> 1, re = inf;
    if (x <= mid) re = max(re, query_1(lson, l, mid, x, y));
    if (y > mid) re = max(re, query_1(rson, mid + 1, r, x, y));
    return re;
}

int query_2(int pos, int l, int r, int x, int y)
{
    pushdown(pos, l, r);
    if (x <= l && r <= y) return maxh[pos];
    int mid = (l + r) >> 1, re = inf;
    if (x <= mid) re = max(re, query_2(lson, l, mid, x, y));
    if (y > mid) re = max(re, query_2(rson, mid + 1, r, x, y));
    return re;
}

int main()
{
    memset(maxh, 0xc0, sizeof maxh);
    memset(maxt, 0xc0, sizeof maxt);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    build(1, 1, n);
    cin >> m;
    char opt[2];
    for (int x, y, z, i = 1; i <= m; ++i)
    {
        scanf("%s", opt); x = read(); y = read();
        switch(opt[0])
        {
        case 'Q': printf("%d\n", query_1(1, 1, n, x, y)); break;
        case 'A': printf("%d\n", query_2(1, 1, n, x, y)); break;
        case 'P': z = read(); modify_1(1, 1, n, x, y, z); break;
        case 'C': z = read(); modify_2(1, 1, n, x, y, z); break;
        }
    }
}