[ Educational Codeforces Round 65 (Rated for Div. 2)][二分]

You are given an array consisting of

Let's denote a function

Your task is to calculate the number of pairs

Input

The first line contains two integers

The second line contains

Output

Print the number of pairs

Examples

input

Copy

3 3
2 3 1

output

Copy

input

Copy

7 4
1 3 1 2 2 4 3

output

Copy

Note

In the first test case correct pairs are

In the second test case correct pairs are

题意：有一个含有n个元素的数组，数组元素的范围是 1<=ai<=x，你可以删除值在(l,r)的元素，问有多少种方案使删除后数组成为非严格单调递增数组

题解：固定左边界L，则右边界呈现单调性，所以可以二分。判断条件为考虑删除（L,R）之后，(1)L左边的呈现非严格单调递增，(2)R右边呈现非严格单调递增，(3)并且原数组中比L左边某一元素大并且在该元素左边的最大值应<=R，预处理一下即可二分

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define debug(x) cout<<"["<<#x<<"]"<<x<<endl;
 5 const int maxn=1e6+5;
 6 const int inf=1e8;
 7 int a[maxn],b[maxn],maxx2;
 8 bool check(ll x0,ll len){
 9     if(b[x0-1]>x0+len-1)return false;
10     if(x0+len-1<maxx2)return false;
11     return true;
12 }
13 int main() {
14     int n,x;
15     scanf("%d%d",&n,&x);
16     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
17     int maxx=a[n];
18     int minn=x;
19     for(int i=n-1;i>=1;i--){
20         if(maxx>=a[i]){
21             maxx=a[i];
22         }
23         else{
24             minn=min(a[i],minn);
25         }
26     }
27     maxx=a[1];
28     for(int i=2;i<=n;i++){
29         if(maxx>a[i]){
30             b[a[i]]=max(b[a[i]],maxx);
31             maxx2=max(maxx2,a[i]);
32         }
33         else{
34             maxx=a[i];
35         }
36     }
37     for(int i=1;i<=x;i++){
38         b[i]=max(b[i],b[i-1]);
39     }
40     ll aans=0;
41     for(int i=1;i<=minn;i++){
42         ll l=1;
43         ll r=x-i+1;
44         ll ans=-1;
45         while(l<=r){
46             ll mid=(l+r)/2;
47             if(check(i,mid)){
48                 ans=mid;
49                 r=mid-1;
50             }
51             else{
52                 l=mid+1;
53             }
54         }
55         if(ans!=-1){
56             aans+=x-(i+ans-1)+1;
57         }
58     }
59     printf("%lld
",aans);
60     return 0;
61 }
62 
63 /*
64 */

View Code

[ Educational Codeforces Round 65 (Rated for Div. 2)][二分]

相关推荐