Algoogle

Algorithm for Programming Contest

Codeforces 459D Pashmak and Parmida’s problem

Category: Codeforces Tag: binary-indexed-tree

Pashmak and Parmida’s problem

問題概要


長さn数列bについて以下を満たすi, jの組の個数を求めよ.

  • 区間[0,i]に出現するb[i]の個数 > 閉区間[j,n)に出現するb[j]の個数

解法


区間[j,n)に存在するb[j]の個数はj=n-1からmapでカウントしていけば求められる.
これをg[j]とする.
同様に[0,i]に存在するb[i]の個数も求められるのでf[i]とする.

fを予め求めておく.
f[i]に対してそれより小さいg[j](i<j)の数は区間[i+1,n)でg[j]の値をインデックスとしてその個数をもつbitをつくればlognで求められる.
よってi=n-1から順次bitを更新しながらf[i]未満になるg[j]の個数の総和を足し合わせれば良い.

コード


(459D.cpp) download
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
59
60
61
#include <bits/stdc++.h>
using namespace std;

// T have +- and 0
template<class T, int M> class bit
{
public:
        T dat[M+1];
        int N;

        bit(){}
        bit(int N) : N(N){
                fill(dat,dat+N,0);
        }
        // sum [0,i)
        T sum(int i){
                T ret = 0;
                for(--i; i>=0; i=(i&(i+1))-1) ret += dat[i];
                return ret;
        }
        // sum [i,j)
        T sum(int i, int j){ return sum(j) - sum(i);}
        // add x to i
        void add(int i, T x){ for(; i < N; i|=i+1) dat[i] += x;}
};


int n, b[1000010], f[1000010];

long long solve()
{
        map<int,int> cnt;
        bit<int,1000000> bt(n+1);
        long long ans = 0;

        for (int i = 0; i < n; i++)
                f[i] = ++cnt[b[i]];

        cnt.clear();
        for (int i = n-1; i >= 0 ; i--) {
                ans += bt.sum(f[i]);
                bt.add(++cnt[b[i]],1);
        }

        return ans;
}

void input()
{
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
                scanf("%d", b+i);
        }
}

int main()
{
        input();
        cout << solve() << endl;
        return 0;
}

Comments