E. Range Deleting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an array consisting of nn integers a1,a2,…,ana1,a2,…,an and an integer xx. It is guaranteed that for every ii, 1≤ai≤x1≤ai≤x.
Let's denote a function f(l,r)f(l,r) which erases all values such that l≤ai≤rl≤ai≤r from the array aa and returns the resulting array. For example, if a=[4,1,1,4,5,2,4,3]a=[4,1,1,4,5,2,4,3], then f(2,4)=[1,1,5]f(2,4)=[1,1,5].
Your task is to calculate the number of pairs (l,r)(l,r) such that 1≤l≤r≤x1≤l≤r≤x and f(l,r)f(l,r) is sorted in non-descending order. Note that the empty array is also considered sorted.
Input
The first line contains two integers nn and xx (1≤n,x≤1061≤n,x≤106) — the length of array aa and the upper limit for its elements, respectively.
The second line contains nn integers a1,a2,…ana1,a2,…an (1≤ai≤x1≤ai≤x).
Output
Print the number of pairs 1≤l≤r≤x1≤l≤r≤x such that f(l,r)f(l,r) is sorted in non-descending order.
Examples
input
Copy
3 3 2 3 1
output
Copy
4
input
Copy
7 4 1 3 1 2 2 4 3
output
Copy
6
Note
In the first test case correct pairs are (1,1)(1,1), (1,2)(1,2), (1,3)(1,3) and (2,3)(2,3).
In the second test case correct pairs are (1,3)(1,3), (1,4)(1,4), (2,3)(2,3), (2,4)(2,4), (3,3)(3,3) and (3,4)(3,4).
题意：
给n个数和x，让你找出来有多少f(l,r) (1 <= l,r <= x)，被删去后可以使得当前的数列变成非递减序列
定义：f(l,r)代表所有数中l到r的数
思路：
假如现在有f(l,r)是满足的，那么说明所有1~(l - 1)最后出现的位置要< (r + 1)~x第一次出现的位置，另外对于每个1~(l - 1)个元素所有的i 和 i - 1也要满足这个条件，即i - 1的最右边要<i的最左边，r + 1到x也是一样。如果这样的话，对于f(l,r)就可以继续r++，或者l--，他都是会满足这个条件的，所以就可以利用双指针来计数
处理出每个数出现的最左边和最右边，然后再跑前缀和后缀，对于1~i，所有数出现的最大下标，对于i~n所有数出现的最小的下标，再跑出可以满足删除f(l,r)条件的前后缀，l、r最远位置，pre,post是前后缀最远的位置，precan、postcan是是否满足前后缀可行
代码：
int l[maxn],r[maxn];
int precan[maxn],postcan[maxn],vis[maxn];
int pre[maxn],post[maxn];
bool check(int ll,int rr){ if(!precan[ll - 1] || !postcan[rr + 1]) return false;if(pre[ll - 1] > post[rr + 1]) return false;return true;
}
int main(){ios::sync_with_stdio(false);int x; while(cin >> n >> x){ for(int i = 1;i <= n;i++) cin >> a[i],vis[a[i]] = 1;MS0(l),MS0(r); memset(l,INF,sizeof(l));for(int i = 1;i <= n;i++){ if(l[a[i]] == INF) l[a[i]] = i;r[a[i]] = i;} memset(post,INF,sizeof(post));for(int i = 1;i <= x;i++){ pre[i] = max(pre[i - 1],r[i]); } for(int i = x;i >= 1;i--) post[i] = min(post[i + 1],l[i]); l[x + 1] = INF,r[x + 1] =INF ;precan[0] = postcan[x + 1] = 1;int l1 = INF,r1 = 0; for(int i = 1;i <= x;i++){ if(!vis[i] ){ if(precan[i - 1]) precan[i] = 1;}else if(precan[i - 1] && l[i] >= r1){ precan[i] = 1;if(r[i] ) r1 = max(r1,r[i]);} }for(int i = x;i >= 1;i--){ if(!vis[i]){ if(postcan[i + 1]) postcan[i] = 1;}else if(postcan[i + 1] && r[i] <= l1){postcan[i] = 1; if(l[i])l1 = min(l1,l[i]);} } int L = 1,R = 1; ll ans = 0; while(R <= x){ while(L > R) R++;while(R < x && !check(L,R)) R++; // cout << L << " --- " << R << endl;if(check(L,R)) ans += x - R + 1 ; L++;}wt(ans);}return 0;}