UOJ164 V

发表于

  题意:维护一个序列，5个操作:

  1、区间加x

  2、区间减x后对0取max

  3、区间覆盖成x

  4、询问单点值

  5、询问单点历史最大值

  又是一眼线段树。但是同样也有新东西。
  首先，区间减x后对0取max这个操作看起来十分的棘手。还有就是历史最大值。
  但是这道题的好处是单点查询，也就是说我们的每个节点并不需要维护实际信息，而只需要维护lazy-tag。将初始信息记录在叶节点tag上，在询问单点时，将一路上的tag给pushdown下去，最后一个点的tag上的值就用来更新答案了。
  我们定义节点tag为一个二元组$(a, b)$ 代表执行这个标记时，对于区间内的数，先加上a然后对b取max。
  那么操作1 2 3分别对应标记$(x, {- \infty})$ $(-x, 0)$ $({- \infty}, x)$
  如何pushdown这个标记?设下传的标记为$(A, B)$，直接将当前标记$(a, b)$更新为即可。
  在实际应用中由于数字可能爆-INF的下界，所以左边要对-INF取个max。
  如何维护历史标记?同样用一个二元组$(c, d)$，分别代表该节点在上次与这次pushdown之间的最大add值和最大取max值。pushdown的话，设下传的标记为$(C, D)$，当前历史标记更新为:
  左侧同样要对-INF取max。注意到更新标记涉及到节点当前标记$(a, b)$，所以pushdown时先下传历史标记再下传当前标记。
  最后pushdown到叶子时，节点的$\max(a, b)$、$\max(c, d)$就分别为当前和历史的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <ctime>
 
using namespace std;
 
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define mp make_pair
#define ms(a, b) memset(a, b, sizeof a)
#define x first
#define y second
 
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
template<typename T> inline T& read(T& x)
{
    static char c; bool flag = 0;
    while(!isdigit(c = getchar())) if(c == '-') flag = 1;
    for(x = c ^ 48; isdigit(c = getchar()); x = (x << 3) + (x << 1) + (c ^ 48));
    if(flag) x = -x; return x;
}
const int maxn = 500010;
int n, m;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
typedef pair<LL, LL> PLL;
namespace SGT
{
#define ls h << 1
#define rs h << 1 | 1
#define mid ((l + r) >> 1)
#define lc l, mid
#define rc mid + 1, r
    PLL T[maxn * 3], Past[maxn * 3];
    void creat(int h, int l, int r)
    {
        if(l == r)
        {
            Past[h].x = Past[h].y = T[h].x = read(T[h].y);
            return;
        }
        creat(ls, lc); creat(rs, rc);
    }
    void pushdown(int h)
    {
        chkmax(Past[ls].x, max(Past[h].x + T[ls].x, -INF));
        chkmax(Past[ls].y, max(Past[h].y, Past[h].x + T[ls].y));
        chkmax(Past[rs].x, max(Past[h].x + T[rs].x, -INF));
        chkmax(Past[rs].y, max(Past[h].y, Past[h].x + T[rs].y));
        T[ls] = mp(max(T[ls].x + T[h].x, -INF), max(T[ls].y + T[h].x, T[h].y));
        T[rs] = mp(max(T[rs].x + T[h].x, -INF), max(T[rs].y + T[h].x, T[h].y));
        T[h] = Past[h] = mp(0, 0);
    }
    void update(int h, int l, int r, int L, int R, PLL w)
    {
        if(L <= l && r <= R)
        {
            T[h] = mp(max(T[h].x + w.x, -INF), max(T[h].y + w.x, w.y));
            chkmax(Past[h].x, T[h].x); chkmax(Past[h].y, T[h].y);
            return;
        }
        pushdown(h);
        if(L <= mid) update(ls, lc, L, R, w);
        if(R > mid) update(rs, rc, L, R, w);
    }
    LL query(int h, int l, int r, int p, bool op)
    {
        if(l == r) return op ? max(T[h].x, T[h].y) : max(Past[h].x, Past[h].y);
        pushdown(h);
        if(p <= mid) return query(ls, lc, p, op);
        else return query(rs, rc, p, op);
    }
}
using namespace SGT;
int main()
{
    freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
    read(n); read(m);
    creat(1, 1, n);
    while(m--)
    {
        int op, l, r; LL w; read(op);
        if(op == 1) read(l), read(r), read(w), update(1, 1, n, l, r, mp(w, 0));
        else if(op == 2) read(l), read(r), read(w), update(1, 1, n, l, r, mp(-w, 0));
        else if(op == 3) read(l), read(r), read(w), update(1, 1, n, l, r, mp(-INF, w));
        else read(l), printf("%lld\n", query(1, 1, n, l, op == 4));
    }
    return 0;
}