# # Leetcode 第233场周赛题解

## # Problem A - 最大升序子数组和 (opens new window)

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(1)$

class Solution:
def maxAscendingSum(self, nums: List[int]) -> int:
ans = 0
n = len(nums)
p = 0
while p < n:
last = 0
s = 0
q = p
while q < n and nums[q] > last:
s += nums[q]
last = nums[q]
q += 1
p = q
ans = max(ans, s)
return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

## # Problem B - 积压订单中的订单总数 (opens new window)

• 时间复杂度$\mathcal{O}(N\log N)$
• 空间复杂度$\mathcal{O}(N)$

typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
priority_queue<pair<int, ll>, vector<pair<int, ll>>, greater<>> sell;
for (auto &order : orders) {
int price = order[0];
ll amount = order[1];
int t = order[2];
if (t == 0) { // Buy
while (amount > 0 && !sell.empty() && sell.top().first <= price) {
ll lo = min(amount, sell.top().second);
amount -= lo;
ll rem = sell.top().second - lo;
int p = sell.top().first;
sell.pop();
if (rem) {
sell.emplace(p, rem);
}
}
if (amount)
} else { // Sell
amount -= lo;
ll rem = buy.top().second - lo;
if (rem) {
}
}
if (amount)
sell.emplace(price, amount);
}
}
ll ans = 0;
}
while (!sell.empty()) {
ans += sell.top().second;
sell.pop();
}
return ans % MOD;
}
};

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

## # Problem C - 有界数组中指定下标处的最大值 (opens new window)

• 时间复杂度$\mathcal{O}(\log M)$。其中$M$为最大总和。
• 空间复杂度$\mathcal{O}(1)$

typedef long long ll;

ll calc_min(ll len, ll hi) {
if (len >= hi)
return hi * (hi + 1) / 2 + (len - hi);
return (hi + hi - len + 1) * len / 2;
}

class Solution {
public:
int maxValue(int n, int index, int maxSum) {
int left = index, right = n - index - 1;
int lo = 1, hi = maxSum - (n - 1);
while (lo <= hi) {
int mid = (lo + hi) >> 1;
ll lmin = calc_min(left, mid - 1);
ll rmin = calc_min(right, mid - 1);
if (lmin + rmin + mid > maxSum)
hi = mid - 1;
else
lo = mid + 1;
}
return hi;
}
};

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

## # Problem D - 统计异或值在范围内的数对有多少 (opens new window)

1. 构造字典树。注意要在每个节点处记录当前节点为根节点的子树中包含数组元素的总个数。
2. 遍历数组中的元素。对于每一个元素，在字典树中从最高位开始进行一次DFS（具体实现可参考代码）。
• 如果走使得当前位异或值为$1$的分支，则要求之后最小值小于等于$H$
• 如果走使得当前为异或值为$0$的分支，且之后的最大值也小于等于$H$，则可以不进行DFS，直接利用节点上的计数。

struct TrieNode {
int val, cnt = 0;
TrieNode *son[2]{};
};

class Solution {
vector<int> nums;
TrieNode *root;

int dfs(TrieNode *p, int now, int num, int k, int hi) {
int flag = (num & (1 << k)) ? 1 : 0;
int ans = 0;
if (p->son[flag]) {
if ((now ^ (1 << k)) - 1 <= hi) {
ans += p->son[flag]->cnt;
} else {
ans += dfs(p->son[flag], now, num, k - 1, hi);
}
}
if ((now ^ (1 << k)) <= hi) {
if (p->son[1 - flag])
ans += dfs(p->son[1 - flag], now ^ (1 << k), num, k - 1, hi);
}
return ans;
}

int count(int hi) {
int ans = 0;
TrieNode *p = root;
for (int num : nums) {
ans += dfs(p, 0, num, 15, hi);
}
return ans;
}
public:
int countPairs(vector<int>& nums, int low, int high) {
this->nums = nums;
root = new TrieNode();

for (int num : nums) {
TrieNode *p = root;
for (int k = 15; k >= 0; --k) {
int flag = (num & (1 << k)) ? 1 : 0;
if (!p->son[flag]) {
p->son[flag] = new TrieNode();
}
p = p->son[flag];
p->cnt++;
}
}

return (count(high) - count(low - 1)) / 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
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