# C

# 题目大意

如果一个数 $n$，能够找到唯一一对 $x, y~(0 < x < y)$，满足 $x^2+y^2=n$ 的话，那么就称 $n$ 为好数

现在，给你 $n$，请问，$1 \to n$ 有多少好数？请你输出他们

# 数据范围

• $1 \le n \le 10^7$

# 题解

这题实际上考的是预处理，我们只需要定义一个 cnt ，然后预处理出所有数可能出现的次数即可了，复杂度是 $O( {\sqrt{N}}^2)$，可以接受

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

from math import sqrt

N = 10 ** 7 + 10

cnt = [0 for _ in range(N)]

for i in range(1, int(sqrt(N))):
    j = i + 1
    k = i * i
    num = k + j * j
    
    while num <= N - 10:
        cnt[num] += 1
        j += 1
        num = k + j * j

n = int(input())

res = []
for i in range(n + 1):
    if cnt[i] == 1:
        res.append(i)

print(len(res))
for i in res:   print(i, end = ' ')

# D

# 题目大意

给定 $n$ 个数，$a_1, \ldots, a_n$，请问，满足以下条件的三元组 $(i, j, k)$ 有几个？

• $1 \le i, j, k \le n$
• $a_i : a_j : a_k = 7 : 5 : 3$
• $\min(i, j, k) = j \quad or \quad \max(i, j, k) = j$

# 数据范围

• $1 \le n \le 3 \times 10^5$
• $1 \le a_i \le 10^9$

# 题解

显然，根据 $\min(i, j, k) = j \quad or \quad \max(i, j, k) = j$ 这个条件，我们可以得知，当确定了 $j$ 的位置时，$i, k$ 要么都在 $j$ 的左边，要么都在 $j$ 的右边，由此可以衍生出做法

我们用 map 记录左右两边的数出现的个数，然后扫描 $j: 1 \to n$，如果 $a_j$ 是 $5$ 的倍数，那么代表其可以当做中间的那个，我们只需要计算

$$cnt_{l3} \times cnt_{l7} + cnt_{r3} \times cnt_{r7}$$

累加即可，其中， l3 = r3 = 3 * (a[j] / 5), l7 = r7 = 7 * (a[j] / 5)

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

l = dict()
r = dict()

n = int(input())
a = [0] + list(map(int, input().split()))

for i in range(1, n + 1):
    r[a[i]] = r.get(a[i], 0) + 1

res = 0

for i in range(1, n + 1):
    r[a[i]] -= 1

    if a[i] % 5 == 0:
        t = a[i] // 5
        num7, num3 = t * 7, t * 3

        cntL7 = l.get(num7, 0)
        cntL3 = l.get(num3, 0)
        cntR7 = r.get(num7, 0)
        cntR3 = r.get(num3, 0)

        # <-- 这里用乘法，和 C++ 一致
        res += cntL7 * cntL3 + cntR7 * cntR3

    l[a[i]] = l.get(a[i], 0) + 1

print(res)

# E

# 题目大意

$n$ 个人想放风筝，第 $i$ 个人站在 $(a_i, 0)$，想把风筝放到 $(b_i, 1)$
问这 $n$ 个人，如果要求线不能交叉，能满足最多人放风筝的数量是多少？

# 数据范围

• $1 \le n \le 2 \times 10^5$
• $0 \le a_i, b_i \le 10^9$

# 题解

# 一些知识

为了写这道题，我们先介绍下最长上升子序列（$LIS$）和最长连续上升子序列（$LCIS$）

最长上升子序列：首先是 $O(n^2)$ 的做法，定义 dp[i] 为以 $i$ 结尾的最长上升子序列的长度，很容易可以得到状态转移方程

$$dp_i = \max_{j \in t, a[\forall t] < a[i]} dp_j + 1$$

这样的是 $O(n^2)$ 的，那有没有 $O(n \log n)$ 的做法呢？有的兄弟有的
我们可以额外维护一个 $d$ 数组，$d_i$ 表示，长度为 $i$ 的最长上升子序列的末尾元素的最小值
显然，$d_i$ 是单调递增的，于是我们便可以用二分去找到位置

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

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size(), res = 1;

        vector<int> d(n + 1, INT_MAX);   // d[i] 表示，长度为 i 的最长上升子序列，末尾的最小值
        d[0] = -INT_MAX, d[1] = nums[0];

        for (int i = 1; i < n; i++) {
            int l = 0, r = i;

            while (l < r) {
                int mid = (l + r + 1) >> 1;

                if (d[mid] >= nums[i]) r = mid - 1;
                else l = mid;     
            }

            res = max(res, l + 1);
            d[l + 1] = min(d[l + 1], nums[i]);
        }

        return res;
    }
};

最长连续上升子序列：这个很简单了，就是扫一遍 $O(n)$ 解决

# 最终解答

其实这题就是，先按 $a$ 升序排，然后按 $b$ 降序排，排完后做一个 $LIS$ 就结束了
为什么按 $B$ 降序排？
这是因为，如果按 $B$ 升序排，那同一个起点，比如 $(1, 2), (1, 3), (1, 4)$ 就会被算入 $3$，但实际上只算 $1$

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

class PII:
    def __init__(self, a, b):
        self.a = a
        self.b = b

n = int(input())
seg = [PII(0, 0) for _ in range(n + 1)]

for i in range(1, n + 1):
    a, b = list(map(int, input().split()))
    seg[i] = PII(a, b)

seg[1 : n + 1] = sorted(seg[1 : n + 1], key = lambda x : (x.a, -x.b))
d = [10 ** 9 + 10 for _ in range(n + 1)]
d[1] = seg[1].b
d[0] = -1000000
res = 1

for i in range(2, n + 1):
    l = 0
    r = i - 1

    while l < r:
        mid = (l + r + 1) // 2

        if d[mid] >= seg[i].b:  r = mid - 1
        else:   l = mid
    
    res = max(res, l + 1)
    d[l + 1] = min(d[l + 1], seg[i].b)

print(res)

# F

# 题目大意

门松形序列：当且仅当一个序列 $(a_1, \ldots, a_n)$ 满足峰数 > 谷数

现在给你一个 $(1, 2, \ldots, N)$ 的排列 $P$，请问，$P$ 中子序列是门松形序列的个数？（不一定要求子序列连续）

# 数据范围

• $1 \le n \le 3 \times 10^5$

# 题解

假设峰数量是 $x$，谷数量是 $y$
显然，对于任意一个序列，x-y \in \

一个超妙结论：只要子序列中存在 $i < j \le k < l$，并且 $a_i < a_j, \quad a_k > a_l$，换句话说，如果序列两头是两个峰，即是满足题目要求的子序列

我们维护好两个数组

1. bf[i] ：在 $i$ 前比 $a_i$ 小的数的个数
2. bh[i] ：在 $i$ 后比 $a_i$ 小的数的个数

然后我们就可以计算了，对于 $i < j = k < l$ 的情况，枚举 $j(k)$ 即可，答案就是 bf[j] * bh[j]

接着考虑 $i < j < k < l$ 的情况
我们枚举 $k$，那么 $l$ 的数量是 bh[k] ，然后我们可以在 $j = 1 \to j = k - 1$ 中枚举 $j$，那么 $i$ 的个数是 bf[j] ，$j + 1 \to k - 1$ 这一段的数字可以随便取，一共 $k-j-1$ 个，答案还要乘上 $2^{k - j - 1}$，也就是最终答案是

$$\sum\limits_{k=1}^{n} bh_{k} \times (\sum\limits_{j = 1}^{k - 1} bf_j \times 2^{k-j-1})$$

但这样枚举的写法是 $O(n^2)$ 的，对式子进行变形

$$\sum\limits_{k=1}^{n} bh_{k} \times (\sum\limits_{j = 1}^{k - 1} bf_j \times 2^{-j}) \times 2^{k-1}$$

可以发现，中间含 $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
66
67
68
69
70
71
72
73
74
75
76
77
78
79

int n;
vector<int> p, bf, bh;
vector<int> pw, ipw;

struct Tree {
    vector<int> a;
    int n;

    Tree(int nn) {
        a = vector<int>(nn + 1);
        n = nn;
    }

    int lowbit(int x) {
        return x & -x;
    }

    void add(int p, int x) {
        while (p <= n) a[p] += x, p += lowbit(p);
    }

    int sum(int p) {
        int res = 0;
        while (p) res += a[p], p -= lowbit(p);
        return res;
    }
};

int qmi(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void solve() {
    cin >> n;

    p = vector<int>(n + 1);
    bf = vector<int>(n + 1), bh = vector<int>(n + 1);
    pw = vector<int>(n + 1), ipw = vector<int>(n + 1);

    Tree bef(n), beh(n);

    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        bf[i] = bef.sum(p[i] - 1);
        bef.add(p[i], 1);
    }

    for (int i = n; i >= 1; i--) {
        bh[i] = beh.sum(p[i] - 1);
        beh.add(p[i], 1);
    }

    pw[0] = 1;
    for (int i = 1; i <= n; i++)
        pw[i] = pw[i - 1] * 2 % MOD;

    for (int i = 0; i <= n; i++)
        ipw[i] = qmi(pw[i], MOD - 2);

    int res = 0;

    for (int i = 1; i <= n; i++)
        res = (res + bf[i] * bh[i]) % MOD;

    int pre = 0;

    for (int i = 2; i < n; i++) {
        res = (res + bh[i] * pre % MOD * pw[i - 1]) % MOD;
        pre = (pre + bf[i] * ipw[i]) % MOD;
    }

    cout << res << '\n';
}