CST PA2
2-1 Risk
算法构思
本题的思路是先求出由每一天回溯所得的最大单日确诊病例数, 然后使用前缀和算法处理得到的最大病例数数组, 最后对于每组给定的输入 p、q, 查询并输出相应的低、中风险天数.
使用数组 x[i] 储存每日的确诊人数, 数组 m[i] 储存对应的回溯天数. 实际上, 本题相当于用一个滑动窗口来扫描遍历 x[i] 数组, 并返回 x[i - m[i]] 到 x[i - 1] 这个窗口中的最大值.
注意到序列 x[i - m[i]] 是不减的, 那么窗口整体是向右移动的, 对于窗口内不同的两天 i < j, 若经过一系列移动后 i 在窗口内, 那么 j 必然也在窗口内. 此时如果 x[i] <= x[j], 那么 x[i] 将不会对窗口中的最大值做出贡献.
这也就是说, 随着窗口右移加入新的确诊病例数, 窗口内不大于该数的数字在之后都不会成为窗口中的最大值 (它至少不大于这个新加入的确诊病例数). 也就是说, 我们可以直接删去窗口中不大于新加入确诊病例数的所有数.
构造单调队列这一数据结构, 队列中元素从队首到队尾降序排列. 对于每一次窗口扫描, 我们将窗口最右端新加入的元素与队尾元素比较, 若队尾元素不大于新入队元素, 则删去队尾元素, 最后将新元素入队. 如此操作, 保证了队列元素的单调性. 同时使用 int 数组与两个 int 类型整数 header、trailer 记录队列的首尾位置, 模拟单调队列的功能. 对于队列中的每个元素, 我们在入队的同时记录它的确诊病例数和它在原数组中的天数.
// Line 8
class PriorityQueue {
public:
int header = 0; // 指向头部.
int trailer = -1; // 指向尾部.
long long pos[MAXLEN + 1]; // 记录队中病例数在原数组中对应的天数.
int val[MAXLEN + 1]; // 记录队中病例数的大小.
};考虑到窗口的左端实际上是单调不减的, 因此在队尾元素出队后, 它不可能再次入队. 只需要查询队首元素, 如果它对应的位置不位于滑动窗口中, 则删去该元素, 最后剩下的满足条件的队首元素即是窗口中对应的最大确诊病例数. 我们使用 cases[i] 数组存储第 i 天回溯对应的最大确诊病例数. 然后遍历 cases[i], 将为病例数大小 k 出现的天数记录在数组 sum[k] 中. 随后对 sum 数组从第二项开始求出前缀和, sum[k - 1] 即对应了 cases 数组中病例数位于 $[0, k)$ 范围内的天数. 如此操作, 我们在查询时只需访问数组 sum[i], 这实现了 $O(1)$ 的复杂度.
问题解决
注意到 p, q, m[i] 的范围均为 $[1, 2^{32} - 1]$, 超过了 int 的范围, 因此使用 long long 数组存储.
若 p = 0, 则需直接返回低风险天数为 0; 若输入的 p、q 过大, 由于 x[i] 的范围为 $[1, 2\times 10^6]$, 在查询时应直接返回全部的风险天数. 这在代码中体现为使用 flag 记录最大单日确诊病例数的上界, 当超过此上界时, 直接返回 sum[flag].
...
// Line 54
// 计算病例数位于 [0, p) 范围内的天数.
ans1 = (p > flag ? sum[flag] : sum[p - 1]);
if (p == 0)
ans1 = 0;
// 计算病例数位于 [0, q) 范围内的天数.
ans2 = (q > flag ? sum[flag] : sum[q - 1]);
cout << ans1 << ' ' << ans2 - ans1 << endl;
...复杂度估计
算法时间复杂度主要来自计算最大单日确诊病例、计算前缀和与查询风险天数等部分:
...
// Line 30
for(int i = 1; i <= n; i++) {
while(que.header <= que.trailer && que.val[que.trailer] <= x[i - 1])
que.trailer--;
que.trailer++;
que.val[que.trailer] = x[i - 1];
que.pos[que.trailer] = i - 1;
while(que.pos[que.header] < i - m[i])
que.header++;
cases[i] = que.val[que.header];
}
...在计算最大单日确诊病例时, 每个元素最多入队且出队一次, 从而时间复杂度与输入元素数成正比, 为 $O(n)$;
...
// Line 42
int flag = 0;
for(int i = 1; i <= n; i++) {
flag = max(cases[i], flag);
sum[cases[i]] += 1;
}
for(int i = 0; i < flag; i++) {
sum[i + 1] += sum[i];
}
...在进行前缀和计算时, 由于 flag = max(x[i]), 从而时间复杂度为 $O(n + max(x[i]))$;
...
// Line 52
for (int i = 0; i < t; i++) {
cin >> p >> q;
ans1 = (p > flag ? sum[flag] : sum[p - 1]);
if (p == 0)
ans1 = 0;
ans2 = (q > flag ? sum[flag] : sum[q - 1]);
cout << ans1 << ' ' << ans2 - ans1 << endl;
}
...在查询风险天数时, 每次查询用时常数时间, 从而时间复杂度与查询次数成正比, 为 $O(T)$;
综上, 算法总时间复杂度为 $O(n + max(x[i]) + T)$.
算法空间复杂度主要来自读取并存储数据的过程:
...
// Line 4
#define MAXLEN 1000000
...
// Line 8
class PriorityQueue {
public:
int header = 0;
int trailer = -1;
long long pos[MAXLEN + 1];
int val[MAXLEN + 1];
};
...
// Line 18
int x[MAXLEN + 1] = {0};
long long m[MAXLEN + 1] = {0};
int cases[MAXLEN + 1] = {0};
int sum[2 * MAXLEN + 1] = {0};
PriorityQueue que;
...代码开辟了定长的数组用于存储相关数据, 算法的空间复杂度约为: $8B\times 2\times 10^6 + 4B \times 5\times 10^6 = 36000KB$.
