第十八届西电程序设计竞赛-E

第十八届西电程序设计竞赛-E

九月 06, 2020

E.世界第四

题意

给出一个排列p 长度为n<5e5 其中[1,n]的数各出现一次

将区间[L,R]的MEX作为权值 问排列p所有区间的MEX和为多少

(MEX表示最小的不在该区间中出现的正整数 )

题解

注意到所有数只出现一次

考虑求各个MEX对答案的贡献

寻找MEX=1的区间有多少个

记1出现的位置为pos[1]

那么MEX=1的区间有pos[1]×(pos[1]-1)/2+(1+n-pos[1])×(n-pos[1])/2个

MEX=2的区间必须存在1但不能有2出现

1
2
3
if(n>=2&&pos[2]>pos[1])ans+=1ll*(pos[2]-pos[1])*(pos[1])*2;
else if(n>=2&&pos[2]<pos[1])ans+=1ll*(pos[1]-pos[2])*(n-pos[1]+1)*2;
//最后乘2表示MEX=2对答案的贡献前半部分是MEX=2的区间个数

到这里我们可以发现MEX=x>2的区间 必须包含1到x-1的所有数

我们维护一个leftpos和rightpos记录前1到x-1所有数最左端和最右端的位置

  • 假如x在1到x-1所有数的右侧则，即pos[x]>rightpos

    那么 就存在leftpos×(pos[i]-rightpos)个MEX=x的区间

  • 假如x在1到x-1所有数的左侧则，即pos[x]<leftpos

    那么 就存在(n-rightpos+1)×(leftpos-pos[i])个MEX=x的区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=5e5+5;
const double Pi=acos(-1);
const ll mod=1e9+7;
/*
*/
ll P[Max],pos[Max];
int main(){
    //Turnoff;
    ll n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>P[i];
        pos[P[i]]=i;
    }
    ll ans=1ll*pos[1]*(pos[1]-1)/2+1ll*(1+n-pos[1])*(n-pos[1])/2;
    //cout<<ans<<endl;
    if(n>=2&&pos[2]>pos[1])ans+=1ll*(pos[2]-pos[1])*(pos[1])*2;
    else if(n>=2&&pos[2]<pos[1])ans+=1ll*(pos[1]-pos[2])*(n-pos[1]+1)*2;
    //cout<<ans<<endl;
    ll rightpos=max(pos[1],pos[2]),leftpos=min(pos[1],pos[2]);
    for(int i=3;i<=n;i++){
        //if(pos[i]<rightpos&&pos[i]>leftpos)continue;
        if(pos[i]<leftpos){
            ans+=1ll*(n-rightpos+1)*(leftpos-pos[i])*i;
        }
        else if(pos[i]>rightpos){
            ans+=1ll*leftpos*(pos[i]-rightpos)*i;
        }
        rightpos=max(rightpos,pos[i]);
        leftpos=min(leftpos,pos[i]);
    }
    ans+=n+1;
    cout<<ans<<endl;
}