Description
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 ≤ rand ak = x. His task is to calculate the number of pairs of indicies i, j(1 ≤ i < j ≤ n) such that f(1, i, ai) > 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 Input
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
这道题，虽然请教了暾暾和蒙蒙，但毕竟他们只是提供了思路，所以对于我自己居然手撸了线段树这件事情我还是比较满意的。感觉到自己的成长，fighting!!!
这个其实是一个比较简单的线段树问题。线段树的根节点rt保留介于l和r之间的相似的数的个数。
建树的过程：
rt=1，l=1，r=n; tree[rt]=x x表示从j到n，与aj相同的元素的个数。
在建树的过程中，查询从1到i，与a[i]相同的元素的个数k大于1到k-1的个数。
由于建树是从后向前查询。所以建树完成后，查询也刚好完成，并且得到结果。
#include<iostream> #include<stdio.h> #include<map> #include<cstring> using namespace std; const int maxx = 1000000+5; map<int,int>mf; map<int,int>mb; int fro[maxx]; int bes[maxx]; int num[maxx]; int tree[maxx<<2]; void add (int index,int l,int r,int rt) { tree[rt]++; if(l==r) return; int mid=(l+r)>>1; if(index<=mid) add(index,l,mid,rt<<1); else add(index,mid+1,r,rt<<1|1); } int query(int inl,int inr,int l,int r,int rt) { //cout<<rt<<endl; // printf("rt: %d l: %d r: %d **%d***%d ",rt,l,r,inl,inr); // char a; //cin>>a; if(inl>inr) return 0; int re=0; if(inr==r&&inl==l) return tree[rt]; int mid=(l+r)>>1; if(inr<=mid) re= query(inl,inr,l,mid,rt<<1); else if(inl>mid) re= query(inl,inr,mid+1,r,rt<<1|1); else if(inl<=mid&&inr>mid) {re=(query(inl,mid,l,mid,rt<<1)+query(mid+1,inr,mid+1,r,rt<<1|1));} //cout<<re<<endl; return re; } int main() { int n; while(~scanf("%d",&n)) { mf.clear(); mb.clear(); memset(tree,0,sizeof(tree)); for(int i=0;i<n;i++) { scanf("%d",&num[i]); } for(int i=0;i<n;i++) { mf[num[i]]++; fro[i]=mf[num[i]]; } //cout<<fro[2]<<endl; long long ans=0; for(int i=n-1;i>0;i--) { mb[num[i]]++; add(mb[num[i]],1,n,1); ans+=query(1,fro[i-1]-1,1,n,1); } // for(int i=0;i<28+5;i++) // cout<<tree[i]<<endl; //cout<<"ss"<<endl; // int ans=0; //for(int i=0;i<n;i++) // { // } printf("%I64d ",ans); } }