diff options
| author | Yuqian Yang <crupest@crupest.life> | 2025-02-28 23:13:39 +0800 |
|---|---|---|
| committer | Yuqian Yang <crupest@crupest.life> | 2025-02-28 23:13:39 +0800 |
| commit | dc1f0c4c0096013799416664894c5194dc7e1f52 (patch) | |
| tree | 2f5d235f778cd720f4c39ec3e56b77ba6d99f375 /store/works/solutions/acwing/1215.cpp | |
| parent | 7299d424d90b1effb6db69e3476ddd5af72eeba4 (diff) | |
| download | crupest-dc1f0c4c0096013799416664894c5194dc7e1f52.tar.gz crupest-dc1f0c4c0096013799416664894c5194dc7e1f52.tar.bz2 crupest-dc1f0c4c0096013799416664894c5194dc7e1f52.zip | |
chore(store): move everything to store.
Diffstat (limited to 'store/works/solutions/acwing/1215.cpp')
| -rw-r--r-- | store/works/solutions/acwing/1215.cpp | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/store/works/solutions/acwing/1215.cpp b/store/works/solutions/acwing/1215.cpp new file mode 100644 index 0000000..d6832b3 --- /dev/null +++ b/store/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;
+}
|