Codeforces 1167E（思路、数据处理）

思路

• 不难想到枚举(l)，那如何高效求出最小的(r)？这样答案加上(x-r+1)即可。
• 如果(l)并没在序列里出现……没啥想法；如果(l)是序列里的数，我们可以做的事情是记下每个数出现的每个pos。观察可以发现如果某数小于(l)且在序列里出现过，则它不会被删，则：它的区间内所有跟它不同的数得都删掉；更小的数的右端点必须在它的左端点左边。
• (r)还有个限制条件就是：比如如果序列中出现(r+3)在(r+2)左边，则不得不把(r)提高到(r+2)，因此可以知道(r)始终都要大于等于一个值。
• 思路是思路，预处理和维护就是另一个故事了……

const int maxn = 1e6 + 5;
int n,x,a[maxn],premax[maxn];
vector<int> pos[maxn];
ll ans;

int main() {    
    read(n),read(x);
    rep(i,1,n) {
        read(a[i]);
        pos[a[i]].push_back(i);
        premax[i] = max(a[i],premax[i - 1]);
    }

    int p,t = n + 1;
    for (int i = x; i; i--) {
        if (pos[i].size()) {
            if (t < pos[i].back())  break;
            t = pos[i][0];
        }
        p = i;
    }

    t = -1;
    rep(l,x) {
        int r = max(l,p - 1);
        if (t > 0)  r = max(r,premax[t]);
        ans += x - r + 1;
        if (pos[l].size()) {
            if (t > pos[l][0])  break;
            t = pos[l].back();
        }
    }

    writeln(ans);
    return 0;
}