【luogu P6621】【LOJ 3301】魔法商店（线性基）（保序回归）

【luogu P6621】【LOJ 3301】魔法商店（线性基）（保序回归）

魔法商店

题目链接：luogu P6621 / LOJ 3301

题目大意

给你 n 个物品，每个有魅力值和价格。
然后一组合法的方案定义为数量最多的一个物品集，使得每个非空子集魅力值的异或和都非 0。
然后你可以修改物品的价格，费用是价格差的平方。
然后给你两个合法方案，要你用最小的费用使得它们在所有合法方案中一个价格和最大，一个最小。

思路

首先看到那个合法方案就是每个都能放进线性基里面。
那最大最小可以分开看看。

然后发现你枚举出所有合法方案不太行，考虑先是最小的怎么做。
那我们考虑能否把最小的集合变化一下得到别的。
那如果这个集合 A A A 里面一个子集的异或和是 k k k，那 k k k 其实是可以替代子集里的任意一个。

那集合 A A A 还是最小的，那我们就其实可以通过这个替代列出一些关系 v x ⩽ v y v_xleqslant v_y vx​⩽vy​。
对 A A A 来说，就是它自己里面的 v v v 要小于等于替换的 k k k 的 v v v 值。
至于 B B B，就是大于等于。
然后你会发现这个关系已经充要了。

那我们就可以考虑这些偏序关系怎么满足：
保序回归！

然后因为第一次做网络流的保序回归，就说说怎么做。
首先也是整体二分，然后每次有一个点集和一个答案的范围。
然后首先假设答案不要求整数，那它就是一个实数，你总不能递归下去，于是考虑这么一个方法：
m i d mid mid 和一个位置 m i d + x mid+x mid+x，如果我们让 x x x 很小很小，然后两个的费用都除 x x x，那你会发现首先谁优这个不变，第二它其实就相当于在 m i d mid mid 位置的导数！
那我们就可以把这个作为权值，至于为啥是网络流做，你会发现你因为限制条件，你一个点如果要选前面的那能到它的点都要选前面。

那它其实就是最大权闭合图的感觉，那就是网络流模板啦。
（具体一点你要最小的权值，然后你每个的权值就是左边的减右边的，然后搞最小割）

然后至于答案要是整数，那我们就不能完全用上面的方法搞，因为你 L + 1 = R L+1=R L+1=R 的时候你小的位置 L + x L+x L+x 不能代表 R R R，所以就直接两个用 L , R L,R L,R，然后就选 L , R L,R L,R 给它即可。

然后最后带进去求每个费用加起来即可。

代码

#include<queue>
#include<cstdio>
#include<vector>
#include<iostream>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3fusing namespace std;const int N = 1000 + 10;
const int M = 64; 
int n, m, v[N], a[M], b[M], ans[N];
bool in1[N], in2[N];
bool lnk[N][N];//[i][j] -> i<=j
ull c[N];
vector <int> d;struct XXJ {ull f[M], hav[M];void clear() {for (int i = 0; i < M; i++) f[i] = hav[i] = 0;}void insert(ull x, ull pl) {for (int i = M - 1; i >= 0; i--)if ((x >> i) & 1) {if (f[i]) x ^= f[i], pl ^= hav[i];else {f[i] = x; hav[i] = pl; break;}}}ull get_id(ull x) {ull id = 0;for (int i = M - 1; i >= 0; i--)if ((x >> i) & 1) x ^= f[i], id ^= hav[i];return id;}
}H;struct Map_Flow {struct node {ll x;int to, nxt, op;}e[N * N * 2];int le[N], KK, tot, S, T, deg[N], lee[N];queue <int> q;void Init(int siz) {tot = siz; S = ++tot; T = ++tot;for (int i = 1; i <= tot; i++) le[i] = 0; KK = 0;} void add(int x, int y, ll z) {e[++KK] = (node){z, y, le[x], KK + 1}; le[x] = KK;e[++KK] = (node){0, x, le[y], KK - 1}; le[y] = KK;}bool bfs() {while (!q.empty()) q.pop();for (int i = 1; i <= tot; i++) deg[i] = 0, lee[i] = le[i];q.push(S); deg[S] = 1;while (!q.empty()) {int now = q.front(); q.pop();for (int i = le[now]; i; i = e[i].nxt)if (e[i].x && !deg[e[i].to]) {deg[e[i].to] = deg[now] + 1;if (e[i].to == T) return 1;q.push(e[i].to);}}return 0;}ll dfs(int now, ll sum) {if (now == T) return sum;ll go = 0;for (int &i = lee[now]; i; i = e[i].nxt)if (e[i].x && deg[e[i].to] == deg[now] + 1) {ll this_go = dfs(e[i].to, min(sum - go, e[i].x));if (this_go) {e[i].x -= this_go; e[e[i].op].x += this_go;go += this_go; if (go == sum) return go;}}return go;}void dinic() {while (bfs())dfs(S, INF);}
}G;//(x^p)'=px^{p-1}
//(x^2)'=2x 
void slove(vector <int> d, int L, int R) {if (d.empty()) return ;if (L >= R) return ;int mid = (L + R) >> 1; G.Init(d.size()); for (int i = 0; i < d.size(); i++) {int x = d[i];ll va = (L + 1 == R) ? 1ll * (v[x] - R) * (v[x] - R) - 1ll * (v[x] - L) * (v[x] - L) : 2ll * (mid - v[x]);if (va < 0) G.add(G.S, i + 1, -va);else G.add(i + 1, G.T, va);}for (int i = 0; i < d.size(); i++)for (int j = 0; j < d.size(); j++)if (lnk[d[i]][d[j]]) G.add(i + 1, j + 1, INF);G.dinic();if (L + 1 == R) {for (int i = 0; i < d.size(); i++)if (G.deg[i + 1]) ans[d[i]] = R;else ans[d[i]] = L;return ;}vector <int> dl, dr;for (int i = 0; i < d.size(); i++)if (G.deg[i + 1]) dr.push_back(d[i]);else dl.push_back(d[i]);slove(dl, L, mid); slove(dr, mid, R);
}int main() {
//	freopen(&#", "r", stdin);scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++) scanf("%llu", &c[i]);for (int i = 1; i <= n; i++) scanf("%d", &v[i]);for (int i = 0; i < m; i++) scanf("%d", &a[i]), in1[a[i]] = 1;for (int i = 0; i < m; i++) scanf("%d", &b[i]), in2[b[i]] = 1;H.clear(); for (int i = 0; i < m; i++) H.insert(c[a[i]], 1ull << i);for (int i = 1; i <= n; i++) if (!in1[i]) {ull id = H.get_id(c[i]);for (int j = 0; j < m; j++) if ((id >> j) & 1) lnk[a[j]][i] = 1;}H.clear(); for (int i = 0; i < m; i++) H.insert(c[b[i]], 1ull << i);for (int i = 1; i <= n; i++) if (!in2[i]) {ull id = H.get_id(c[i]);for (int j = 0; j < m; j++) if ((id >> j) & 1) lnk[i][b[j]] = 1;}for (int i = 1; i <= n; i++) d.push_back(i);slove(d, 0, 1e6);ll answer = 0;for (int i = 1; i <= n; i++) answer += 1ll * (v[i] - ans[i]) * (v[i] - ans[i]);printf("%lld", answer);return 0;
}