Intro
跑去上海打了这两场考试，结果惨不忍睹 (╯‵□′)╯︵┻━┻
所以我取消了最近几天的行程专心写题 _(:з)∠)_
本文缓慢更新，一些神仙题可能我一辈子都改不出来。
由于洛谷的新版界面丑陋不堪，除非迫不得已，将不提供洛谷的原题链接。
Day 1
异或粽子
简述题意
给定一个数列，求前 $k$ 大的区间异或值的和。
吐槽
它不希望用同样的馅儿的集合做出一个以上的粽子。
这句话被我理解成了 “不希望用同样的馅儿 的集合”，以至于我认为所有集合是互斥的。成功爆零。
思路
我们对这个数列做一下前缀异或，令得到的数列为 $s$，问题实际上就是求 $k$ 个数对 $(i,j),1\le i\le j \leq n$，使得 $s[i-1] \ \text{xor} \ s[j]$ 之和最大。
如果我们固定 $j$ ，我们很容易在 $s[1] – s[j]$ 中找到一个 $i$ ，使得 $s[i-1] \ \text{xor} ] s[j]$ 的值为所有 $i$ 中的第 $k$ 大：对 $s[1] – s[j]$ 建立 $\text{Trie}$ 树，并记录子树大小，从根开始贪心查找即可。
首先，我们可以对于每个 $j$，找到最优的 $i$，将这个数对的答案记为 $v$，并且将 $(j,v,1)$ 这个三元组加入以 $v$ 为关键字的堆中。现在我们取出堆顶的三元组 $(j’,v’,p)$，将 $v’$ 计入答案，然后找出第 $p+1$ 优的 $i$ 对应的答案 $v”$，将三元组 $(j’,v”,p+1)$ 加入堆中。重复这个过程 $k$ 次，就可以得到最终的答案。
如果这样写，你需要一棵可持久化 $\text{Trie}$ 树，时空复杂度都不够优秀。
思考一下，我们需要可持久化，是因为数对 $(i,j)$ 里，$1\le i\le j \leq n$ 的限制；如果我们取消这个限制，会发生什么？
一个数对会被统计两次，仅此而已。所以不需要可持久化，找到前 $2k$ 个数对，最后的答案再除以 $2$ 即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+1;
typedef long long ll;
ll read(){
ll x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x;
}
struct node{
int id,k;ll val;
node(int a=0,int b=0,ll c=0){
id=a,k=b,val=c;
}
bool operator < (const node &x) const{
return val<x.val;
}
};
int n,k;
ll a[maxn],ans;
int t[maxn<<5][2],siz[maxn<<5],tot;
priority_queue<node>q;
void insert(ll x){
int pos=0;
for (int i=31;i>=0;--i){
int son=(x>>i)&1;
siz[pos]++;
if (!t[pos][son])
t[pos][son]=++tot;
pos=t[pos][son];
}
siz[pos]++;
}
ll query(ll x,int rank){
int pos=0;ll ans=0;
for (int i=31;i>=0;--i){
int son=(x>>i)&1;
if (!t[pos][son^1])
pos=t[pos][son];
else if (rank<=siz[t[pos][son^1]])
pos=t[pos][son^1],ans|=1ll<<i;
else rank-=siz[t[pos][son^1]],pos=t[pos][son];
}
return ans;
}
int main(){
n=read(),k=read();
for (int i=1;i<=n;++i)
a[i]=read()^a[i-1];
for (int i=0;i<=n;++i)
insert(a[i]);
for (int i=0;i<=n;++i)
q.push(node(i,1,query(a[i],1)));
for (int i=1;i<=2*k;++i){
node u=q.top();
ans+=u.val;q.pop();
if (u.k>=n) continue;
q.push(node(u.id,u.k+1,query(a[u.id],u.k+1)));
}
printf("%lld\n",ans/2);
}Day 2
春节十二响
简述题意
给定一个带点权树，求一种点集划分方案，使得任意集合内不存在两个点为祖先关系，最小化每个集合内点权最大值之和。
思路
可能是本次联考最简单的一道题？
我们从链的部分分得到启发。对于链的数据，因为在同一条从根向下的链上的点必须在不同集合内，我们可以从大到小贪心合并左右两条链。理解了这个做法，我们可以将它推广到一般情况。
给每个点分配一个优先队列，存储由它向下的链上可以被合并的所有点权。那么在树上 DFS 的时候，直接贪心合并一个点每个儿子的优先队列即可。
注意到直接合并是 $\Theta(n^2)$ 的。改为启发式合并，每次合并时两个队列时，保留最长的优先队列，这样复杂度就直接来到了 $\Theta(n\log n)$。
代码
#include <bits/stdc++.h>
#define chkmax(a,b) (b>a?a=b:0)
using namespace std;
const int maxn=2e5+1;
const int inf=1e9+1;
typedef long long ll;
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x;
}
priority_queue<int>q[maxn];
vector<int>son[maxn];
int sta[maxn],top,cnt;
int n,fa[maxn],val[maxn],cur[maxn];
ll ans;
void solve(int u){
cur[u]=++cnt;
for (auto v:son[u]){
solve(v);
if (q[cur[u]].size()<q[cur[v]].size())
swap(cur[u],cur[v]);
top=q[cur[v]].size();
for (int i=1;i<=top;++i){
sta[i]=max(q[cur[u]].top(),q[cur[v]].top());
q[cur[u]].pop();q[cur[v]].pop();
}
for (int i=1;i<=top;++i) q[cur[u]].push(sta[i]);
}
q[cur[u]].push(val[u]);
}
int main(){
n=read();
for (int i=1;i<=n;++i)
val[i]=read();
for (int i=2;i<=n;++i)
son[fa[i]=read()].push_back(i);
solve(1);
while(!q[cur[1]].empty())
ans+=q[cur[1]].top(),q[cur[1]].pop();
printf("%lld\n",ans);
}