1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
|
#include <iostream> #include <algorithm> #include <vector> #include <utility> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; #define INF 0x3f3f3f3f #define LL long long #define pb push_back #define mp make_pair #define pii pair<int,int> #define MAXN 1000010
class BIT;
int n,m,a[MAXN],map[MAXN]; vector<int>pos[MAXN]; int head[MAXN], tail[MAXN]; BIT *bit;
class BIT { public: int c[MAXN]; BIT() { reset(); } void reset() { memset(c, 0, sizeof(c)); } inline int lowbit(int x) { return x & (-x); } void add(int pos, int val) { while (pos <= n) { c[pos] += val; pos += lowbit(pos); } } LL query(int pos) { LL ans = 0LL; while (pos) { ans += c[pos]; pos -= lowbit(pos); } return ans; } };
int create_map() { sort(map, map+n); m=1; for (int i = 1; i < n; i++) if (map[i] != map[i-1]) map[m++] = map[i]; }
void create_a_pos() { for (int i = 0; i <= m; i++) pos[i].clear(); for (int i = 0; i < n; i++) { a[i] = lower_bound(map, map+m, a[i]) - map; pos[a[i]].pb(i); } }
void create_head_tail_bit() { memset(head, 0, sizeof(head)); memset(tail, 0, sizeof(tail)); bit->reset(); for (int i = 0; i < n; i++) { int x = a[i]; int size = pos[x].size(); int p = lower_bound(pos[x].begin(), pos[x].end(), i) - pos[x].begin(); head[i] = p+1; tail[i] = size - p; bit->add(tail[i], 1); } }
LL solve() { LL ans = 0LL; for (int i = 0; i < n; i++) { bit->add(tail[i], -1); LL res = bit->query(head[i]-1); ans += res; } return ans; }
int main() { bit = new BIT(); while (scanf("%d", &n) != EOF) { for (int i = 0; i < n; i++) { scanf("%d", &a[i]); map[i] = a[i]; } create_map(); create_a_pos(); create_head_tail_bit(); cout << solve() << endl; } return 0; }
|