codeforces 459 D. Pashmak and Parmida's problem (离散化+线段树求逆序对数)
题目链接 题意：定义_f_(l, r, x)为区间[l,r]中x出现的次数。现在要求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).
思路：可以通过o(n)预处理出f(1,i,a[i])和f[j,n,a[j]]，其实预处理的过程就是离散化的过程呢。。。
分别得到
1 1 2 3 2 3 4
4 3 3 2 2 1 1
所以答案其实就是第一组数在第二组数中找逆序数的过程。。。
我们不妨倒序处理。
需要注意的是，线段树维护的区间是0..mx，我整体增加了1.
线段树求逆序对和树状数组求逆序对是同样的思想。。。注意体会。。
1/* ***********************************************
2Author :111qqz
3Created Time :Mon 05 Sep 2016 02:06:05 PM CST
4File Name :code/cf/problem/459D.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=1E6+7;
32map<int,int>mp;
33int n ;
34int a[N],b[N];
35int tmp[N];
36int tree[N<<2];//tree[i]表示的是以i节点为根节点的子树所代表的区间中数的个数。
37void PushUp( int rt)
38{
39 tree[rt] = tree[rt<<1] + tree[rt<<1|1];
40}
41void update(int p,int l,int r,int rt)
42{
43 if (l==r)
44 {
45 tree[rt]++;
46 return;
47 }
48 int m = (l+r)>>1;
49 if (p<=m) update(p,lson);
50 else update(p,rson);
51 PushUp(rt);
52}
53int query(int L,int R,int l,int r,int rt)
54{
55 if (L<=l&&r<=R) return tree[rt];
56 int m = (l+r)>>1;
57 int ret = 0;
58 if (L<=m)
59 {
60 int res = query(L,R,lson);
61 ret +=res;
62 }
63 if (R>=m+1)
64 {
65 int res = query(L,R,rson);
66 ret +=res;
67 }
68 return ret;
69}
70int main()
71{
72 #ifndef ONLINE_JUDGE
73 freopen("code/in.txt","r",stdin);
74 #endif
75 cin>>n;
76 mp.clear();
77 int mx = 0 ;
78 for ( int i = 1 ; i <= n ; i++)
79 {
80 int x;
81 scanf("%d",&x);
82 tmp[i] = x;
83 if (!mp[x]) mp[x] = 2; //mp表示的是出现的次数。。。是从0开始，但是线段树下标从1开始，因此整体+1,也就是第一次出现的时候设为2.
84 else mp[x]++;
85 a[i] = mp[x];
86 mx = max(mx,a[i]);
87 }
88 mp.clear();
89 for ( int i = n ; i >= 1; i--)
90 {
91 int x = tmp[i];
92 if (!mp[x]) mp[x] = 2;
93 else mp[x]++;
94 b[i] = mp[x];
95 }
96 ms(tree,0);
97 LL ans = 0 ;
98 for ( int i = n ; i >=1 ; i--)
99 {
100 ans = ans + LL(query(1,a[i]-1,1,mx,1));//查询在在a[i]之前插入的（下标比i大）且比a[i]小（因此查询区间是1..a[i]-1)的数的个数。
101 update(b[i],1,mx,1); //在b[i]位置插入一个数。
102 }
103 cout<<ans<<endl;
104 #ifndef ONLINE_JUDGE
105 fclose(stdin);
106 #endif
107 return 0;
108}