Codeforces 1067E Range Deleting
题目链接
https://codeforces.com/contest/1167/problem/E
题目大意
给你一个长度为 $n$ 的数列 $a$ ，保证对于所有 $1 \leq i \leq n$ 有 $a_i \leq x$ 成立，定义 $f(l, r)$ 为删除所有满足 $l \le a_i \le r$ 的数之后所剩下的数列。问使得这个数列为不下降序列的 $l, r$ 共有多少对。
题目分析
考虑如果令 $l = l_0$ ，那么一定可以确定一个最小的 $r_0$ 使得 $f(l_0, r_0)$ 满足题意，对于所有的 $r \geq r_0$ 都满足题意。此时如果将 $l$ 变为 $l_0 + 1$ ，如果能保证前 $l$ 个数满足题意，那么显然 $r_0$ 一定是不移动或者向右移动，只需要向右移动直到不冲突即可。对于 $l = 1$ 时，显然从后往前扫即可确定出第一个 $r$，依次向后扫即可。注意考虑数列中没有出现的数。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e6 + 5;
int n, m, t;
int a[maxn];
int f[maxn][2];
int read(){
int x;
scanf("%d", &x);
return x;
}
int main(){
int i, j;
int l, r = 2;
int minx = 0x3f3f3f3f, maxx = 0;
long long ans = 0;
n = read();
m = read();
for(i=1;i<=n;i++){
a[i] = read();
if(!f[a[i]][0]){
f[a[i]][0] = f[a[i]][1] = i;
}else{
f[a[i]][1] = i;
}
}
for(i=m;i>0;i--){
if(f[i][0]){
if(f[i][1] < minx){
minx = f[i][0];
}else{
r = i + 1;
break;
}
}
}
ans += m - r + 2;
l = r;
for(i=1;i<m;i++){
if(!f[i][0]){
l = max(l, i + 2);
ans += m - l + 2;
continue;
}
if(f[i][0] > maxx){
maxx = f[i][1];
r = max(r, i + 1);
while(r <= m){
if(f[r][0]){
if(f[r][0] < maxx){
l = r + 1;
}else{
break;
}
}
r++;
}
l = max(l, i + 2);
ans += m - l + 2;
}else{
break;
}
}
printf("%lld\n", ans);
return 0;
}