智灵班分班考 · Day1

时间线

• 8:00 在滨兰实验的远古机房中的一个键盘手感爆炸的电脑上开考。
• 开 T1，推了推发现可以 segment tree 优化 dp，由于按空格需要很大的力气导致马蜂被迫改变。后来忍不住了顶着疼痛按空格。
• 8:30 过了样例，但是没有大样例，先这样吧。
• 开 T2，发现每颗子树可以对应到序列上的一段区间，感觉可以区间 dp，但是怎么知道左右儿子的点的左右手写上什么呢？
• 苦思冥想到 9:45，思考无果打算打一个暴搜，暴搜过程中发现状态数可以直接从 $O(n^4)$ 降到 $O(n^3)$，但是我忘了转移还要 $O(n)$ 导致我以为我莫名其妙获得正解，于是把暴搜加了个 $O(n^3)$ 空间复杂度的记忆化数组（$n\le 500$）。
• 10:20 开 T3，一眼盯真，维护每个区间的支配点对，这只有 $O(n\log V)$ 个，然后转二维数点；二维数点过程中推出了形如给定 $[l,r]$，数 $l\le u\le v\le r$ 的数量，脑子爆炸以为要数 $(l,l)$ 到 $(r,r)$ 的矩形，发明了一会儿二维 st 未果，最后注意到只要数 $l\le u\le n$，$1\le v\le r$ 就可以了。糖丸力
• 写完调完 T3 是 11:10，赶紧开 T4，一眼盯真，对 dfn 序维护线段树，线段树每个节点维护一个 01 Trie，单点修改就修改一整条链，查询正常查询，时空复杂度 $O(n\log n\log V)$，赶紧冲！欸之前是不是过来说了啥 T4 某个样例要改一改？算了不管了。
• 写写写，11:45 分写完，测样例发现错了（其实是因为样例是错的），以为自己读错题了，爆裂鼓手，遗憾离场。

期望得分 100+60+100+70，实际得分 30+0+100+0。挂了 200 分，天下无敌！

总榜排名第 50，下一场需要翻 20+ 名。

题解 & 错因

T1

给定一个长度为 $n$ 的数列 $a$，你需要选出若干个不相交也不相邻的区间（即任意两个区间中间至少隔一个元素），一个区间 $[l,r]$ 能被选当且仅当 $l=r$ 或者 $\forall i\in [l+1,r]$，满足 $a_i\ge {\sum }_{j=l}^{i-1}{a}_j$；求所有方案中区间中元素的最大和。

$2\le n\le 2\times 10^5$，$1\le a_i\le 10^9$。

设 $f(i)$ 表示考虑完 $[1,i]$ 的答案。注意到以 $a_i$ 为选中区间右端点时，最长可选区间的左端点随着 $i$ 增大单调不降，于是可以双指针维护这个左端点。从 $j$ 转移的式子是 $f(i)\leftarrow {\max }_{k<j-1}f(k)+{\sum }_{k=j}^i{a}_k$，令 $s_i={\sum }_{j=1}^i{a}_i$ 那么就是 $f(i)\leftarrow {\max }_{k<j-1}f(k)+s_i-s_{j-1}$，令 $g(j)={\max }_{k<j}f(k)-s_j$，线段树维护这个东西的区间最大值即可。时间复杂度 $O(n\log n)$。

为啥我挂成 30pts 了呢？赛时 $g(j)$ 的表达式错误的认为是 $f(j-1)-s_j$，也就是坚定的认为只要隔一个元素。痛失 70pts。

#include <bits/stdc++.h>
bool MemoryST; using namespace std;
#define ll long long
#define mk make_pair
#define open(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define lowbit(x) ((x) & (-(x)))
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define BCNT __builtin_popcount
#define cost_time (1e3 * clock() / CLOCKS_PER_SEC) << "ms"
#define cost_space (abs(&MemoryST - &MemoryED) / 1024.0 / 1024.0) << "MB"
const int inf = 0x3f3f3f3f; 
const ll linf = 1e18; 
mt19937 rnd(random_device{}());
template<typename T> void chkmax(T& x, T y) { x = max(x, y); }
template<typename T> void chkmin(T& x, T y) { x = min(x, y); }
template<typename T> T abs(T x) { return (x < 0) ? -x : x; }const int maxn = 2e5 + 5;
int n, a[maxn]; ll sum[maxn];
ll f[maxn];
ll mx[maxn<<2];
// 一开始空格按的难受死了没打空格
void update(int rt){mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
}void build(int l,int r,int rt){if(l==r){mx[rt]=-1e18;return;}int mid=(l+r)>>1;build(lson),build(rson),update(rt);
}ll query(int l,int r,int rt,int nowl, int nowr){if (nowl > nowr) return 0;if(nowl<= l && r <= nowr) return mx[rt];int mid = (l + r) >> 1; ll res = -1e18;if (nowl <= mid) res = max(res, query(lson, nowl, nowr));if (mid < nowr) res = max(res, query(rson, nowl, nowr));return res;
}
// 忍不住开始打空格
void modify(int l, int r, int rt, int now, ll k) {if (l == r) return mx[rt] = max(mx[rt], k), void(0);int mid = (l + r) >> 1;if (now <= mid) modify(lson, now, k);else modify(rson, now, k);update(rt);
}
bool MemoryED; int main() {scanf("%d",&n),build(0,n,1);for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];modify(0, n, 1, 0, -sum[1]);modify(0, n, 1, 1, (f[1] = a[1]) - sum[2]);ll ans = a[1];for(int i=2,j=1;i<=n;i++){for(j<i;sum[i-1]-sum[j-1]>a[i];j++);f[i] = f[i - 1];if (j == 1) {chkmax(f[i], sum[i]);modify(0, n, 1, i, sum[i] - sum[i + 1]);} else {chkmax(f[i], query(0, n, 1, j - 2, i - 2) + sum[i]);modify(0, n, 1, i, f[i] - sum[i + 1]);} ans = max(ans, f[i]);}printf("%lld\n", ans);return 0;
}

T2

给定一个长度为 $n$ 的序列 $a$，对于所有中序遍历为 $1,2,\cdots ,n$ 且是以点的编号为键值的二叉搜索树，定义一个点 $u$ 的权值是：从 $u$ 到根节点的路径中，深度最深的是父节点左儿子的父节点权值（若没有则是 $1$）乘上深度最深的是父节点右儿子的父节点权值（若没有则是 $1$），整棵树的权值是所有点的权值的和。求所有树的权值的最大值。

$1\le n\le 500$，$1\le a_i\le 10^7$。

注意到任意一个区间 $[l,r]$ 都可以对应一个子树。不妨我们指定 $[l,r]$ 这颗子树的根节点是 $x$（$l\le x\le r$），我们考察 $x$ 是哪两个父节点的权值乘积。

由图可知：$x$ 的权值就是 $a_{l-1}\times a_{r+1}$，不妨认为 $a_0=a_{n+1}=1$。那就可以进行区间 dp 了，设 $f(l,r)$ 表示子树 $[l,r]$ 的最大权值，转移就是
$$f(l,r)=a_{l-1}\times a_{r+1}+\underset{l\le x\le r}{\max }f(l,x-1)+f(x+1,r)$$
时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。

为啥赛时没推出来呢？我一直在想能不能把点从根转化为从根到点，这样子权值就变成最后一个满足条件的点而非第一个，然后 balabala 就坠机了。开了一个 $500\times 500\times 500\times 2$ 的数组导致 MLE 0pts。

#include <bits/stdc++.h>
bool MemoryST; using namespace std;
#define ll long long
#define mk make_pair
#define open(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define lowbit(x) ((x) & (-(x)))
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define BCNT __builtin_popcount
#define cost_time (1e3 * clock() / CLOCKS_PER_SEC) << "ms"
#define cost_space (abs(&MemoryST - &MemoryED) / 1024.0 / 1024.0) << "MB"
const int inf = 0x3f3f3f3f; 
const ll linf = 1e18; 
mt19937 rnd(random_device{}());
template<typename T> void chkmax(T& x, T y) { x = max(x, y); }
template<typename T> void chkmin(T& x, T y) { x = min(x, y); }
template<typename T> T abs(T x) { return (x < 0) ? -x : x; }
const int maxn = 505;
int n, a[maxn]; ll f[maxn][maxn];
bool MemoryED; int main() {scanf("%d", &n), a[0] = a[n + 1] = 1;for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);for (int i = 1; i <= n; i ++) f[i][i] = 1ll * a[i - 1] * a[i + 1];for (int len = 2; len <= n; len ++)for (int l = 1, r = l + len - 1; r <= n; l ++, r ++) {for (int x = l; x <= r; x ++)chkmax(f[l][r], (x == l ? 0 : f[l][x - 1]) + (x == r ? 0 : f[x + 1][r]));f[l][r] += 1ll * a[l - 1] * a[r + 1];}printf("%lld", f[1][n]);return 0;
}

T3

给定一个长度为 $n$ 的序列 $a$，$Q$ 次询问，每次给定 $[l,r]$（保证 $l<r$），求
$$\underset{i,j\in [l,r],i\ne j}{\max }\gcd (a_i,a_j)$$
$n,Q\le 2\times 10^5$。

luqyou 在前两天的膜你赛中出了近乎一样的题，且昨天晚上寝室的杂题选讲环节中有人提到了支配点对这个东西。考虑一对 $(i_1,j_1)$，如果有一对 $(i_2,j_2)$ 满足 $i_1\le i_2<j_2\le j_1$ 且 $\gcd (a_{i_1},a_{j_1})\le \gcd (a_{i_2},a_{j_2})$，那 $(i_1,j_1)$ 的贡献就不需要考虑了。也就是说，我们可以找出若干对真正对每个询问有贡献的点对，称为支配点对。哪些点对是支配点对呢？考虑对于每个 $d$，我们找出所有是 $d$ 的倍数的 $a_i$ 的下标序列 $i_1,i_2\cdots ,i_k$，从小到大排序后显然只有 $(i_1,i_2),(i_2,i_3),\cdots$ 这样的点对可能是支配点对。进一步分析，对于一个 $i$，假设在上一步中选出了若干个可能为支配点对的点对 $(i,j_1),(i,j_2),\cdots ,(i,j_k)$ 并且 $j_1<j_2<\cdots <j_k$；那么对于一个 $j_u<j_v$，如果 $\gcd (i,j_u)\ge \gcd (i,j_v)$ 那么 $(i,j_v)$ 这对点对也没有用了。这样最终的点对数量大概是所有 $a_i$ 的因子个数和，但显然远远不到，大概可以估成 $O(n\log n)$。最后做一个二维数点即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5, V = 2e5;
int n, Q, a[maxn]; vector<int> tab[maxn];
vector<int> f[maxn]; vector<pair<int, int> > imp[maxn];
#define lowbit(x) ((x) & (-(x)))
struct Point {int x, y, val, qid;
}; vector<Point> p;
int b[maxn], ans[maxn];
void add(int x, int v) { x = n - x + 1;for (; x <= n; x += lowbit(x))b[x] = max(b[x], v);
} int ask(int x) { x = n - x + 1;int res = 0;for (; x; x -= lowbit(x))res = max(res, b[x]);return res;
} 
#define open(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
int read() {char c = getchar();for (; c < '0' || c > '9'; c = getchar());int s = 0;for (; c >= '0' && c <= '9'; c = getchar())s = (s << 1) + (s << 3) + (c ^ 48);return s;
}
int main() { // open(data);n = read();for (int i = 1; i <= n; i ++)a[i] = read(), tab[a[i]].push_back(i);for (int i = 2; i <= V; i ++)for (int j = i; j <= V; j += i)if (!tab[j].empty())for (int k : tab[j]) f[i].push_back(k);for (int i = 2; i <= V; i ++) if ((int)f[i].size() > 1) {int len = (int)f[i].size(); sort(f[i].begin(), f[i].end());for (int j = 0; j < len - 1; j ++) {int now = f[i][j], nxt = f[i][j + 1];while (!imp[now].empty() && imp[now].back().second >= nxt) imp[now].pop_back();imp[now].emplace_back(i, nxt);}} for (int i = 1; i <= n; i ++)for (auto j : imp[i]) p.push_back(Point { j.second, i, j.first, 0 });Q = read();for (int i = 1, L, R; i <= Q; i ++) L = read(), R = read(), p.push_back(Point { R, L, 0, i });sort(p.begin(), p.end(), [&](const Point &x, const Point &y) {return x.x == y.x ? y.qid > 0 : x.x < y.x;}); for (Point cur : p) {int x = cur.x, y = cur.y, val = cur.val, qid = cur.qid;if (qid != 0) ans[qid] = max(1, ask(y));else add(y, val);} for (int i = 1; i <= Q; i ++)printf("%d\n", ans[i]);return 0;
} 

唯一一道做对的题

T4

给定一个树，初始只有一个根节点 $1$，$Q$ 次操作，要么给定一个点 $x$ 和一个 $w$，在 $x$ 节点的孩子中增加一个点，边权为 $w$；要么给定 $u,v$，求对于所有 $v$ 子树中的点 $i$，$u$ 到 $i$ 的路径的边权异或和的最大值。

$1\le Q\le 2\times 10^5$，$0\le w\le 2^{30}$。

把操作离线下来得到一棵 $n$ 个点的树。考虑 $u,v$ 两点间路径异或和就等于 $u$ 到根的路径异或和异或上 $v$ 到根的路径异或和，那操作就变成：

• 给一个点一个点权；
• 给定一个 $w$ 和点 $u$，求 $u$ 的子树中所有点权异或上 $w$ 的最大值。

不妨在这棵树上 dfs，每个点维护一个子树中所有点权的 01Trie，每次像线段树合并那样合并孩子的 01Trie；01 Trie 上对每条边维护一个最早建立时间即可。时间复杂度 $O(n\log n)$。

赛时做法因为空间爆了只能拿 70pts，好像也能进行类似的离线使空间复杂度下降。

#include <bits/stdc++.h>
bool MemoryST; using namespace std;
#define ll long long
#define mk make_pair
#define open(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define lowbit(x) ((x) & (-(x)))
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define BCNT __builtin_popcount
#define cost_time (1e3 * clock() / CLOCKS_PER_SEC) << "ms"
#define cost_space (abs(&MemoryST - &MemoryED) / 1024.0 / 1024.0) << "MB"
const int inf = 0x3f3f3f3f; 
const ll linf = 1e18; 
mt19937 rnd(random_device{}());
template<typename T> void chkmax(T& x, T y) { x = max(x, y); }
template<typename T> void chkmin(T& x, T y) { x = min(x, y); }
template<typename T> T abs(T x) { return (x < 0) ? -x : x; }
const int maxn = 2e5 + 5;
int Q, tim[maxn], f[maxn], n; vector<pair<int, int> > que[maxn];
namespace Graph {struct Edge { int to, nxt; } e[maxn << 1];int head[maxn], ecnt;void addEdge(int u, int v) { e[++ ecnt] = Edge { v, head[u] }, head[u] = ecnt; }
} using namespace Graph; char tmp[10];
struct Trie {Trie *son[2]; int create_time;Trie(int t0 = inf) { son[0] = son[1] = nullptr, create_time = t0; }
} *root[maxn];
void insert(Trie *rt, int x, int tim) {Trie *cur = rt;for (int i = 29; ~i; i --)if (x & (1 << i)) {if (cur -> son[1] == nullptr)cur -> son[1] = new Trie();chkmin(cur -> son[1] -> create_time, tim), cur = cur -> son[1];} else {if (cur -> son[0] == nullptr)cur -> son[0] = new Trie();chkmin(cur -> son[0] -> create_time, tim), cur = cur -> son[0];}
} int query(Trie *rt, int x, int tim) {Trie *cur = rt; int ans = 0;for (int i = 29; ~i; i --) if (x & (1 << i)) {if (cur -> son[0] != nullptr && cur -> son[0] -> create_time < tim)ans += (1 << i), cur = cur -> son[0];else cur = cur -> son[1];} else {if (cur -> son[1] != nullptr && cur -> son[1] -> create_time < tim)ans += (1 << i), cur = cur -> son[1];else cur = cur -> son[0];}return ans;
} Trie *merge(Trie *rt, Trie *oth) {if (rt == nullptr) return oth;if (oth == nullptr) return rt;chkmin(rt -> create_time, oth -> create_time);rt -> son[0] = merge(rt -> son[0], oth -> son[0]), rt -> son[1] = merge(rt -> son[1], oth -> son[1]);delete oth; oth = nullptr; return rt;
} int ans[maxn]; void dfs(int u, int fa) {root[u] = new Trie(0); insert(root[u], f[u], tim[u]);for (int i = head[u], v; i; i = e[i].nxt) {if ((v = e[i].to) == fa) continue;dfs(v, u), root[u] = merge(root[u], root[v]);} for (auto [tim, val] : que[u])ans[tim] = query(root[u], val, tim);
} vector<int> qid;
bool MemoryED; int main() {scanf("%d", &Q); int n = 1; tim[1] = f[1] = 0;for (int i = 1, u, v, w; i <= Q; i ++) {scanf("%s", tmp);if (tmp[0] == 'A') {scanf("%d %d", &u, &w), tim[++ n] = i;f[n] = f[u] ^ w, addEdge(n, u), addEdge(u, n);} else scanf("%d %d", &u, &v), que[v].emplace_back(i, f[u]), qid.push_back(i);} dfs(1, 0); for (int i : qid) printf("%d\n", ans[i]);return 0;
}

还是非常好写的。