题解：P11845 [USACO25FEB] Min Max Subarrays P

· · 题解

模拟赛考了这个题，被硬控 2h，最后没调出来，问候搬题人母亲。

考虑对于一个长度等于奇数的序列，在上面进行一轮操作，手玩发现很大概率都是得到最大值。

继续手玩发现 n=3 的部分情况并不满足，这种情况是最大值在中间，而对于 n>3 都是成立的。

考试时对于这个的一种解释：只有 n=3 且最大值在中间时第一次必然会对周围两个数取 \min，所以只能取到次大值，而更大 n 的则可以避免第一次对最大值取 \min。

考虑区间长度为偶数，发现很多情况都是取到次大值。

反例手玩就会发现，只会存在于 4,6 中，设 X,Y 为最大，次大值，形如：

考虑证明，因为 X,Y 必须都留到最后然后再取 \min，然后考虑类似上面 n=3 一样分析，就可以感性证明。

这样只需要维护所有长度为奇数的区间的最大值和所有长度为偶数的区间的次大值。

这个好（？）维护，直接分治，每次拿个双指针扫就做完了。

真难写，/tuu /tuu /tuu，果然我还是不适合做数据结构，时间 O(n \log n)。

Tips：有大神告诉我，不用分类讨论，直接记搜搜出来 \le 10 就行了。

#include <bits/stdc++.h>
#define ll long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<ll, ll>
#define mp make_pair
#define pb push_back
#define ld lower_bound
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define drep(i, a, b) for (int i = (a); i >= (b); i--)
#define ud upper_bound
#define mem(s, k) memset(s, k, sizeof(s))
#define cpy(s, t) memcpy(s, t, sizeof(s))
#define fi first
#define se second
#define ull unsigned long long
#define vi vector<int>
#define fv inline void
#define fn inline static
using u16 = unsigned short;
using u32 = unsigned;
using u64 = unsigned ll;
using u128 = __uint128_t;
using i16 = short;
using i32 = ll;
using i64 = ll;
using i128 = __int128_t;
using db = double;
using namespace std;
const int N = 1e6 + 5;
i32 ans = 0;
struct info {
    i32 mx, se;
    info() { mx = se = 0; }
    fv ins(i32 x) {
        if (mx < x)
            se = mx, mx = x;
        else if (se < x)
            se = x;
    }
    friend info operator+(info x, info y) {
        x.ins(y.mx), x.ins(y.se);
        return x;
    }
};
i32 n, m, a[N];
info p[N], q[N];
fv calc(i32 n, i32 m) {
    i32 pos = 0, t[2] = {};
    rep(i, 1, m) {
        while (pos < n && p[pos + 1].mx <= q[i].se) t[(++pos) & 1]++;
        ans += t[i & 1] * q[i].se;
    }
    pos = t[0] = t[1] = 0;
    rep(i, 1, n) {
        while (pos < m && q[pos + 1].mx <= p[i].se) t[(++pos) & 1]++;
        ans += t[i & 1] * p[i].se;
    }
    pos = t[0] = t[1] = 0;
    rep(i, 1, m) {
        while (pos < n && p[pos + 1].mx <= q[i].mx) t[(++pos) & 1] += p[pos].mx;
        ans += t[i & 1];
    }
    pos = t[0] = t[1] = 0;
    rep(i, 1, m) {
        while (pos < n && p[pos + 1].mx <= q[i].se) t[(++pos) & 1] += p[pos].mx;
        ans -= t[i & 1];
    }
    pos = t[0] = t[1] = 0;
    rep(i, 1, n) {
        while (pos < m && q[pos + 1].mx < p[i].mx) t[(++pos) & 1] += q[pos].mx;
        ans += t[i & 1];
    }
    pos = t[0] = t[1] = 0;
    rep(i, 1, n) {
        while (pos < m && q[pos + 1].mx <= p[i].se) t[(++pos) & 1] += q[pos].mx;

        ans -= t[i & 1];
    }
}
fv solve(i32 l, i32 r) {
    if (l == r)
        return;
    i32 mid = (l + r) >> 1;
    solve(l, mid), solve(mid + 1, r);
    i32 n = mid - l + 1, m = r - mid;
    p[0] = q[0] = info();
    rep(i, 1, n) p[i] = p[i - 1], p[i].ins(a[mid - i + 1]);
    rep(i, 1, m) q[i] = q[i - 1], q[i].ins(a[mid + i]);
    calc(n, m);
}
i32 L[N], R[N], stk[N], tp;
int main() {
    IOS;
    freopen("minmax.in", "r", stdin);
    freopen("minmax.out", "w", stdout);
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) {
        i32 mxp = -1, secp = -1, mx = -1e9, sec = -1e9, thd = -1e9;
        rep(j, i, n) {
            if (a[j] > mx)
                secp = mxp, mxp = j, thd = sec, sec = mx, mx = a[j];
            else if (a[j] > sec)
                secp = j, thd = sec, sec = a[j];
            else if (a[j] > thd)
                thd = a[j];
            if (j - i + 1 == 3) {
                if (mx == a[i + 1])
                    ans += max(a[i], a[j]);
                else
                    ans += mx;
            } else if (j - i + 1 == 4) {
                if (a[i] == mx && a[i + 2] == sec || a[i + 2] == mx && a[i] == sec)
                    ans += max(a[i + 1], a[i + 3]);
                else if (a[i + 1] == mx && a[i + 3] == sec || a[i + 1] == sec && a[i + 3] == mx)
                    ans += max(a[i], a[i + 2]);
                else if (a[i + 1] == mx && a[i + 2] == sec || a[i + 1] == sec && a[i + 2] == mx)
                    ans += max(a[i], a[i + 3]);
                else
                    ans += sec;
            } else if (j - i + 1 == 6) {
                if (abs(secp - mxp) == 2 && secp != i && mxp != i && secp != j && mxp != j)
                    ans += thd;
                else if (abs(secp - mxp) == 3 && secp != i && mxp != i && secp != j && mxp != j)
                    ans += thd;
                else
                    ans += sec;
            } else {
                if ((j - i + 1) & 1)
                    ans += mx;
                else
                    ans += sec;
            }
            ans -= ((j - i + 1) & 1 ? mx : sec);
            if (j - i + 1 >= 6)
                break;
        }
    }
    solve(1, n);
    rep(i, 1, n) {
        while (tp && a[stk[tp]] < a[i]) --tp;
        L[i] = stk[tp] + 1, stk[++tp] = i;
    }
    tp = 0;
    drep(i, n, 1) {
        while (tp && a[stk[tp]] <= a[i]) --tp;
        R[i] = tp ? stk[tp] - 1 : n, stk[++tp] = i;
        i32 vl = i - L[i], vr = R[i] - i;
        i32 p0 = (vl + 2) >> 1, p1 = vl + 1 - p0;
        i32 q0 = (vr + 2) >> 1, q1 = vr + 1 - q0;
        ans += p0 * q0 * a[i] + q1 * p1 * a[i];
    }
    cout << ans;
}