比赛 2024暑假C班集训5 评测结果 AAAAAAAAAA
题目名称 充电宝 最终得分 100
用户昵称 darkMoon 运行时间 0.300 s
代码语言 C++ 内存使用 9.47 MiB
提交时间 2024-07-05 09:15:57
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
ifstream fin("charger.in");
ofstream fout("charger.out");
auto mread = [](){
    int x;
    fin >> x;
    return x;
};
const int N = 2e5 + 5;
int n = mread(), a[N], la[N], to[N], s[N];
void add(int x, int k){
    while(x <= n){
        s[x] += k;
        x += x & -x;
    }
    return;
}
int query(int x){
    int ans = 0;
    while(x){
        ans += s[x];
        x -= x & -x;
    }
    return ans;
}
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
signed main(){
    for(int i = 1; i <= n; i ++){
        a[i] = mread();
        la[i] = n + 1;
    }
    for(int i = n; i >= 1; i --){
        to[i] = la[a[i]] - 1;
        la[a[i]] = i;
    }
    for(int i = 1; i <= n; i ++){
        la[i] = 0;
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        while(q.size() && q.top().fi == i){
            auto tmp = q.top();
            q.pop();
            add(tmp.se, -1);
//            printf("--- %lld %lld %lld\n", i, tmp.fi, tmp.se);
        }
        int l = la[a[i]] + 1;
        la[a[i]] = i;
        ans += query(n) - query(l - 1);
        add(i, 1);
        q.push(mp(to[i] + 1, i));
//        printf("*** %lld %lld %lld\n", i, l, to[i]);
    }
    fout << ans;
}