Muutokset

#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <iostream>
#include <map>
#include <vector>
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ost = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using iii = tuple<int,int,int>;
using vi = vector<int>;
using vll = vector<ll>;

vll f(vi M) {
    int m=M.size();
    vll ans;
    ll cost=0;
    ost<iii> S;
    map<int,int> CNT;
    map<int,int> XT;
    int T=0;
    for (int i=0; i<m; i++) {
        int x = M[i];
        if (CNT.count(x)) {
            ll c = CNT[x];
            ll t = XT[x];
            ll pos = S.order_of_key(iii(-c,t,x));
            cost -= (pos+1)*c;
            ll p = S.order_of_key(iii(-c,-1,-1));
            cost += (pos-p)*c;
            S.erase(iii(-c,t,x));
        }
        XT[x] = ++T;
        ll c = ++CNT[x];
        ll pos = S.order_of_key(iii(-c,T,x));
        S.insert(iii(-c,T,x));
        cost += (pos+1)*c;
        ans.push_back(cost);
    }
    return ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m; cin>>n>>m;
    vi M(m);
    for (int&x:M) cin>>x;
    vll X = f(M);
    reverse(M.begin(), M.end());
    vll Y = f(M);
    vll ans;
    for (int i=0; i<m-1; i++) {
        ans.push_back(X[i]+Y[m-i-2]);
    }
    for (ll x:ans) cout << x << ' ';
    cout << '\n';
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED