思路1：枚举+二分

考虑任选一个区间 $[l, r]$ 删除，剩余的左部分是 $[1,l-1]$ ，右部分是 $[r+1,n]$

需要保证 $a[1,l-1]$ 是单调递增，$a[r+1,n]$ 也是单调递增的，且满足 $a[l-1]\leq a[r+1]$

枚举区间 $[l,r]$ 的左端点 $left$，，来二分出区间的右端点 $right$，check 函数是 $a[left-1]\leq a[right+1]$

我们需要保证 $a[1]\leq a[2]\leq \cdots\leq a[left-1]$ ，所以枚举左端点 $left$ ，直到 $a[left]<a[left-1]$ 停止。

之后需要确定 $right$ ，满足 $a[left-1]\leq a[right+1]\leq a[right+2]\leq \cdots\leq a[n]$ 。

这部分可以用二分答案来解决，而我们需要保证二分的区间是递增的，所以需要先预处理出最长的单调递增的后缀。

时间复杂度：$O(n\log n)$

代码

n = int(input())
a = list(map(int, input().split()))
a = [0] + a + [2 * 10 ** 9]

# 预处理后缀
# 通过枚举 left ，确定 right
# a[left - 1] <= a[right + 1]
ok = [False for _ in range(len(a))]
ok[n + 1] = True
min_r = n
for i in range(n, -1, -1):
    if ok[i + 1] and a[i] <= a[i + 1]:
        ok[i] = True
        min_r = i
    else:
        break

# 枚举区间左端点 left
# 二分区间右端点 right
ans = 0
for left in range(1, n + 1):
    l, r = max(left, min_r - 1), n
    while l < r:
        right = (l + r) >> 1
        if a[right + 1] >= a[left - 1]:
            r = right
        else:
            l = right + 1

    ans += n - l + 1

    if a[left] < a[left - 1]:
        break

print(ans)

思路2：双指针

从上面的思路来看，我们枚举左端点，值是单调递增的，那么对于越大的左端点来说，其右端点位置也必然是单调递增的。

所以可以预处理出后缀单调递增的起始位置。从这个位置 $right$ 开始，我们枚举左端点 $left$ ，不断移动右端点 $right$ 使得 $a[right+1]\geq a[left-1]$ 即可。

时间复杂度：$O(n)$

python

n = int(input())
a = list(map(int, input().split()))
a = [0] + a + [2 * 10 ** 9]

min_r = n
for i in range(n, 0, -1):
    if a[i] <= a[i + 1]:
        min_r = i
    else:
        break

ans = 0
right = min_r - 1
for left in range(1, n + 1):
    right = max(right, left)
    while right <= n and a[right + 1] < a[left - 1]:
        right += 1
    ans += n - right + 1
    if a[left] < a[left - 1]:
        break

print(ans)

C++

#include <bits/stdc++.h>


using namespace std;
typedef long long ll;
int t;

const int mod = 1e9 + 7;
ll ans2 = 0;

bool check(vector<int> &c) {
    for (int i = 0; i < c.size(); i++) {
        //cout  << c[i] << " ";
    }
    for (int i = 1; i < c.size(); i++) {
        if (c[i] < c[i - 1]) {
            return false;
        }
    }
    return true;
}

void bf(vector<int> &a) {
    ans2 = 0;
    for (int l = 0; l < a.size(); l++) {
        for (int r = l; r < a.size(); r++) {
            vector<int> c;
            for (int i = 0; i < l; i++) {
                c.push_back(a[i]);
            }
            for (int i = r + 1; i < a.size(); i++) {
                c.push_back(a[i]);
            }
            if (check(c)) {
                //cout << l << " " << r << endl;
                ans2++;
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
       // a[i] = rand() % 5 + 1;
    }
    vector<int> pre;
    vector<int> preId;
    vector<int> nxt;
    vector<int> nxtId;
    pre.push_back(a[0]);
    preId.push_back(0);
    for (int i = 1; i < n; i++) {
        if (a[i] >= a[i - 1]) {
            pre.push_back(a[i]);
            preId.push_back(i);
        } else {
            break;
        }
    }
    nxt.push_back(a[n - 1]);
    nxtId.push_back(n - 1);
    for (int i = n - 2; i >= 0; i--) {
        if (a[i] <= a[i + 1]) {
            nxt.push_back(a[i]);
            nxtId.push_back(i);
        } else {
            break;
        }
    }
    reverse(nxt.begin(), nxt.end());
    reverse(nxtId.begin(), nxtId.end());
    ll ans = 1ll * nxt.size() * (nxt.size() + 1) / 2;
    //bf(a);
    if (preId[0] != nxtId[0]) {
        ans = (int) pre.size() + (int) nxt.size() + 1;
        for (int i: pre) {
            int id = lower_bound(nxt.begin(), nxt.end(), i) - nxt.begin();
            ans += (nxt.size() - id);
        }
    }
    cout << ans << endl;
    /*if (ans2 != ans) {
        cout << "WA" << ans2 << " " << ans << endl;
        for (int i: a) {
            cout << i << " ";
        }
        cout << endl;
        exit(0);
    } else {
        cout << "AC" << endl;
    }*/

}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
    //cin >> t;
    t = 1;
    while (t--) {
        solve();
    }

}

java

#include <bits/stdc++.h>


using namespace std;
typedef long long ll;
int t;

const int mod = 1e9 + 7;
ll ans2 = 0;

bool check(vector<int> &c) {
    for (int i = 0; i < c.size(); i++) {
        //cout  << c[i] << " ";
    }
    for (int i = 1; i < c.size(); i++) {
        if (c[i] < c[i - 1]) {
            return false;
        }
    }
    return true;
}

void bf(vector<int> &a) {
    ans2 = 0;
    for (int l = 0; l < a.size(); l++) {
        for (int r = l; r < a.size(); r++) {
            vector<int> c;
            for (int i = 0; i < l; i++) {
                c.push_back(a[i]);
            }
            for (int i = r + 1; i < a.size(); i++) {
                c.push_back(a[i]);
            }
            if (check(c)) {
                //cout << l << " " << r << endl;
                ans2++;
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
       // a[i] = rand() % 5 + 1;
    }
    vector<int> pre;
    vector<int> preId;
    vector<int> nxt;
    vector<int> nxtId;
    pre.push_back(a[0]);
    preId.push_back(0);
    for (int i = 1; i < n; i++) {
        if (a[i] >= a[i - 1]) {
            pre.push_back(a[i]);
            preId.push_back(i);
        } else {
            break;
        }
    }
    nxt.push_back(a[n - 1]);
    nxtId.push_back(n - 1);
    for (int i = n - 2; i >= 0; i--) {
        if (a[i] <= a[i + 1]) {
            nxt.push_back(a[i]);
            nxtId.push_back(i);
        } else {
            break;
        }
    }
    reverse(nxt.begin(), nxt.end());
    reverse(nxtId.begin(), nxtId.end());
    ll ans = 1ll * nxt.size() * (nxt.size() + 1) / 2;
    //bf(a);
    if (preId[0] != nxtId[0]) {
        ans = (int) pre.size() + (int) nxt.size() + 1;
        for (int i: pre) {
            int id = lower_bound(nxt.begin(), nxt.end(), i) - nxt.begin();
            ans += (nxt.size() - id);
        }
    }
    cout << ans << endl;
    /*if (ans2 != ans) {
        cout << "WA" << ans2 << " " << ans << endl;
        for (int i: a) {
            cout << i << " ";
        }
        cout << endl;
        exit(0);
    } else {
        cout << "AC" << endl;
    }*/

}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
    //cin >> t;
    t = 1;
    while (t--) {
        solve();
    }

}

题目描述

小红有一个长度为$n$的数组$a$，他想要使得数组$a$有序(单调不降），他必须选择一段区间$[l,r](1\le l,r\le n)$，将数组的这一段删除，其他的部分(如果存在的话)就按顺序拼在一起。 现在他想知道有多少种不同的选择区间的方案。

输入描述

第一行一个正整数$n(1≤n≤2\times 10^5)$，表示数组的长度。

第二行$n$个正整数$a_i(1≤a¡≤ 10^9)$，表示数组$a$。

输出描述

输出一行一个正整数表示答案。

样例

输入

3
1 2 3

输出

6

说明

可以选择:
[1, 1], [2, 2], [3, 3], [1, 2], [2, 3], [1, 3]
这六个区间