CodeForces 61E Enemy is weak

十一月 03, 2020 2418

题意简述

给定一个序列 a ，求有序三元组 (i, j, k) 满足 i < j < k \text{ and } a_i > a_j > a_k 的个数。

解题思路

老套路了。

枚举中间点 j ，统计前面有多少个 a_i > a_j ，后面有多少个 a_k < a_j ，和求逆序对个数差不多，直接树状数组即可。

代码实现

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;
#define forall(G,u) for (int i_ = 0, __for_siz__ = (int) G[u].size(); i_ < __for_siz__; ++i_) 

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 1e6 + 10;

int n;

struct BIT {
    int ss[MAXN];
    #define lb(x) ((x) & (-(x)))
    void insert(int s, int x) { while (s <= n) ss[s] += x, s += lb(s); }
    int query(int s) {
        int ret = 0; while (s >= 1) ret += ss[s], s -= lb(s);
        return ret;
    }
} rev;

struct revBIT {
    int ss[MAXN];
    #define lb(x) ((x) & (-(x)))
    void insert(int s, int x) { while (s >= 1) ss[s] += x, s -= lb(s); }
    int query(int s) {
        int ret = 0; while (s <= n) ret += ss[s], s += lb(s);
        return ret;
    }
} pre;

int aa[MAXN], la[MAXN];
long long int ans = 0;

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) aa[i] = la[i] = read();
    std::sort(la + 1, la + n + 1);
    for (int i = 1; i <= n; ++i) aa[i] = std::lower_bound(la + 1, la + n + 1, aa[i]) - la;
    // for (int i = 1; i <= n; ++i) printf("%d%c", aa[i], " \n"[i == n]);
    pre.insert(aa[1], 1);
    for (int i = 3; i <= n; ++i) rev.insert(aa[i], 1);
    for (int j = 2; j <= n - 1; ++j) {
        // 枚举中间点
        int left = pre.query(aa[j]);
        int right = rev.query(aa[j]);
        ans += 1ll * left * right;
        pre.insert(aa[j], 1); rev.insert(aa[j + 1], -1);
    } printf("%lld\n", ans);
    return 0;
}