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 | 99e2e923d0c77b02f3fb4ff648ea916954868606 (patch) | |
| tree | ec8e03f6f2cd1ce43990fb4fe6cd631967d0237e /store/works/solutions/acwing/1215.cpp | |
| parent | 1cee979f5d36b311a03cc7397a036ba11caf3d42 (diff) | |
| download | crupest-99e2e923d0c77b02f3fb4ff648ea916954868606.tar.gz crupest-99e2e923d0c77b02f3fb4ff648ea916954868606.tar.bz2 crupest-99e2e923d0c77b02f3fb4ff648ea916954868606.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;
+}
|