CF #261 Div2 D. Pashmak and Parmida's problem （離散化+逆序對+線段樹）

CF #261 Div2 D. Pashmak and Parmida's problem （離散化+逆序對+線段樹）

Parmida is a clever girl and she wants to participate in Olympiads this year. Of course she wants her partner to be clever too (although he's not)! Parmida has prepared the following test problem for Pashmak.

There is a sequence a that consists of n integers a₁,?a₂,?...,?a_n. Let's denote f(l,?r,?x) the number of indices k such that: l?≤?k?≤?r and a_k?=?x. His task is to calculate the number of pairs of indicies i,?j (1?≤?i?j?≤?n) such that f(1,?i,?a_i)?>?f(j,?n,?a_j).

Help Pashmak with the test.

Input

The first line of the input contains an integer n (1?≤?n?≤?10⁶). The second line contains n space-separated integers a₁,?a₂,?...,?a_n (1?≤?a_i?≤?10⁹).

Output

Print a single integer — the answer to the problem.

Sample test(s) Input

7
1 2 1 1 2 2 1

Output

8

Input

3
1 1 1

Output

1

Input

5
1 2 3 4 5

Output

0

題目給出的F函數，可以用離散的方法加預處理 將每個F（1，i，x）和F（j，n，x）求出，分別保存於f1, f2數組，那麼題目就可以轉化為： f1[i] > f2[j] && i < j , 求出滿足條件的個數，和逆序對的思想基本一樣，但本題不好用歸並排序解決，因為牽扯到兩個數組，那麼可以考慮線段樹解決。

#include 
#include 
#include 
#include 
#include 
#include 
#define lson o << 1, l, m
#define rson o << 1|1, m+1, r
using namespace std;
typedef long long LL;
const int MAX = 200000000;
const int maxn = 1000100;
int n, a, b;
int vis[maxn], tt[maxn], in[maxn], f1[maxn], f2[maxn], num[maxn<<2], fu[maxn];
int bs(int v, int x, int y) {
    int m;
    while(x < y) {
        m = (x+y) >> 1;
        if(fu[m] >= v) y = m;
        else x = m+1;
    }
    return x;
}
void up(int o) {
    num[o] = num[o<<1] + num[o<<1|1];
}
void update(int o, int l, int r) {
    if(l == r) num[o]++;
    else {
        int m = (l+r) >> 1;
        if(a <= m) update(lson);
        else update(rson);
        up(o);
    }
}
LL query(int o, int l, int r) {
    if(a <= l && r <= b) return num[o];
    int m = (l+r) >> 1;
    LL res = 0;
    if(a <= m) res += query(lson);
    if(m < b ) res += query(rson);
    return res;
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) {
        scanf("%d", &in[i]);
        tt[i] = in[i];
    }
    sort(in, in+n);
    int k = 0;
    fu[k++] = in[0];
    for(int i = 1; i < n; i++)
        if(in[i] != in[i-1]) fu[k++] = in[i];
    for(int i = 0; i < n; i++) {
        int tmp = bs(tt[i], 0, k-1);
        vis[tmp]++;
        f1[i] = vis[tmp];
    }
    memset(vis, 0, sizeof(vis));
    for(int i = n-1; i >= 0; i--) {
        int tmp = bs(tt[i], 0, k-1);
        vis[tmp]++;
        f2[i] = vis[tmp];
        b = max(b, f2[i]);
    }
    LL ans = 0;
    for(int i = 0; i < n; i++) {
        a = f2[i]+1; ans += query(1, 0, b);
        a = f1[i]; update(1, 0, b);
    }
    cout << ans << endl;
    return 0;
}