World is Exploding

Problem Description

Given a sequence A with length n,count how many quadruple (a,b,c,d) satisfies:

Input

The input consists of multiple test cases.
Each test case begin with an integer n in a single line.

The next line contains n integers

Output

For each test case,output a line contains an integer.

Sample Input

2 4 1 3

1 2 3 4

Sample Output

Insipired by http://blog.csdn.net/libin66/article/details/52098019

题意：比较简单直接看。

思路：分别求出在 i 的时候前面有多少比它小的（即像Aa，Ab这样升序的有多少对），用up记录，后面有多少比它小的（像Ac，Ad这样降序的有多少对），用down记录，然后ans = up * down，因为有很多重复。用树状数组维护四个数组，ls —— 在[1,i-1]有多少比a[i]小的，rs —— 在[i+1,n]有多少比a[i]小的，lb —— 在[1,i-1]有多少比a[i]大的，rb —— 在[i+1,n]有多少比a[i]大的。由容斥原理要减去 ( ls * lb + rs * rb + ls * rs + lb * rb )。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 #define N 50005
 6 #define MOD 1000000007
 7 typedef long long LL;
 8 LL ls[N], lb[N], rs[N], rb[N], bit[N];
 9 int a[N], num[N], n, m;
10 
11 /*
12 ls和lb是[1,i-1]中比a[i]小的数的数量，比a[i]大的数的数量
13 rs和rb是[i+1, n]中比a[i]小的数的数量，比a[i]大的数的数量
14 这些都可以通过树状数组实现
15 由于答案会多算进去a=c || a=d || b=c || b=d的情况，那么枚举这四种情况减去就可以了(a=c那么必定b!=d，同理其他
16 a=c：ans-=rs[i]*rb[i]
17 a=d：ans-=lb[i]*rb[i]
18 b=c：ans-=ls[i]*rs[i]
19 b=d：ans-=lb[i]*ls[i]
20 */
21 
22 void init()
23 {
24     memset(ls, 0, sizeof(ls));
25     memset(lb, 0, sizeof(lb));
26     memset(rs, 0, sizeof(rs));
27     memset(rb, 0, sizeof(rb));
28     memset(sum, 0, sizeof(sum));
29 }
30 
31 int lowbit(int x)
32 {
33     return x & (-x);
34 }
35 
36 void update(int pos)
37 {
38     while(pos <= m) {
39         bit[pos]++;
40         pos += lowbit(pos);
41     }
42 }
43 
44 LL query(int pos)
45 {
46     LL ans = 0;
47     while(pos > 0) {
48         ans += bit[pos];
49         pos -= lowbit(pos);
50     }
51     return ans;
52 }
53 
54 int main()
55 {
56     while(~scanf("%d", &n)) {
57         init();
58         for(int i = 1; i <= n; i++) {
59             scanf("%d", &a[i]);
60             num[i] = a[i];
61         }
62         sort(a+1, a+1+n);
63         m = unique(a+1, a+1+n) - (a+1);
64         for(int i = 1; i <= n; i++)
65             num[i] = lower_bound(a+1, a+1+m, num[i]) - a;
66 
67         LL up = 0, down = 0;
68         memset(bit, 0, sizeof(bit));
69         for(int i = 1; i <= n; i++) {
70             ls[i] = query(num[i] - 1);
71             lb[i] = query(m) - query(num[i]);
72             up += ls[i];
73             update(num[i]);
74         }
75 
76         memset(bit, 0, sizeof(bit));
77         for(int i = n; i >= 1; i--) {
78             rs[i] = query(num[i] - 1);
79             rb[i] = query(m) - query(num[i]);
80             down += rs[i];
81             update(num[i]);
82         }
83 
84         LL ans = 0;
85 
86         for(int i = 1; i <= n; i++) {
87             ans -= ls[i] * lb[i];
88             ans -= rs[i] * ls[i];
89             ans -= rb[i] * lb[i];
90             ans -= rb[i] * rs[i];
91         }
92 
93         printf("%I64d
", up * down + ans);
94     }
95     return 0;
96 }