P3292 [SCOI2016]幸运数字 题解
EastPorridge
·
·
题解
写了一个 猫树 的博客，里面有几道题。
题目分析：
我们有个最暴力的做法，树剖线段树套线性基，树剖，线段树各一个 \log，线性基合并俩 \log，一共四个 \log。
具体来说就是我们树剖每次会从树上拆分出一条路径，我们没必要立刻知道它的答案，而是再把它看成一个询问，这样的复杂度怎么样呢？
树剖一次最多会跳 $\log n$ 个链头，$q$ 次询问，所以我们把原问题拆成了**序列**上的 $q \log n$ 个子问题，每个问题是求 $l \sim r$ 这个区间任选值，使它的异或和最大。
怎么做呢？再用线段树是没区别的，我们考虑再次离线，这个问题可以使用猫树分治解决，具体的，我们每次维护以 $\text{mid}$ 为中心的，$l \sim \text{mid}$ 的后缀线性基和 $\text{mid+1} \sim r$ 的前缀线性基，如果此时询问区间 $[L,R]$ 横跨 $\text{mid}$，则可以通过合并左右两个线性基得出答案，否则，它一定在 $\text{mid}$ 的一边，分治下去就可以了。
这样做的复杂度瓶颈在线性基合并，是两个 $\log$ 的。
再进一步的，我们求出了 $q \log n$ 个子问题又能怎么样呢？能线性基合并。
我们求子问题的解是没用的，有用的是子问题的线性基，我们把猫树分治求出来的线性基再次合并。
理论部分结束，交一发，[寄了](https://www.luogu.com.cn/record/100349808)。
它跑的确实很快，考虑一下 MLE 的原因，原因是存的 $q \log n$ 个线性基，是一个很大的 $10^7$，虽然树剖一般不可能这么 $\log$，会小一点。
我们拿 `vector` 把它存下来，resize 来动态开空间，把树剖几件套换成 `short`，用完边直接用 `shrink_to_fit()` 把它释放掉，还有就是询问区间为 $l=r$ 的是不需要线性基的，我们通过标号的方式把它剔除，或者直接倍增或者根号分治处理掉一点询问等等技巧，凹一下就可以了，难点不在这里。
整个代码写了 $3.5 \text{KB}$，应该没人想看吧，只给树剖出子问题和猫树分治部分的代码了。
### Code.
```cpp
void pre(int u,int v)
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) swap(u,v);
pl.emplace_back(node{id[top[u]],id[u]}); ++tot;
u=fa[top[u]];
}
if(dep[u] < dep[v]) swap(u,v); pl.emplace_back(node{id[v],id[u]}); ++tot;
}
void sol(int l,int r,int L,int R)
{
if(L > R) return ; int mid = (l + r) >> 1;
f[mid].init(); for(int i=mid+1;i<=r;i++) f[i]=f[i-1],f[i].insert(a[i]);
f[mid].insert(a[mid]); for(int i=mid-1;i>=l;i--) f[i]=f[i+1],f[i].insert(a[i]);
int tmid=L-1; tn=0;
for(int i=L;i<=R;i++)
{
int tmp=p[i];
if(pl[tmp].r <= mid) p[++tmid]=tmp;
else if(mid < pl[tmp].l) s[++tn]=tmp;
else ans[tmp]=merge(f[pl[tmp].l],f[pl[tmp].r]);
}
for(int i=1;i<=tn;i++) p[tmid+i]=s[i]; R=tmid+tn;
sol(l,mid,L,tmid); sol(mid+1,r,tmid+1,R);
}
```