solution-cf830b

CaiXY06 · 2021-08-20 21:52:35 · 题解

看到大家都是数据结构的做法，那我就来篇不一样的吧。

我们观察到 a_i\leq 10^5，所以我们可以对于所有值记录下其在 a 中出现的位置，然后从小到大枚举数值进行暴力跳位置以及运算。具体实现我们可以使用链表或者 set。时间复杂度：采用链表的话是 O(n) 的，set 是 O(n\log n) 的。这里我们采用 set（毕竟写写方便不是么）。详细请见代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[100010];
set<int>S[100010];//开1e5个set存下每个值出现的位置
set<int>::iterator it;//指针
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        S[a[i]].insert(i);//插入位置
    }
    sort(a+1,a+n+1);//将数值从小到大排序，免去枚举无值的set
    int p=1;long long ans=n;//p记录当前在a中的位置
    for(int i=1;i<=n;i++){
        it=S[a[i]].lower_bound(p);//二分查找当前数值第一个出现在p之后的位置
        if(it==S[a[i]].end())ans+=n-i+1,p=1,it=S[a[i]].lower_bound(p);//如果当前数值已经没有在p之后的，就从头重新找
        p=*it,S[a[i]].erase(it);
    }
    printf("%lld",ans);
    return 0;
}