Muutokset

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;

int a[200002];
int cnts[200002];

#define N (1<<20)
int tree[2*N];
int n,m;

int summa(int a, int b) {
    a += N; b += N;
    int s = 0;
    while (a <= b) {
        if (a%2 == 1) s += tree[a++];
        if (b%2 == 0) s += tree[b--];
        a /= 2; b /= 2;
    }
    return s;
}
 
void update(int k, int x) {
    k += N;
    tree[k] += x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = tree[2*k]+tree[2*k+1];
    }
}

vector<ll> solve() {
    for (int i = 0; i < 2*N; i++) tree[i] = 0;
    for (int i = 0; i <= n; i++) cnts[i] = 0;
    vector<ll> res;
    ll ans = 0;
    for (int i = 0; i < m; i++) {
        cnts[a[i]]++;
        update(cnts[a[i]], 1);
        update(cnts[a[i]]-1, -1);
        ans += summa(cnts[a[i]], m);
        res.push_back(ans);
    }
    return res;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> a[i];
    auto v1 = solve();
    reverse(a, a+m);
    auto v2 = solve();
    reverse(v2.begin(), v2.end());
    for (int i = 0; i < m-1; i++) {
        cout << v1[i] + v2[i+1] << " ";
    }
    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