A.自动收小麦机
预处理在每一格倒水时水能流过的最短距离，查询时输出前缀和即可。
标程
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 5, M = 1e5 + 5, INF = 0x3f3f3f3f;
int n, q, k;
ll h[N], sum[N]; // 麦田的高度和麦田小麦的前缀和
int tj[N], st[N]; // 前一个台阶的距离和最远流到的位置
int main() {
cin >> n >> q >> k;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
// 求前缀和
sum[i] = sum[i - 1] + x;
}
h[0] = -1;
tj[1] = 1;
int idx = 0; // 记录距前一个台阶的距离
for (int i = 1; i <= n; i++) {
cin >> h[i];
if (h[i] != h[i - 1]) tj[i] = idx = 1;
else tj[i] = idx;
idx++;
if (tj[i] < k) st[i] = st[i - 1]; // 能够流入下一个台阶
else st[i] = i - k + 1; // 无法流入下一个台阶
}
while (q--) {
int x;
cin >> x;
cout << sum[x] - sum[st[x] - 1] << endl;
}
return 0;
}
B.异星突击
由题可知，我们需要一种数据结构，可以快速的查询所有数中异或某个数x后大于h的数的数量。
对于异或值的查询可以想到用trie来解决，记录一下每个节点下的数字数量。每次查询时 从高位向低位贪心查询，当h当前位为1时，我们只能选择和x异或值为1的位置继续向下搜索，当当前位h为0时所有与x异或值为1的数字都符和条件，然后继续搜索当前位不符合条件但以后可能符和条件的数，即可保证所有选择的数都大于h。
标程
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 5, M = 1e5 * 32 + 5, INF = 0x3f3f3f3f;
int n, hp, idx = 1;
int cnt[M], tr[M][2]; // 计数每个节点的数字数量 和子节点编号
// 插入
void insert(int x, int num) {
int p = 1; // 从根节点开始
for (int i = 30; i >= 0; i--) {
int d = (x >> i) & 1;
if (!tr[p][d]) tr[p][d] = ++idx;
p = tr[p][d];
cnt[p] += num; // 当前节点上的数字数量+1
}
}
int find(int x, int h) {
int p = 1, res = 0; // 从根节点开始搜索
for (int i = 30; i >= 0; i--) {
int d = (x >> i) & 1; // x这一位的值
int dh = (h >> i) & 1; // h这一位的值
if (!dh) { // h当前位为0,则选择异或后值为1的所有数都能使结果大于h
res += cnt[tr[p][d ^ 1]]; // 异或后值为1的所有数数量
p = tr[p][d]; // 继续查找当前位异或后为0的数
} else { // h当前位为1,想要异或后大于h只能选择查找当前值异或后值为1的数
p = tr[p][d ^ 1];
}
}
return res; // 返回结果
}
int main ()
{
// 输入输出
cin >> n >> hp;
for (int i = 0; i < n; i++) {
int op, x, h;
cin >> op;
if (op == 0) {
cin >> x;