2023 NOIP A层联测9 - 风信子 题解

思路

我们可以考虑设 $f_{l_0,r_0,l_1,r_1}$ 表示最大的 $a_l-a_r$，其中 $l\in [l_0,r_0]$，$r\in [l_1,r_1]$。

于是如果我们能够快速求出 $f$ 值，那么我们就能解决问题。

考虑如何快速求 $f$ 值。

发现似乎没有什么好方法，但是我们在某些特殊情况下是可以快速求的，即当 $l_0=l_1$，$r_0=r_1$ 或 $r_0<l_1$ 时，我们可以用线段树快速求出其 $f$ 值。

我们又发现刚开始给出的左右两边端点能取的区间是一样的，于是我们考虑当取出这区间的最大值之后，如何拆分区间使得拆分出来的区间满足上面的特殊情况。

当 $l_0=l_1$，$r_0=r_1$ 时，我们假设此时最大值的为 $a_x-a_y$，当我们取出 $a_x-a_y$ 后，我们就不能再取 $(x,y)$ 这对数了，此时我们的左右端点的区间会改变，于是我们可以将改变后的区间拆为如下六种形式。

• 左端点 $\in [l,x-1]$，右端点 $\in [l,x-1]$，此时 $x>l$。
• 左端点 $\in [l,x-1]$，右端点 $\in [x,r]$，此时 $x>l$。
• 左端点 $\in [x,x]$，右端点 $\in [x,x]$，此时 $x\ne y$。
• 左端点 $\in [x,x]$，右端点 $\in [x+1,y-1]$，此时 $x<y-1$。
• 左端点 $\in [x,x]$，右端点 $\in [y+1,r]$，此时 $y>r$。
• 左端点 $\in [x+1,r]$，右端点 $\in [x+1,r]$，此时 $x<r$。

因为此时 $l_0=l_1$，$r_0=r_1$，所以我们用 $l$，$r$ 代替。

注意一下后面的条件，要满足其这个取值区间才会存在。

还有一种情况为 $r_0<l_1$，此时拆分形式如下。

• 左端点 $\in [l_0,x-1]$，右端点 $\in [l_1,r_1]$，此时 $l_0<x$。
• 左端点 $\in [x,x]$，右端点 $\in [l_1,y-1]$，此时 $l_1<y$。
• 左端点 $\in [x,x]$，右端点 $\in [y+1,r_1]$，此时 $y<r_1$。
• 左端点 $\in [x+1,r_0]$，右端点 $\in [l_1,r_1]$，此时 $x<r_0$。

于是我们发现，当我们满足特殊条件时的区间，取出最大值后还是能变成满足特殊条件的区间，于是我们就可以做出来了。

代码

#include 
using namespace std;
typedef long long LL;
const LL inf = 1e16;
int n, Q, a[100005];
LL bz[5000005];
struct Grid {
    LL val; int id;
    friend bool operator> (Grid a, Grid b) { return a.val > b.val; }
    friend bool operator< (Grid a, Grid b) { return a.val < b.val; }
} maxn[5000005], minn[5000005];
struct Ans {
    LL val; int x, y;
    friend bool operator> (Ans a, Ans b) { return a.val > b.val; }
    friend bool operator< (Ans a, Ans b) { return a.val < b.val; }
} ans[5000005];
inline void updata(int x) {
    maxn[x] = max(maxn[x * 2], maxn[x * 2 + 1]);
    minn[x] = min(minn[x * 2], minn[x * 2 + 1]);
    ans[x] = max(ans[x * 2], ans[x * 2 + 1]);
    if (maxn[x * 2].val - minn[x * 2 + 1].val > ans[x].val)
        ans[x].val = maxn[x * 2].val - minn[x * 2 + 1].val, ans[x].x = maxn[x * 2].id, ans[x].y = minn[x * 2 + 1].id;
}
inline void build(int x, int l, int r) {
    if (l == r) {
        maxn[x].val = minn[x].val = a[l], ans[x].val = 0;
        maxn[x].id = minn[x].id = ans[x].x = ans[x].y = l;
        return ;
    }
    int mid = l + r >> 1;
    build(x * 2, l, mid), build(x * 2 + 1, mid + 1, r);
    updata(x);
}
inline void pushdown(int x) {
    maxn[x].val += bz[x], minn[x].val += bz[x];
    bz[x * 2] += bz[x], bz[x * 2 + 1] += bz[x];
    bz[x] = 0;
}
inline void add(int x, int l, int r, int sl, int sr, int val) {
    pushdown(x);
    if (r < sl || sr < l)
        return ;
    if (sl <= l && r <= sr) {
        bz[x] += val;
        pushdown(x);
        return ;
    }
    int mid = l + r >> 1;
    add(x * 2, l, mid, sl, sr, val), add(x * 2 + 1, mid + 1, r, sl, sr, val);
    updata(x);
}
inline Grid find_max(int x, int l, int r, int sl, int sr) {
    pushdown(x);
    if (r < sl || sr < l)
        return { -inf, 0 };
    if (sl <= l && r <= sr)
        return maxn[x];
    int mid = l + r >> 1;
    return max(find_max(x * 2, l, mid, sl, sr), find_max(x * 2 + 1, mid + 1, r, sl, sr));
}
inline Grid find_min(int x, int l, int r, int sl, int sr) {
    pushdown(x);
    if (r < sl || sr < l)
        return { inf, 0 };
    if (sl <= l && r <= sr)
        return minn[x];
    int mid = l + r >> 1;
    return min(find_min(x * 2, l, mid, sl, sr), find_min(x * 2 + 1, mid + 1, r, sl, sr));
}
inline Ans find_ans(int x, int l, int r, int sl, int sr) {
    pushdown(x);
    if (r < sl || sr < l)
        return { -inf, 0, 0 };
    if (sl <= l && r <= sr)
        return ans[x];
    int mid = l + r >> 1;
    Ans t = max(find_ans(x * 2, l, mid, sl, sr), find_ans(x * 2 + 1, mid + 1, r, sl, sr));
    Grid a = find_max(x * 2, l, mid, sl, sr), b = find_min(x * 2 + 1, mid + 1, r, sl, sr);
    t = max(t, {a.val - b.val, a.id, b.id});
    return t;
}
struct node {
    int il, ir, jl, jr;
    LL val;
    Ans Val() {
        if (ir < jl) {
            Grid l = find_max(1, 1, n, il, ir), r = find_min(1, 1, n, jl, jr);
            return { l.val - r.val, l.id, r.id };
        }
        else
            return find_ans(1, 1, n, il, ir);
    }
    friend bool operator< (node a, node b) { return a.val < b.val; }
} ;
priority_queue <node> q;
int main() {
    scanf("%d%d", &n, &Q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    while (Q--) {
        int opt, L, R, k;
        scanf("%d%d%d%d", &opt, &L, &R, &k);
        if (opt == 1)
            add(1, 1, n, L, R, k);
        else {
            node t;
            t.il = t.jl = L, t.jr = t.ir = R;
            t.val = t.Val().val;
            q.push(t);
            LL sum = 0;
            while (k) {
                node now = q.top();
                Ans val = now.Val();
                int x = val.x, y = val.y;
                q.pop(), k--;
                sum = sum + val.val;
                if (now.ir < now.jl) {
                    if (x > now.il) {
                        t.il = now.il, t.ir = x - 1, t.jl = now.jl, t.jr = now.jr;
                        t.val = t.Val().val;
                        q.push(t);
                    }
                    if (now.jl < y) {
                        t.il = x, t.ir = x, t.jl = now.jl, t.jr = y - 1;
                        t.val = t.Val().val;
                        q.push(t);
                    }
                    if (y < now.jr) {
                        t.il = x, t.ir = x, t.jl = y + 1, t.jr = now.jr;
                        t.val = t.Val().val;
                        q.push(t);
                    }
                    if (x < now.ir) {
                        t.il = x + 1, t.ir = now.ir, t.jl = now.jl, t.jr = now.jr;
                        t.val = t.Val().val;
                        q.push(t);
                    }
                }
                else {
                    int l = now.il, r = now.ir;
                    if (x > l) {
                        t.il = l, t.ir = x - 1, t.jl = l, t.jr = x - 1;
                        t.val = t.Val().val;
                        q.push(t);
                        t.il = l, t.ir = x - 1, t.jl = x, t.jr = r;
                        t.val = t.Val().val;
                        q.push(t);
                    }
                    if (x != y) {
                        t.il = x, t.ir = x, t.jl = x, t.jr = x;
                        t.val = t.Val().val;
                        q.push(t);
                    }
                    if (x < y - 1) {
                        t.il = x, t.ir = x, t.jl = x + 1, t.jr = y - 1;
                        t.val = t.Val().val;
                        q.push(t);
                    }
                    if (y < r) {
                        t.il = x, t.ir = x, t.jl = y + 1, t.jr = r;
                        t.val = t.Val().val;
                        q.push(t);
                    }
                    if (x < r) {
                        t.il = x + 1, t.ir = r, t.jl = x + 1, t.jr = r;
                        t.val = t.Val().val;
                        q.push(t);
                    }
                }
            }
            printf("%lld\n", sum);
            while (!q.empty())
                q.pop();
        }
    }
    return 0;
}
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178