P6294 题解
船酱魔王
·
·
题解
Changelog
- 更改了关于「顺推」的歧义表述。
- 更改了对于时间复杂度的错误判断。
题意回顾
两个人玩游戏，每次取出前缀内未被取走的最大的数并得到数值分数，然后前缀往后推一格，求出游戏后先手与后手的得分差。
$ 1 \le n \le 10^5 $，$ 1 \le k \le 2 \times 10^3 $。
## 分析
考虑改变暴力的写法，前缀 $ i $ 从前往后顺序枚举，考虑每个询问，若一个询问已经可以取数，那么就取第 $ i $ 个数与第 $ i-p_j+1 $ 大的数的较大值。
考虑一个证明：
* 设前 $ i $ 个数加入前缀后已经取完前 $ i $ 个数中的前 $ i-p_j+1 $ 大的数。
* 如果第 $ i+1 $ 个数加入后，作为第 $ i-p_j+2 $ 大乃至更大的数的话，那么显然这个数就是这组询问要取到的最大的数；若不是的话这组询问取到的数就是原来的第 $ i-p_j+2 $ 大的数，同时这个数比新加入的数更大因此它及之前的数排名不变。
* 无论如何，我们要取到的数都是前 $ i+1 $ 个数中的前 $ i-p_j+2 $ 大的数，故数学归纳法成立。
因此，我们只需要维护一个数据结构，支持：
* 插入一个数。
* 连续查询 $ k $ 次排名对应的数。
平衡树是 $ O(nk \log n) $ 的，考虑让操作二面对一个类似于线性表的结构，可以常数复杂度内查到一个数。
我们排序 $ p $ 数组，那么此时查询过程是从前往后查，单次查询 $ O(1) $ 的话考虑开线性表，但是有大量的插入操作因此考虑分块。
具体地，把要插入的数从大到小排序后每 $ S $ 个数分成一个部分，每次插入数后插入到对应的子表（实现中使用了暴力重排序但是理论上可以使用插入排序的思想优化排序效率，不过这里不是时间复杂度的瓶颈无需优化）中，查询从第一个子表往下双指针（两个指针为子表编号和询问编号），此时连续查询的总复杂度是 $ O(\frac{n}{S}+k) $ 的。
故本题本实现的总复杂度为 $ O(n(S \log n+\frac{n}{S}+k)) $，在 $ S $ 近似取 $ \sqrt{n} $ 时是 $ O(n^{1.5} \log n+nk) $，可以通过本题，实现中取 $ S=317 $。
## AC 代码
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
const int K = 2e3 + 5;
const int S = 317;
int n, k;
int a[N], p[K];
pair<int, int> aa[N];
int bid[N];
vector<int> vec[325];
int stp[K];
ll ans[N];
bool jsx(int x, int y) {
return x > y;
}
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]), aa[i].first = -a[i], aa[i].second = i;
sort(aa + 1, aa + n + 1);
for(int i = 1; i <= k; i++) scanf("%d", &p[i]), stp[i] = p[i];
sort(p + 1, p + k + 1, jsx);
for(int i = 1; i <= n; i++) bid[aa[i].second] = i / S;
int kk = k;
for(int i = 1; i <= n * 2; i++) {
int val = 0;
if(i <= n) {
vec[bid[i]].push_back(a[i]);
sort(vec[bid[i]].begin(), vec[bid[i]].end(), jsx);
val = a[i];
} else {
while(k >= 1 && i > n + p[k] - 1) k--;
}
int pre = 0;
int now = 1;
while(now <= k && i < p[now]) now++;
for(int j = 0; j <= n / S; j++) {
while(now <= k && pre + vec[j].size() >= i - p[now] + 1) {
ans[p[now]] += max(val, vec[j][i - p[now] - pre]) * (((i - p[now]) % 2 == 0) ? 1 : (-1));
//cout << max(val, vec[j][i - p[now] - pre]) << " IN " << p[now] << endl;
now++;
}
pre += vec[j].size();
}
}
for(int i = 1; i <= kk; i++) printf("%lld\n", ans[stp[i]]);
return 0;
}
```