Codeforces 1167E (双指针+单调性)

Codeforces 1167E
题意：给定一个序列$a_i$，求有多少种在$a$中取$a_i \in (-∞, l] \cup [r, +∞)$的方案使得取出来的数是增序排序的。

我们考虑分开两边处理，发现左边如果使$l$单调递增，那么右边的$r$也是单调递增的。

所以我们可以考虑双指针来做。

$l$增加的过程中，不能存在$a_i \in (-∞, l]$不有序的情况。$r$即为满足$a_i \in (-∞, l] \cup [r, +∞)$的最小$r$

那么我们这样就可以算方案了。

判断加进来的数能不能有序，就每个数记录一个最大出现位置和最小出现位置，判断一下大小关系即可。

知识点
程序出错的原因
1、大思路就出错了 —— 重构
2、程序上有bug —— 检查程序
3、思维上有bug —— 出数据，想特殊情况
一般情况下，错误先看程序上是否写错，然后再看思维上是否有漏洞，否则就考虑一下是否大思路是有误

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 1000000 + 5;

    LL n, x, a[MAXN];
    LL maxd[MAXN], mind[MAXN];
    LL pre[MAXN], suf[MAXN];

    void clean() {
        ms(maxd, 0), ms(mind, 0x3f);
        ms(pre, 0), ms(suf, 0x3f);
    }
    int solve() {

        clean();
        cin >> n >> x;
        for (LL i = 1; i <= n; ++i) {
            scanf("%lld", &a[i]);
            maxd[a[i]] = max(maxd[a[i]], i);
            mind[a[i]] = min(mind[a[i]], i);
        }
        for (LL i = 1; i <= x; ++i) {
            pre[i] = max(maxd[i], pre[i - 1]);
        }
        for (LL i = x; i; --i) {
            suf[i] = min(mind[i], suf[i + 1]);
        }

        LL r = 1, ans = 0, lstL = 0;

        for (LL i = x - 1; i; --i) {
            if (maxd[i] > suf[i + 1]) {
                r = i + 1; break ;
            }
        }

        for (LL l = 0; l <= x; ++l) {
            if (l && mind[l] < pre[l - 1]) break ;
            while (r <= x && suf[r] < maxd[l]) ++r;
            LL L = l + 1ll, R = r - 1ll;
            ans += (L - lstL) * (x - max(L, R) + 1ll);
            lstL = L;
        }
        cout << ans;

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}