【题解】P17234 [Algo Beat Contest 017 C] 交互题

· · 题解

螳臂当车，我是螳臂。

Solution

约定：ml_i = \min\limits_{j \le i} a_j, mr_i = \min\limits_{j \ge i} a_j。特别地，ml_0 = mr_{n+1} = +\infty。

枚举 l，先求满足 ml_{l-1} = \operatorname{cmin}(l,r) 的区间贡献，即 ml_{l-1} \le mr_{r+1}。mr 单调不降，可以二分得到满足该限制的最小 r（限制 0）。

问题转化为：对于 l，求 \operatorname{mex}(l,r) = ml_{l-1} 的 r 的数量。

设 m = ml_{l-1}，考虑限制的本质：

限制 1：a[l \cdots r] 中包含 0, 1, \dots m - 1。

限制 2：a[l \cdots r] 中不包含 m。

由于 m = \min\limits_{j<i} a_j，于是限制 1 等价于 0,1,\dots,m-1 第一次出现的位置 \in [l,r]。可以维护 first_i 表示 i 第一次出现的位置，则合法的 r 满足：

r \ge \max\limits_{i < m} first_i

即 first 的前缀最大值，容易预处理得到。

对于限制 2，预处理每个数出现的下标后二分即可。

根据三个限制容易得到 r 的范围。

处理 mr_{r+1} = \operatorname{cmin}(l,r) 的贡献可以翻转数组，但是注意为了不算重，需要满足的条件是 mr_{r+1} < ml_{l-1}。

时间复杂度 O(n \log n)。

#include <bits/stdc++.h>
//#define int long long
//#define lson (id << 1)
//#define rson (id << 1 | 1)
#define endl '\n'

using namespace std;
typedef long long ll;

const int N = 2e5 + 5;

int n;
int a[N];
int ml[N], mr[N], min_r[N];
int fst[N];

vector<int> p[N];
ll res;

void solve(bool sp) {
    for (int i = 1; i <= n; i ++) p[a[i]].push_back(i);
    ml[0] = mr[n + 1] = 1e9; 
    for (int i = 1; i <= n; i ++) ml[i] = min(ml[i - 1], a[i]);
    for (int i = n; i >= 1; i --) {
        mr[i] = min(mr[i + 1], a[i]);
        int l = i + 1, r = n, res = n + 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (!sp ? (mr[mid] >= ml[i - 1]) : (mr[mid] > ml[i - 1])) res = mid, r = mid - 1;
            else l = mid + 1;
        }
        min_r[i] = res - 1;
    }
    for (int i = 1; i <= n; i ++) {
        if (!fst[a[i]]) fst[a[i]] = i;
    }
    if (!fst[0]) fst[0] = 1e9;
    for (int i = 1; i <= 2e5; i ++) {
        if (!fst[i]) fst[i] = 1e9;
        fst[i] = max(fst[i], fst[i - 1]);
    }
    for (int i = 2; i <= n; i ++) {
        int mn = ml[i - 1];
        int get = lower_bound(p[mn].begin(), p[mn].end(), i) - p[mn].begin();
        if (get == (int)p[mn].size()) get = n + 1;
        else get = p[mn][get];
        res += max(0, get - max(mn ? fst[mn - 1] : 0, min_r[i]));
    }
    for (int i = 1; i <= n; i ++) ml[i] = mr[i] = min_r[i] = 0, p[a[i]].clear(), fst[a[i]] = 0;
}

signed main() {
//  freopen("data.txt", "r", stdin);
//  freopen("2.txt", "w", stdout);
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    solve(0);
    reverse(a + 1, a + n + 1);
    solve(1);
    cout << res;
    return 0;
}