Pashmak and Parmida's problem（树状数组）

题目链接：http://codeforces.com/contest/459/problem/D

题意： 数列A， ai表示 i-th 的值， f（i，j, x） 表示【i，j】之间x的数目， 问：当 1 <= i < j <= n， 满足 f(1, i, ai) < f（j，n, aj）的对数。

题解：分别求出两组数列  Ii = f(1, i, ai)（1<=i <= n） Jj =  f（j，n, aj）(1 <= j <= n), 然后， 从n开始， 在数列   Ij（i < j <= n）中求出   小于 Ii的个数和。

 /***Good Luck***/

 #define _CRT_SECURE_NO_WARNINGS

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <stack>

 #include <map>

 #include <queue>

 #include <vector>

 #include <set>

 #include <functional>

 #include <cmath>

 #define Zero(a) memset(a, 0, sizeof(a))

 #define Neg(a)  memset(a, -1, sizeof(a))

 #define All(a) a.begin(), a.end()

 #define PB push_back

 #define inf 0x3f3f3f3f

 #define inf2 0x7fffffffffffffff

 #define ll long long

 using namespace std;

 //#pragma comment(linker, "/STACK:102400000,102400000")

 void get_val(int &a) {

     int value = , s = ;

     char c;

     while ((c = getchar()) == ' ' || c == '\n');

     if (c == '-') s = -s; else value = c - ;

     while ((c = getchar()) >= '' && c <= '')

         value = value *  + c - ;

     a = s * value;

 }

 const int maxn = ;

 int arri[maxn], arrj[maxn];

 int arr2[maxn];

 int arr1[maxn];

 int A[maxn];

 int n;

 int  lowbit(int x) {

     return x & (-x);

 }

 int sum(int i) {

     int ret = ;

     while (i > ) {

         ret += A[i];

         i -= lowbit(i);

     }

     return ret;

 }

 void update(int pos, int val) {

     while (pos <= n) {

         A[pos] += val;

         pos += lowbit(pos);

     }

 }

 int main() {

     //freopen("data.out", "w", stdout);

     //freopen("data.in", "r", stdin);

     //cin.sync_with_stdio(false);

     scanf("%d", &n);

     for (int i = ; i <= n; ++i) {

         scanf("%d", arr1 + i);

         arr2[i] = arr1[i];

     }

     sort(arr2, arr2 + n + );           // 离散化

     int len = unique(arr2, arr2 + n) - arr2;

     for (int i = ; i <= n; ++i) {

         arr1[i] = lower_bound(arr2, arr2 + len, arr1[i]) - arr2;

     }

     Zero(arr2);

     for (int i = ; i <= n; ++i) {

         arri[i] = ++arr2[arr1[i]];

     }

     Zero(arr2);

     for (int i = n ; i > ; --i) {

         arrj[i] = ++arr2[arr1[i]];

     }

     ll count = ;

     for (int i = n; i >= ; --i) {

         count += sum(arri[i] - ) ;

         update(arrj[i], );

     }

     cout << count << endl;

     return ;

 }