CF 杂题
定义函数 \(f(x)=\sum_{i=0}^{k-1}c_i\bigl([2^i]x\big)\)，其中 \(0\le x\le 2^k-1\)。你需要构造一个长度为 \(n\) 的序列 \(a_{1\sim n}\)，满足 \(\forall i\in[1,n],~l_i\le a_i\le r_i\)（\(l,r\) 是给定的序列），同时 \(\sum_{i=1}^{n-1}f(a_i\oplus a_{i+1})\) 最小。输出最小值。
\(n\le 50,~k\le 50\)
对于一个 \(a_i\in [l_i,r_i]\)，在高位 \(l_i\) 和 \(r_i\) 的 \(\operatorname{LCP}\) 部分，它每一位的取值都是固定的；直到某一位 \([2^x]l_i<[2^x]r_i\)，此时 \(a_i\) 可以选择跟随下界 \(l_i\) 或者上界 \(r_i\)；再直到某一位 \([2^x]l_i=0\) 或者 \([2^x]r_i=1\)，\(a_i\) 在这一位可以解除最后的限制，后面的位就可以任意取了。
因此每个 \(a_i\) 形如跟随 \(l_i\) 或 \(r_i\) 高位的一段前缀，然后某一位脱离了限制，后面任取。其中脱离限制的那一位不能违反另一个界的限制。考察任取的位会对答案造成什么样的影响，假设当前位置左右两个元素的这一位都是固定的，那么发现我们无论填 0/1，贡献只和 \([2^x](a_{i-1}\oplus a_{i+1})\) 有关：当相邻两个元素这一位不同时，产生 \(c_x\) 的代价，否则没有代价。进一步的，不难推广到数组上连续的一段 \([l,r]\) 都有同一位任取的情况：只要 \(i\) 和 \(i-1\) 填的 0/1 一样，就相当于 \(a_{l-1}\) 和 \(a_{r+1}\) 相邻时产生的代价。
高位
*---*---*---*---*---*---*---*
*---*---*---*---*---^---*---*
*---*---^---*---*-------^---*
*---^-------*---*-----------^
*-----------*---^
*-----------^
^
低位
^ 表示解除限制的那一位，横线表示代价源于横线连接的两个 bit 的异或。
因此计算过程中，一个固定位较长的元素会把另一侧固定位较短的元素“挡住”；两个固定位较长的元素就会把中间固定位较短的元素“挡住”。由于是最优化问题，因此考虑区间 dp，钦定两侧的元素挡住了中间的元素。如果直接钦定区间两端点分别解除限制的位数，状态数会爆炸，因此一位一位考虑。设 \(f_{x,i,j,0/1,0/1}\) 表示考虑了高于或等于 \(x\) 的位，\(i-1\) 和 \(j+1\) 还没有解除限制，\([i,j]\) 之间元素的元素都已经解除限制（刚刚解除也算），内部的代价最小是多少。
考虑转移，分讨 \([i,j]\) 中是否存在第 \(x\) 位解除限制的元素，若没有，则直接从 \(f_{x+1}\) 转移；否则将区间划分为若干段，段的边界处在第 \(x\) 位解除限制，段内在更高位解除限制。这可以用另一个数组 \(g\) 辅助转移。答案就是 \(\sum_x f_{x,0,n+1}\)，转移的时候 \(0\) 和 \(n+1\) 的贡献要特判一下。
代码
| #include<iostream>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int N = 55;
const int INF = 0x003f3f3f3f3f3f3f;
int n, k;
int l[N], r[N], lcp[N], c[N];
int f[N][N][N][2][2];
int g[N][N][N][2][2];
inline void ckmin(int &a, int b) { a = min(a, b); }
inline int calc(int x, int i, int j, int p, int q) {
if(!i || j == n + 1) return 0;
int a, b;
if(p == 0) a = (l[i] >> x) & 1;
else a = (r[i] >> x) & 1;
if(q == 0) b = (l[j] >> x) & 1;
else b = (r[j] >> x) & 1;
return c[x] * (a != b);
}
inline int calc1(int x, int i, int j, int p, int q) {
if(!i || j == n + 1) return 0;
int a, b;
if(p == 0) a = (l[i] >> x) & 1;
else a = (r[i] >> x) & 1;
if(q == 0) {
b = (l[j] >> x) & 1;
if(b == 1 || x >= lcp[j]) return INF;
b = 1;
} else {
b = (r[j] >> x) & 1;
if(b == 0 || x >= lcp[j]) return INF;
b = 0;
}
return c[x] * (a != b);
}
inline int calc2(int x, int i, int j, int p, int q) {
if(!i || j == n + 1) return 0;
int a, b;
if(p == 0) {
a = (l[i] >> x) & 1;
if(a == 1 || x >= lcp[i]) return INF;
a = 1;
} else {
a = (r[i] >> x) & 1;
if(a == 0 || x >= lcp[i]) return INF;
a = 0;
}
if(q == 0) b = (l[j] >> x) & 1;
else b = (r[j] >> x) & 1;
return c[x] * (a != b);
}
inline int calc3(int x, int i, int j, int p, int q) {
if(!i || j == n + 1) return 0;
int a, b;
if(p == 0) {
a = (l[i] >> x) & 1;
if(a == 1 || x >= lcp[i]) return INF;
a = 1;
} else {
a = (r[i] >> x) & 1;
if(a == 0 || x >= lcp[i]) return INF;
a = 0;
}
if(q == 0) {
b = (l[j] >> x) & 1;
if(b == 1 || x >= lcp[j]) return INF;
b = 1;
} else {
b = (r[j] >> x) & 1;
if(b == 0 || x >= lcp[j]) return INF;
b = 0;
}
return c[x] * (a != b);
}
signed main() {
cin >> n >> k; k += 2;
for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];
for(int i = 2; i < k; i++) cin >> c[i];
for(int i = 1; i <= n; i++) l[i] = l[i] * 4, r[i] = r[i] * 4 + 3;
for(int i = 1; i <= n; i++) lcp[i] = __lg(l[i] ^ r[i]);
memset(f, 0x3f, sizeof(f));
memset(g, 0x3f, sizeof(g));
for(int i = 0; i <= n; i++) {
f[k][i][i + 1][0][0] = 0;
f[k][i][i + 1][0][1] = 0;
f[k][i][i + 1][1][0] = 0;
f[k][i][i + 1][1][1] = 0;
g[k][i][i + 1][0][0] = 0;
g[k][i][i + 1][0][1] = 0;
g[k][i][i + 1][1][0] = 0;
g[k][i][i + 1][1][1] = 0;
}
for(int x = k - 1; x >= 0; x--) {
for(int len = 2; len <= n + 2; len++) {
for(int i = 0; i + len - 1 <= n + 1; i++) {
int j = i + len - 1;
f[x][i][j][0][0] = f[x + 1][i][j][0][0] + calc(x, i, j, 0, 0);
f[x][i][j][0][1] = f[x + 1][i][j][0][1] + calc(x, i, j, 0, 1);
f[x][i][j][1][0] = f[x + 1][i][j][1][0] + calc(x, i, j, 1, 0);
f[x][i][j][1][1] = f[x + 1][i][j][1][1] + calc(x, i, j, 1, 1);
g[x][i][j][0][0] = f[x + 1][i][j][0][0] + calc1(x, i, j, 0, 0);
g[x][i][j][0][1] = f[x + 1][i][j][0][1] + calc1(x, i, j, 0, 1);
g[x][i][j][1][0] = f[x + 1][i][j][1][0] + calc1(x, i, j, 1, 0);
g[x][i][j][1][1] = f[x + 1][i][j][1][1] + calc1(x, i, j, 1, 1);
for(int t = i + 1; t <= j - 1; t++) {
ckmin(f[x][i][j][0][0], g[x][i][t][0][0] + f[x + 1][t][j][0][0] + calc2(x, t, j, 0, 0));
ckmin(f[x][i][j][0][0], g[x][i][t][0][1] + f[x + 1][t][j][1][0] + calc2(x, t, j, 1, 0));
ckmin(f[x][i][j][0][1], g[x][i][t][0][0] + f[x + 1][t][j][0][1] + calc2(x, t, j, 0, 1));
ckmin(f[x][i][j][0][1], g[x][i][t][0][1] + f[x + 1][t][j][1][1] + calc2(x, t, j, 1, 1));
ckmin(f[x][i][j][1][0], g[x][i][t][1][0] + f[x + 1][t][j][0][0] + calc2(x, t, j, 0, 0));
ckmin(f[x][i][j][1][0], g[x][i][t][1][1] + f[x + 1][t][j][1][0] + calc2(x, t, j, 1, 0));
ckmin(f[x][i][j][1][1], g[x][i][t][1][0] + f[x + 1][t][j][0][1] + calc2(x, t, j, 0, 1));
ckmin(f[x][i][j][1][1], g[x][i][t][1][1] + f[x + 1][t][j][1][1] + calc2(x, t, j, 1, 1));
ckmin(g[x][i][j][0][0], g[x][i][t][0][0] + f[x + 1][t][j][0][0] + calc3(x, t, j, 0, 0));
ckmin(g[x][i][j][0][0], g[x][i][t][0][1] + f[x + 1][t][j][1][0] + calc3(x, t, j, 1, 0));
ckmin(g[x][i][j][0][1], g[x][i][t][0][0] + f[x + 1][t][j][0][1] + calc3(x, t, j, 0, 1));
ckmin(g[x][i][j][0][1], g[x][i][t][0][1] + f[x + 1][t][j][1][1] + calc3(x, t, j, 1, 1));
ckmin(g[x][i][j][1][0], g[x][i][t][1][0] + f[x + 1][t][j][0][0] + calc3(x, t, j, 0, 0));
ckmin(g[x][i][j][1][0], g[x][i][t][1][1] + f[x + 1][t][j][1][0] + calc3(x, t, j, 1, 0));
ckmin(g[x][i][j][1][1], g[x][i][t][1][0] + f[x + 1][t][j][0][1] + calc3(x, t, j, 0, 1));
ckmin(g[x][i][j][1][1], g[x][i][t][1][1] + f[x + 1][t][j][1][1] + calc3(x, t, j, 1, 1));
}
}
}
}
int ans = INF;
for(int x = k - 1; x >= 0; x--) {
ans = min(ans, f[x][0][n + 1][0][0]);
}
cout << ans << '\n';
return 0;
}
|
给定一棵大小为 \(n\) 的无根树，你需要构造一个长度为 \(n\) 的 \(1\sim n\) 的排列 \(p\)，使 \(\sum_{i=1}^{n}dis(i,p_i)\) 最大。并给出字典序最小的构造方案。
\(n\le 10^5\)
首先我们任意钦定一个根节点 \(rt\)，记节点 \(i\) 到根的距离为 \(d(i)\)，那么上式可以表示为 \(\sum_{i=1}^{n}2d(i)-\sum_{i=1}^{n}d(\operatorname{lca}(i,p_i))\)。并且不难说明这个式子的最小值不随根节点而改变。在固定一个根节点之后，式子的第一项不变，第二项有最大值 \(0\)，由此推出答案不能超过 \(\sum_{i=1}^{n}2d(i)\) 的最小值。
\(\sum_{i=1}^{n}2d(i)\) 在 \(rt\) 是重心时取最小值，此时尝试将第二项构造为 \(0\)。问题转化为：给定若干组元素，你需要将元素配对，使得每一对的两个元素都不在同一组中（配对是单向的）。
结论：上面这个问题，在每组元素数量不存在绝对众数时有解；
如果存在绝对众数，那么显然无解。否则，找到最大的两个组，各取一个元素进行匹配（双向匹配），仍然满足条件。发现当 \(rt\) 是重心时，各子树大小显然都不超过 \(\lceil\frac{n}{2}\rceil\)，因此不存在绝对众数，因而一定有解，答案可以取到上界 \(\sum_{i=1}^{n}d(i)\)。
那么如何构造使得字典序最小呢？考虑贪心处理，问题转化为判定一次单向匹配之后是否仍然有解。而这里产生的子问题是上面问题的强化版，可以刻画为一个二分图匹配问题：左部点和右部点各分为 \(k\) 组，当两个点 \(i,j\) 所在组的编号不同时，二者之间连一条边。那么根据霍尔定理，局面有解当且仅当对任意 \(i\in[1,k]\)，左右两边的第 \(i\) 组大小之和不超过节点数 \(n\)（二分图点数的一半）。
因此每次匹配先检查是否有一组节点数之和超过了 \(n\)，若是则强制匹配到这一组；否则找到全局最小值进行匹配。这里可以用堆维护全局抠掉一个点之后的答案。注意 \(rt\) 可以和自己进行匹配，这里注意特判。
代码
| #include<iostream>
#include<queue>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
struct Edge {
int v, w, next;
} pool[2 * N];
int ne, head[N];
void addEdge(int u, int v, int w) {
pool[++ne] = {v, w, head[u]};
head[u] = ne;
}
int n, rt;
int dfn[N], id[N], dt;
int mxp[N], szt[N], anc[N];
int son[N], nn;
ll d[N], sum;
void dfs1(int u, int fa) {
szt[u] = 1;
dfn[u] = ++dt;
id[dt] = u;
for(int e = head[u]; e; e = pool[e].next) {
int v = pool[e].v;
if(v == fa) continue;
dfs1(v, u);
szt[u] += szt[v];
mxp[u] = max(mxp[u], szt[v]);
}
mxp[u] = max(mxp[u], n - szt[u]);
if(mxp[u] < mxp[rt]) rt = u;
}
void dfs2(int u, int fa) {
for(int e = head[u]; e; e = pool[e].next) {
int v = pool[e].v, w = pool[e].w;
if(v == fa) continue;
d[v] = d[u] + w;
if(!anc[u]) { son[++nn] = v; anc[v] = nn; }
else anc[v] = anc[u];
dfs2(v, u);
}
}
template<typename _Tp>
struct myHeap {
priority_queue<_Tp, vector<_Tp>, greater<_Tp> > que, del;
inline void push(_Tp x) { que.push(x); }
inline void erase(_Tp x) { del.push(x); }
inline _Tp top() {
while(!del.empty() && que.top() == del.top()) { que.pop(), del.pop(); }
return que.top();
}
inline bool empty() { return que.size() == del.size(); }
inline _Tp top(int eid) {
if(eid == nn || top().id != eid) return top();
_Tp tmp = top();
que.pop();
_Tp res = top();
que.push(tmp);
return res;
}
};
struct Node1 {
int id, mn;
inline bool operator>(const Node1 &b) const { if(mn != b.mn) return mn > b.mn; return id > b.id; }
inline bool operator==(const Node1 &b) const { return mn == b.mn && id == b.id; }
};
struct Node2 {
int id, sz;
inline bool operator>(const Node2 &b) const { if(sz != b.sz) return sz < b.sz; return id > b.id; }
inline bool operator==(const Node2 &b) const { return sz == b.sz && id == b.id; }
};
priority_queue<int, vector<int>, greater<int> > pt[N];
myHeap<Node1> mn;
myHeap<Node2> sz;
int cs[N];
int ans[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
addEdge(u, v, w);
addEdge(v, u, w);
}
mxp[0] = INF;
dfs1(1, 0);
dfs2(rt, 0);
for(int i = 1; i <= n; i++) sum += 2 * d[i];
cout << sum << '\n';
anc[rt] = ++nn;
for(int i = 1; i <= n; i++) pt[anc[i]].push(i);
for(int i = 1; i <= nn; i++) {
mn.push({i, pt[i].top()});
sz.push({i, cs[i] = pt[i].size() * 2});
}
for(int i = 1; i <= n; i++) {
int p1 = anc[i], p2, j;
sz.erase({p1, cs[p1]});
sz.push({p1, --cs[p1]});
if(sz.top().sz == n - i + 1 && sz.top().id != nn) p2 = sz.top().id;
else p2 = mn.top(p1).id;
j = pt[p2].top();
ans[i] = j;
mn.erase({p2, j});
sz.erase({p2, cs[p2]});
pt[p2].pop();
if(!pt[p2].empty()) mn.push({p2, pt[p2].top()});
sz.push({p2, --cs[p2]});
}
for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
cout << '\n';
return 0;
}
|
这是一道交互题。有一个包含 \(n\) 个节点的 DAG，保证：
- 所有边都是从编号大的点连向编号小的点；
- 图的最小链覆盖不超过 \(2\)；
你初始只知道图的点数 \(n\)。你需要向交互器提出不超过 \(2n\) 个询问，每次你可以询问图上 \(i,j\) 两个点，交互器会告诉你 \(j\) 能否到达 \(i\)。然后，你需要给出图的一种黑白染色方案，满足：颜色相同的点分布在同一条链上。
显然 DAG 形如两条链中间任意连了一些边。我开始 naive 了，以为只询问 \((i,i+1)\) 然后二分图染色就行。其实中间的边完全可以扰乱这个过程，使得你染出来的某一侧不能形成链。
考虑扫描 \(1\sim n\) 的点然后动态维护两条链的前缀。考虑加入一个新的点 \(i+1\)。如果加入的点始终只向其中一条链的链尾有连边，那么显然是容易的（上面那个算法也能过）。因为此时你可以保证两条链的链尾之间没有连边；根据题目限制，新加的点一定向两个链尾连至少一条边。
考虑如何处理同时向两个链尾连边的情况。发现如果不考虑后面的点是没法判断当前点应该加到哪条链后面的（第一种算法就假在这里）。因此考虑开第三条链维护这些不确定的点。
此时，再新加一个点，如果它向第三条链的链尾有连边，那么它的情况等价于同时向两个链尾连边，因此追加到第三条链末尾。否则，无论如何它不能合并到第三条链末尾，因此将它追加到原来的两条链之一，然后将第三条链直接拼接在另一条链后面。发现此时仍然满足两条链的末尾之间没有边相连。
发现可以将加入一个点的询问次数压缩在 \(2\) 次以内。
代码
| #include<iostream>
using namespace std;
const int N = 110;
int T, n;
int ans[N];
int s2[N];
int t0, t1, t2;
bool query(int i, int j) {
cout << "? " << i << ' ' << j << endl;
cout.flush();
string tmp;
cin >> tmp;
return tmp == "YES";
}
int main() {
cin >> T;
while(T--) {
cin >> n;
t0 = t1 = t2 = 0;
t0 = 1;
ans[1] = 0;
for(int i = 2; i <= n; i++) {
if(t2 && query(s2[t2], i)) s2[++t2] = i;
else if(t0 && query(t0, i)) {
if(!t2 && t1 && query(t1, i)) {
s2[++t2] = i;
continue;
}
t0 = i;
ans[i] = 0;
if(t2) t1 = s2[t2];
while(t2) ans[s2[t2--]] = 1;
} else {
t1 = i;
ans[i] = 1;
if(t2) t0 = s2[t2];
while(t2) ans[s2[t2--]] = 0;
}
}
while(t2) { ans[s2[t2--]] = 0; }
cout << "! ";
for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
cout << endl;
cout.flush();
}
return 0;
}
|
给定一个长为 \(n\) 的序列 \(a_{1\sim n}\)，求 \(\operatorname{mex}\bigl(\{\operatorname{lcm}_{i=l}^{r}a_i\mid 1\le l\le r\le n\}\big)\)。
\(n\le 3\times 10^5\)
注意到固定右端点之后，区间 \(\operatorname{lcm}\) 只有本质不同的 \(\log V\) 个，因此集合大小不超过 \(n\log V\)。考虑如何求出这个集合。
考虑动态维护每个前缀的后缀 \(\operatorname{lcm}\) 集合。发现在加入一个数字之后，只需把原先集合中的数字都和当前数字取 \(\operatorname{lcm}\)，再把太大的部分砍掉，时间复杂度就是对的。用 set 维护即可。
代码
| #include<iostream>
#include<set>
#include<algorithm>
using namespace std;
const int N = 3e5 + 10;
const int LIM = 1e7;
int T, n;
int a[N];
set<int> ans, tmp;
long long sta[N], top;
inline long long lcm(int a, int b) {
return (long long)a / __gcd(a, b) * b;
}
int main() {
cin >> T;
while(T--) {
cin >> n;
ans.clear(); tmp.clear();
for(int i = 1; i <= n; i++) cin >> a[i];
tmp.insert(a[1]); ans.insert(a[1]);
for(int i = 2; i <= n; i++) {
for(int j : tmp) sta[++top] = lcm(j, a[i]);
tmp.clear();
while(top) {
if(sta[top] <= LIM) { tmp.insert(sta[top]); ans.insert(sta[top]); }
--top;
}
tmp.insert(a[i]); ans.insert(a[i]);
}
for(int i = 1; i <= LIM; i++) {
if(!ans.count(i)) { cout << i << '\n'; break; }
}
}
return 0;
}
|
给定一个正整数集合 \(A\)，你每次可以选择集合中一个数字 \(k\)，将它分解为 \(k=xy\)，然后将 \(k\) 删掉，\(x,y\) 加入集合。问经过若干次操作，集合的极差最小是多少。
\(n\le 10^6,~a_i\le 5\times 10^6\)
考虑双指针进行枚举，外层枚举集合的下界，然后不断缩紧集合的上界（外层枚举集合的上界显然是没有前途的）。设集合当前的范围为 \([l+1,r]\)，考虑 \(l+1\) 转移到 \(l\) 时的情况，那么一些数字可以分解成 \(l\) 和一些别的，情况增加，因此更优。
设 \(f_x\) 表示在当前下界 \(l\) 下，将数字 \(x\) 分解成若干数字，最大值最小是多少。在加入一个 \(l\) 时，我们枚举 \(x=kl,~(k\ge l)\)，并进行转移：
\[
f_{kl}=\min(f_{kl},f_{k})
\]
记得更新边界 \(f_l=l\)。这样复杂度形如一个调和级数。过程中动态维护 \(f(a_i)\) 的桶，更新边界之后，根据桶来缩紧上界即可。
代码
| #include<iostream>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int V = 5e6 + 10;
const int INF = 0x3f3f3f3f;
int T;
int n, m, k;
int a[V], f[V], cnt[V];
int ans;
void clear() {
ans = INF;
for(int i = 0; i <= m + 5; i++) a[i] = cnt[i] = 0;
for(int i = 0; i <= m + 5; i++) f[i] = INF;
st.clear();
k = 0;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while(T--) {
cin >> n >> m;
clear();
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
if(!a[x]) ++k;
a[x] = 1;
}
for(int i = m, r = m, c = 0; i >= 1; i--) {
f[i] = i;
if(a[i]) ++cnt[i], ++c;
for(int j = i; j * i <= m; j++) {
if(f[j] < f[j * i]) {
if(a[j * i]) --cnt[f[j * i]];
f[j * i] = f[j];
if(a[j * i]) ++cnt[f[j * i]];
}
}
while(r > i && !cnt[r]) --r;
if(c == k) ans = min(ans, r - i);
}
cout << ans << '\n';
}
return 0;
}
|
给定一个长为 \(n\) 的有序二元组序列 \((l_i,r_i),~(i\in [1,n],~l_i\le r_i)\)。考虑一个序列 \(a_{1\sim n}\) 满足 \(a_i\in [l_i,r_i]\)。现在有 \(q\) 次询问，每次询问给定 \([x,y]\)，询问 \(\operatorname{OR}_{i=x}^{y}a_i\)（按位或）的最大值。
\(n,q\le 2\times 10^5\)
考察 \(a_i\) 和 \(r_i\) 的最长公共前缀，记其长度为 \(k\)。如果 \(a_i\) 从高往低数的第 \(k+1\) 位为 \(0\)，\(r_i\) 从高往低数的第 \(k+1\) 位是 \(1\)，那么从第 \(k+2\) 位往后就都可以取 \(1\) 了。
因此预处理 \(f_{i,j,k}\) 表示区间 \([i,j]\) 中 \(r_i\) 的第 \(k\) 位有多少个 \(1\)；\(g_{i,j,k}\) 表示区间 \([i,j]\) 中 \(r_i\) 的第 \(k\) 位有多少个 \(1\) 能变成 \(0\)（也就是在 \(l_i,r_i\) 的公共前缀后面并且值为 \(1\)，变成 \(0\) 之后可以把后面全填上 \(1\)）。对于每次询问，我们从高位往低位处理，考虑第 \(k\) 位，
- 若 \(f_k=0\)，那么该位只可能是 \(0\)；
- 若 \(f_k>0\)，那么必须优先保证当前位为 \(1\)，再去考虑后面的位；
- 若 \(f_k\ge 2\wedge g_k\ge 1\)，那么选择一个 \(1\) 变成 \(0\)，后面的位都填 \(1\) 就行了，结束贪心；
\(f\) 和 \(g\) 容易在 \(O(n\log V)\) 的时间内预处理出来。因此总时间复杂度为 \(O\big((n+q)\log V\big)\)。
代码
| #include<iostream>
using namespace std;
const int N = 2e5 + 10;
inline int lg(int x) {
int res = -1;
while(x) { ++res; x >>= 1; }
return res;
}
int T, n, q;
int a[N], b[N];
int f[N][30], g[N][30];
void clear() {
for(int i = 0; i <= n + 5; i++) {
for(int j = 0; j < 30; j++) f[i][j] = g[i][j] = 0;
}
}
int main() {
cin >> T;
while(T--) {
cin >> n;
clear();
for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
for(int i = 1; i <= n; i++) {
int tmp = lg(a[i] ^ b[i]);
for(int j = 0; j < 30; j++) {
f[i][j] = f[i - 1][j] + ((b[i] >> j) & 1);
g[i][j] = g[i - 1][j] + (((b[i] >> j) & 1) && (j <= tmp));
}
}
cin >> q;
while(q--) {
int l, r, ans = 0;
cin >> l >> r;
for(int i = 29; i >= 0; i--) {
if(f[r][i] - f[l - 1][i] == 0) continue;
ans |= (1 << i);
if(f[r][i] - f[l - 1][i] == 1) continue;
if(g[r][i] - g[l - 1][i]) { ans += (1 << i) - 1; break; }
}
cout << ans << ' ';
}
cout << '\n';
}
return 0;
}
|
给定一个长为 \(n\) 的排列，你等概率选择一段区间 \([l,r]\) 然后等概率重排这段区间内的数。问得到的新序列的逆序对的期望个数。
\[
n\le 10^5
\]
注意到横跨区间内外的逆序对不会被影响。并且等概率随机重排区间 \([l,r]\) 后，\([l,r]\) 内的期望逆序对数量就是长为 \(r-l+1\) 的随机排列的期望逆序对数。因此问题转化为选择一段区间 \([l,r]\)，\([l,r]\) 内的逆序对数量的期望是多少。期望可以转换为求和。
考虑从大到小扫描值域，发现一个数字 \(a_i\) 的贡献等于它左边已经被加进来的点的下标之和，乘以 \(n-i+1\)。于是直接做做完了。
代码
| #include<iostream>
#include<iomanip>
#define int long long
#define ld long double
using namespace std;
const int N = 1e5 + 10;
int n;
ld ans;
int a[N], ia[N];
namespace BIT {
int sum[N];
inline void clear() {
for(int i = 0; i <= n + 5; i++) sum[i] = 0;
}
inline void add(int p, int v) {
for(int i = p; i <= n; i += i & -i) sum[i] += v;
}
inline int query(int p) {
int res = 0;
for(int i = p; i > 0; i -= i & -i) res += sum[i];
return res;
}
}
signed main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) ia[a[i]] = i;
for(int i = 1; i <= n; i++) {
ans += (ld)(i * (i - 1) / 2) * (n - i + 1) / 2;
}
for(int i = n; i >= 1; i--) {
int p = ia[i];
ans -= (ld)BIT::query(p) * (n - p + 1);
BIT::add(p, p);
}
ans /= n * (n + 1) / 2;
BIT::clear();
for(int i = n; i >= 1; i--) {
ans += BIT::query(a[i]);
BIT::add(a[i], 1);
}
cout << fixed << setprecision(12) << ans << '\n';
return 0;
}
|
bitset 高维偏序板子。用扫描线可以做到 \(O(nm+\frac{n^2m}{\omega})\)。