CF1693D

· · 题解

思路

要把一个数列划分成一个降序的和一个升序的序列。

你考虑这个限制其实是很严格的。对于一对数，如果 i<j,a_i<a_j，那肯定他们不能同时放到降序序列里面，那肯定就是要么都放到升序序列，要么一边放一个，总之就是至少有一个在升序序列里。那如果有这种东西：3 4 1 2 。

那肯定寄了。究其原理就是第一对中的数比第二对的都大，也都前，而你必须从每一对中选一个数放到升序序列里面，就寄了。那一猜就感觉这个是充要的。随便写点啥维护就可以了。然后对于 2 1 4 3 这种也考虑一下就可以。

题解

结论：对于一个子区间 [l,r]，有解的充要条件是：

证明： 必要性显然，可以参考“思路”。

考虑充分性，直接取出区间的 LIS，剩下的序列一定是下降序列。反证，不妨假设剩下的序列中存在 i<j,a_i<a_j。为什么他俩不在 LIS 中呢，肯定满足两个条件之一：

  1. 他们都小于 LIS 中他们前面的部分，且他们前面至少有两个数
  2. 他们都大于 LIS 中他们后面的部分，且他们后面至少有两个数。

否则，我们一定可以把这两个数调进 LIS。但以上两个条件与（\star）矛盾。

实现部分的说明由 @RSY 书写。感谢他。

这两种情况是相反的，可以用完全一致的方式处理，具体而言可以对于所有 i 维护出 f_i 表示以 i 为左端点的相对大小为上述关系的子序列的最小右端点，这样只需要将两次计算出的 f 取个 max 后就可以计算答案。以 3 4 1 2 为例，对于 3，只需要考虑最近的 4，因此可以在每个 4 的位置枚举 3 计算答案，同时在右侧找到这个 3 对应的最近的 2。实现时可以先对于每个 2 先找到最靠近的 1，在 1 加入时更新 2 的位置；再对于每个 3 找到最靠近的 4，在 4 加入时枚举 3 查询最近的 2 。需要用数据结构维护小于某一个值的最小位置，不难用树状数组处理。

# include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, a[N], min_r[N], fen[N];
long long ans;
stack <int> sk;
vector <int> vec[2][N];

void mofen(int pos, int val){
    for (pos += 5; pos < N; pos += pos & - pos)
        fen[pos] = min(fen[pos], val);
}
int gefen(int pos){
    int res = n + 1;
    for (pos += 5; 0 < pos; pos -= pos & - pos)
        res = min(res, fen[pos]);
    return res;
}

void find_3412(){
    fill(fen, fen + n + 10, n + 1);
    while (!sk.empty())
        sk.pop();
    for (int i = 1; i <= n; ++ i){
        while (!sk.empty() && a[i] < a[sk.top()])
            sk.pop();
        if (!sk.empty())
            vec[0][sk.top()].push_back(i);
        sk.push(i);
    }
    while (!sk.empty())
        sk.pop();
    for (int i = n; 1 <= i; -- i){
        while (!sk.empty() && a[sk.top()] < a[i])
            sk.pop();
        if (!sk.empty())
            vec[1][sk.top()].push_back(i);
        sk.push(i);
    }
    for (int i = n; 1 <= i; -- i){
        for (int ind : vec[0][i])
            mofen(a[ind], ind);
        for (int ind : vec[1][i])
            min_r[ind] = min(min_r[ind], gefen(a[ind] - 1));
        vec[0][i].clear(), vec[1][i].clear();
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++ i)
        cin >> a[i];
    fill(min_r, min_r + n + 2, n + 1);
    find_3412();
    for (int i = 1; i <= n; ++ i)
        a[i] = n + 1 - a[i];
    find_3412();
    for (int i = n; 1 <= i; -- i){
        min_r[i] = min(min_r[i], min_r[i + 1]);
        ans += min_r[i] - i;
    }
    cout << ans << '\n';

    return 0;
}