T4
先把四组分成两组，左边两组叫 \(L\)，右边两组叫 \(R\)。直接爆搜每个数属于 \(L\) 还是 \(R\)，过程中顺带 \(01\) 背包出两组分别能取到哪些子集异或和。接下来不妨设 \(w_{f(A)} \ge w_{f(B)}\)，\(w_{f(C)} \ge w_{f(D)}\)。若 \(w_{f(A)} \ge w_{f(C)}\)，则答案为 \(w_{f(A)} - w_{f(D)}\)，否则答案为 \(w_{f(C)} - w_{f(B)}\)。按 \(w\) 升序枚举 \(f(A)\) 和 \(f(C)\)，则 \(f(B)\) 和 \(f(D)\) 只需要异或一下。枚举的时候把 \(f(A)\) 和 \(f(C)\) 一起枚举，顺便记录 \(f(B)\) 和 \(f(D)\) 的前缀最大值。
代码
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, S;
int a[20];
int w[2005];
int p[2005];
bool f[2][20][2005];
int ans = 0;
void dfs(int x, int sl, int sr) {
if (x == n + 1) {
for (int j = 0, ml = -1, mr = -1; j <= S; j++) {
int i = p[j];
if (f[0][x][i] && w[i] >= w[sl ^ i]) {
ml = max(ml, w[sl ^ i]);
if (mr != -1)
ans = min(ans, w[i] - min(w[sl ^ i], mr));
}
if (f[1][x][i] && w[i] >= w[sr ^ i]) {
mr = max(mr, w[sr ^ i]);
if (ml != -1)
ans = min(ans, w[i] - min(w[sr ^ i], ml));
}
}
return;
}
for (int i = 0; i <= S; i++) {
f[0][x + 1][i] = (f[0][x][i] | f[0][x][i ^ a[x]]);
f[1][x + 1][i] = f[1][x][i];
}
dfs(x + 1, sl ^ a[x], sr);
for (int i = 0; i <= S; i++) {
f[0][x + 1][i] = f[0][x][i];
f[1][x + 1][i] = f[1][x][i] | f[1][x][i ^ a[x]];
}
dfs(x + 1, sl, sr ^ a[x]);
}
int main() {
int tc;
cin >> tc;
while (tc--) {
ans = 2147483647;
cin >> n >> m;
S = (1 << m) - 1;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i <= S; i++) cin >> w[i], p[i] = i;
sort(p, p + S + 1, [](int a, int b) { return w[a] < w[b]; });
for (int i = 0; i <= S; i++) f[0][2][i] = f[1][2][i] = 0;
f[0][2][a[1]] = f[0][2][0] = f[1][2][0] = 1;
dfs(2, a[1], 0);
cout << ans << "\n";
}
return 0;
}
T12
按照平面直角坐标系第一象限建系。
先预处理出 \(pre[i]\) 表示从起点到达 \((i, p_i)\) 的最大收益，\(suf[i]\) 表示从终点到 \((i, p_i)\) 的最大收益。然后考虑对于一个询问，肯定是从起点到达其左上或右下的一个点，然后从这个点到终点。考虑左上，则右下同理。若区域内存在至少一个点，则这个区域的答案就是 \(\max\limits_{(i, p_i) 在区域内} \{ pre[i] + suf[i] \}\)。如果区域内不存在一个点，那就可以强制令路径经过这区域内的某个点。所以我们考虑对每个询问在左上右下各建一个虚点（建在整个地图的左上和右下应该也行），然后令这些虚点的权值为 \(0\)，正常求它们的 \(pre\) 和 \(suf\)，然后查询就可以变成二维数点。然后整个题就只需要一堆二维数点即可。
代码
#include <iostream>
#include <algorithm>
#include <math.h>
#define int long long
#define lowbit(x) ((x) & (-(x)))
using namespace std;
bool bg;
int n, m;
struct node {
int x, y, v;
} a[1200005], b[2000005];
int pre[1200005];
int suf[1200005];
struct PBIT {
int bit[900005];
void add(int x, int y) { for (; x <= n + 10; x += lowbit(x)) bit[x] = max(bit[x], y); }
int query(int x) {
int ret = 0;
for (; x; x -= lowbit(x)) ret = max(ret, bit[x]);
return ret;
}
void clear() { for (int i = 0; i <= n + 10; i++) bit[i] = 0; }
} pbit;
struct SBIT {
int bit[900005];
void add(int x, int y) { for (; x; x -= lowbit(x)) bit[x] = max(bit[x], y); }
int query(int x) {
// cerr << x << "qq\n";
int ret = 0;
for (; x <= n + 10; x += lowbit(x)) ret = max(ret, bit[x]);
return ret;
}
void clear() { for (int i = 0; i <= n + 10; i++) bit[i] = 0; }
} sbit;
int ans[400005];
bool ed;
signed main() {
// cout << (&ed - &bg) / 1024.0 / 1024.0 << "\n";
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tc;
cin >> tc;
while (tc--) {
cin >> n >> m;
for (int i = 1; i <= m; i++) ans[i] = 0;
for (int i = 1; i <= n; i++) {
a[i].x = i;
cin >> a[i].y >> a[i].v;
++a[i].x, ++a[i].y;
}
int bcnt = 0;
for (int i = 1; i <= m; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
swap(y1, y2);
++bcnt;
b[bcnt].x = x1, b[bcnt].y = y1;
++b[bcnt].x, ++b[bcnt].y;
a[++n] = (node) { b[bcnt].x - 1, b[bcnt].y + 1, 0 };
--b[bcnt].x, ++b[bcnt].y;
b[bcnt].v = i;
++bcnt;
b[bcnt].x = x2, b[bcnt].y = y2;
++b[bcnt].x, ++b[bcnt].y;
a[++n] = (node) { b[bcnt].x + 1, b[bcnt].y - 1, 0 };
++b[bcnt].x, --b[bcnt].y;
b[bcnt].v = -i;
}
sort(a + 1, a + n + 1, [](node a, node b) { return (a.x == b.x) ? (a.y < b.y) : (a.x < b.x); });
for (int i = 1; i <= n; i++) {
pre[i] = pbit.query(a[i].y) + a[i].v;
pbit.add(a[i].y, pre[i]);
}
for (int i = n; i; i--) {
suf[i] = sbit.query(a[i].y) + a[i].v;
sbit.add(a[i].y, suf[i]);
suf[i] -= a[i].v;
}
pbit.clear(), sbit.clear();
for (int i = 1; i <= n; i++) b[++bcnt] = a[i], b[bcnt].v = n + i;
sort(b + 1, b + bcnt + 1, [](node a, node b) { return a.x == b.x ? (a.v > b.v) : (a.x < b.x); });
for (int i = 1; i <= bcnt; i++) {
if (b[i].v > n)
sbit.add(b[i].y, pre[b[i].v - n] + suf[b[i].v - n]);
else if (b[i].v > 0)
ans[b[i].v] = max(ans[b[i].v], sbit.query(b[i].y));
}
sort(b + 1, b + bcnt + 1, [](node a, node b) { return a.x == b.x ? (a.v > b.v) : (a.x > b.x); });
for (int i = 1; i <= bcnt; i++) {
if (b[i].v > n)
pbit.add(b[i].y, pre[b[i].v - n] + suf[b[i].v - n]);
else if (b[i].v < 0)
ans[-b[i].v] = max(ans[-b[i].v], pbit.query(b[i].y));
}
for (int i = 1; i <= m; i++) cout << ans[i] << "\n";
pbit.clear(), sbit.clear();
}
return 0;
}