CF #261 Div2 D. Pashmak and Parmida's problem （离散化+逆序对+线段树）_html/css

CF #261 Div2 D. Pashmak and Parmida's problem （离散化+逆序对+线段树）_html/css_WEB-ITnose

php中文网

发布： 2016-06-24 11:59:46

原创

1551人浏览过

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 a1,?a2,?...,?an. let's denote f(l,?r,?x) the number of indices k such that: l?≤?k?≤?r and ak?=?x. his task is to calculate the number of pairs of indicies i,?j (1?≤?i??f(j,?n,?aj).

Help Pashmak with the test.

Input

The first line of the input contains an integer n (1?≤?n?≤?106). The second line contains n space-separated integers a1,?a2,?...,?an (1?≤?ai?≤?109).

Output

Print a single integer ? the answer to the problem.

Sample test(s)

Input

71 2 1 1 2 2 1

登录后复制

Output

Input

31 1 1

登录后复制

Output

Input

51 2 3 4 5

登录后复制

Output

立即学习“前端免费学习笔记（深入）”；

题目给出的F函数，可以用离散的方法加预处理将每个F（1，i，x）和F（j，n，x）求出，分别保存于f1, f2数组，那么题目就可以转化为： f1[i] > f2[j] && i

标书对比王

标书对比王是一款标书查重工具，支持多份投标文件两两相互比对，重复内容高亮标记，可快速定位重复内容原文所在位置，并可导出比对报告。

查看详情

#include <stdio.h>#include <string.h>#include <algorithm>#include <math.h>#include <ctype.h>#include <iostream>#define lson o << 1, l, m#define rson o << 1|1, m+1, rusing 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;}

登录后复制

立即学习“前端免费学习笔记（深入）”；