From a966cdf3732ec3e635a3a1c66f5fe7f4dcf4682a Mon Sep 17 00:00:00 2001
From: crupest <crupest@outlook.com>
Date: Fri, 5 Mar 2021 20:36:34 +0800
Subject: import(solutions): Add problem 1215.

---
 works/solutions/acwing/1215.cpp | 59 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 59 insertions(+)
 create mode 100644 works/solutions/acwing/1215.cpp

(limited to 'works')

diff --git a/works/solutions/acwing/1215.cpp b/works/solutions/acwing/1215.cpp
new file mode 100644
index 0000000..d6832b3
--- /dev/null
+++ b/works/solutions/acwing/1215.cpp
@@ -0,0 +1,59 @@
+#include <cstring>
+#include <iostream>
+
+const int MAX = 1000010; // Why 1000001 is not ok!?
+
+int n;
+int H[100001];
+int bit[MAX];
+int reverse_pairs[100001];
+
+int lowbit(int x) { return x & -x; }
+
+void add(int x, int y) {
+  for (int i = x; i < MAX; i += lowbit(i)) {
+    bit[i] += y;
+  }
+}
+
+int query(int x) {
+  int result = 0;
+  for (int i = x; i != 0; i -= lowbit(i)) {
+    result += bit[i];
+  }
+  return result;
+}
+
+int main() {
+  std::ios_base::sync_with_stdio(false);
+  std::cin.tie(nullptr);
+
+  std::cin >> n;
+
+  for (int i = 1; i <= n; i++) {
+    std::cin >> H[i];
+    H[i]++;
+  }
+
+  for (int i = 1; i <= n; i++) {
+    add(H[i], 1);
+    reverse_pairs[i] = i - query(H[i]);
+  }
+
+  std::memset(bit, 0, sizeof bit);
+
+  for (int i = n; i >= 1; i--) {
+    add(H[i], 1);
+    reverse_pairs[i] += query(H[i] - 1);
+  }
+
+  long long result = 0;
+
+  for (int i = 1; i <= n; i++) {
+    result += (1LL + reverse_pairs[i]) * reverse_pairs[i] / 2;
+  }
+
+  std::cout << result;
+
+  return 0;
+}
-- 
cgit v1.2.3