题意：给出数组A，定义f(l,r,x)为A[]的下标l到r之间，等于x的元素数。i和j符合f(1,i,a[i])>f(j,n,a[j])，求i和j的种类数。
我们可以用map预处理出 f(1, i, a[i]) 和 f(j, n, a[j]) ，记为s1[n], s2[n]。
这样就变成求满足 s1[i] > s[j]， i < j 情况的数量了,你会发现跟求逆序对一样
分析：
做题的时候想到过逆序数，但是很快放弃了，还是理解不深刻吧，，，233.
看了这个博客以后才明白这些过程：http://www.cnblogs.com/yuiffy/p/3916512.html
使用树状数组统计小于某数的元素数量。
我们可以先把f(1,i,a[i])和f(j,n,a[j])写出来，观察一下，例如样例1：
n=7
A 1 2 1 1 2 2 1
R 4 3 3 2 2 1 1
L 1 1 2 3 2 3 4
其中A为给定的数组，Rj为f(j,n,a[j])，Li为f(1,i,a[i])。
对每个Li，我们要统计的其实就是符合（j>i，且Rj<Li）的Rj的个数。就是这个Li右边有多少个比它小的Rj。
这样我们可以用树状数组，把Rj各个数的数量全存到树状数组里，例如这个样例就是4有1个，3有2个，2有2个，1有2个。然后从左到右遍历Li，每次从树状数组里删掉Rj，并且求sum(Li-1)，也就是树状数组中1~Li-1的和，也就是比Li小的元素个数。
例如这个样例，到L3时，树状数组里记了2个1和2个2（1个4和2个3在之前被删掉了），L3=2，则sum(L3-1)=sum(2)=1的数量+2的数量=3。ans+=3。
其实从左到右加一遍以后，树状数组是这个样子的：
下标 1 2 3 4
值 2 2 2 1
不能不说这个过程还是挺难想的
时间复杂度是O(n*log(n));
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <algorithm>
#define LL __int64
const int maxn = +;
using namespace std;
int c[maxn], a[maxn], n; int lowbit(int x)
{
return x&(-x);
}
void add(int x,int d)
{
while(x <= n)
{
c[x] += d;
x +=lowbit(x);
}
}
LL sum(int x)
{
LL ret = ;
while(x > )
{
ret += c[x];
x -= lowbit(x);
}
return ret;
}
void slove()
{
map<int, int>x, y;
LL ans = ;
int i;
memset(c, , sizeof(c)); for(i = ; i <= n; i++)
{
scanf("%d", &a[i]);
x[a[i]] ++;
add(x[a[i]], ); //其实树状数组里的下标代表个数，数组里的数代表扫过去的依次产生的该个数的数量。
}
for(i = ; i <= n; i++)
{
y[a[i]] ++; //要查找的数量++
add(x[a[i]], -); //依次把原来的-1
x[a[i]] --; //x[]里也要减去
ans += sum(y[a[i]]-); //求从1到 比当前的个数少一的个数的和。
}
printf("%I64d\n", ans);
} int main()
{
while(~scanf("%d", &n))
{
slove();
}
return ;
}