Codeforces

Codeforces 459D

https://codeforces.com/contest/459/problem/D
這題給定一個長度為n的數列a，要找所有數對(i, j)滿足f(1, i, a_i) > f(j, n, a_j)，f(l, r, x)定義為在[i,j]之間=x的個數。

這題的作法和逆序數對相同，只不過update和query的東西不同而已，我會先求出所有的f(1, i, a_i)，在由後往前計算答案。我因為沒算到會超過int吃了一次WA(<-母湯。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
int n;
vector<long long> BIT;

void update(int x)
{
    for(; x <= n; x += lowbit(x))
    {
        ++BIT[x];
    }
}

long long  query(int x)
{
    long long  ans = 0;
    for(; x > 0; x -= lowbit(x))
    {
        ans += BIT[x];
    }
    return ans;
}

int main()
{
    vector<long long> v, v1, cnt, F; //f(i) = f(1,i,a_i) 
    cin >> n;
    v.resize(n);
    cnt.resize(n);
    F.resize(n);
    for(int i = 0; i != n; ++i)
    {
        cin >> v[i];
        v1.push_back(v[i]);
    }
    sort(v1.begin(), v1.end());
    v1.resize(unique(v1.begin(), v1.end()) - v1.begin());
    for(int i = 0, no; i != n; ++i)
    {
        no = lower_bound(v1.begin(), v1.end(), v[i]) - v1.begin();
        ++cnt[no];
        F[i] = cnt[no];
    }

    long long ans = 0;
    BIT.resize(2 * n, 0);
    for(int i = n - 1, no; i >= 0; --i)
    {
        no = lower_bound(v1.begin(), v1.end(), v[i]) - v1.begin();
        int q = cnt[no] - F[i] + 1;
        // cout << no << ' ' << F[i] << ' ' << q << '\n';
        ans += query(F[i] - 1);
        // cout << ans << '\n';
        update(q);
    }
    cout << ans << '\n';
}

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts