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 <bits/stdc++.h>
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 };}elsereturn 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;
}