O(n)-O(1) LA
gxy001
·
·
题解
UPD: 补了个代码实现。
UPD2: 修复一处代码 bug。
网上没搜到欧拉序做法的博客，所以我就写了这篇博客。
利用欧拉序将 LA（Level-Ancestors） 问题转化为 \pm 1 FS（Find-Smaller）问题
注意到，x 的深度为 d 的祖先，在欧拉序上，是 x 后面的第一个深度 \le d 的节点，问题转化为 FS 问题，并且欧拉序具有 \pm 1 性质，所以问题变为 \pm 1 FS 问题，该问题有着线性预处理，常数查询的在线做法。
## $\pm 1$ FS 问题的 $\mathrm O(n\log n)$ 预处理，$\mathrm O(1)$ 查询的在线做法
**定义** $\mathrm {ctz}(i)$ 表示最大的满足 $2^k\mid i$ 的 $k$。
**定义** $\mathrm{lbt}(i,j)$（$i\le j$）表示，$[i,j]$ 内的所有整数中 $\mathrm{ctz}$ 最大的数；当 $i\le 0$ 时，定义其值为 $0$。
**引理** 对于任意 $i,j$（$i\le j$），令 $k=\mathrm{lbt}(i,j)$，显然有 $j-i+1\le 2^{\mathrm{ctz}(k)+1}$，以及 $j-k+1\le 2^{\mathrm{ctz}(k)}$。
$\pm 1$ FS 问题中给出的数组为 $a_{0\sim n-1}$，定义 $f(i)=3\times2^{\mathrm{ctz}(i)}$，$f(0)=n$。
对于每个 $0\le i<n$，预处理出数组 $B_{i,1\sim f(i)}$，其中 $B_{i,j}=\mathrm{FS}(i,a_i-j)$。
查询 $\mathrm{FS}(i,x)$ 时：
- 若 $x\ge a_i$，答案为 $i$；
- 令 $d=a_i-x$，若 $d\le f(i)$，答案为 $B_{i,d}$；
- 否则，令 $k=\mathrm{lbt}(i-d+1,i)$，答案为 $B_{k,a_k-x}$。
接下来给出证明。
首先证明 $a_k-x\le f(k)$：
$$
\begin{aligned}
2^{\mathrm{ctz}(k)+1}&>i-(i-d+1)=d-1=a_i-x-1\\
2^{\mathrm{ctz}(k)}&>i-k\\
3\times2^{\mathrm{ctz}(k)}&\ge a_i+i-k-x\ge a_k-x
\end{aligned}
$$
注意 $a_i+i-k\ge a_k$ 来自于 $\pm 1$ 性质。
然后证明 $\mathrm{FS}(k,x)=\mathrm{FS}(i,x)$。
有 $k>i-d=i-a_i+x$，即，$a_k\cdots a_i$ 所有数都 $\ge a_i-(i-k)>x$，所以有 $\mathrm{FS}(k,x)=\mathrm{FS}(i,x)$。
注意这一证明也依赖于 $\pm 1$ 性质。
$B$ 数组的预处理是简单的，我们从后往前扫一遍，开桶记录每个数的最靠前的出现位置，就可以预处理出来（因为 $\pm 1$ 性质，$\mathrm{FS}(i,a_i-j)$ 一定是 $i$ 后面最靠前的值为 $a_i-j$ 的位置），显然有 $B$ 数组的总长是 $\mathrm O(n\log n)$ 的。
由此，我们获得了 $\mathrm O(n\log n)$ 预处理，$\mathrm O(1)$ 查询的在线做法。
## $\mathrm O(n)$ 预处理，$O(1)$ 查询
首先按 $\mathrm O(\log n)$ 分块。
### 块间
第 $i$ 个块表示编号为 $ib\sim ib+b-1$ 的点。
对每个块，存储 $N_{i,1\sim 2b}$，其中 $N_{i,j}=\mathrm {FS}(ib,a_{ib}-j)$。
对每个块，存储 $F_{i,1\sim f(i)}$，其中 $F_{i,j}=\left\lfloor\frac{\mathrm{FS}(ib,a_{ib}-jb)}{b}\right\rfloor$，即 $\mathrm{FS}(ib,a_{ib}-jb)$ 所在的块。
注意到有令 $k=F_{i,j}$，则有 $a_{ib}-jb\le a_{kb}<a_{ib}-(j-1)b$，这一式子可以简单的使用 $\pm 1$ 性质给出证明。
$N,F$ 数组的预处理方式类似上文中的 $B$ 数组。
查询 $\mathrm{FS}(ib+j,x)$（$j<b$）时：
- 若 $x\ge a_{ib+j}$，返回 $ib+j$；
- 若 $j>0$：
- 通过块内查询，若答案在块内，则直接返回；
- 若答案不在块内，返回 $\mathrm{FS}((i+1)b,x)$；
- $j=0$：
- 若 $x\ge a_{ib}-2b$，返回 $N_{i,a_{ib}-x}$；（3）
- 令 $d=\left\lfloor\frac{a_{ib}-x}{b}\right\rfloor$：
- 若 $d\le f(i)$，令 $k=F_{i,d}$，返回 $\mathrm{FS}(kb,x)$；（2）
- 否则，令 $k=\mathrm{lbt}(i-d+1,i)$，返回 $\mathrm{FS}(kb,x)$。（1）
通过与之前证明类似的方式，我们可以证明，情况（1）一定会跳转至情况（2），这里不多赘述。
接下来证明情况（2）一定会跳转至情况（3）。
$$
a_{kb}<a_{ib}-(d-1)b<x+2b
$$
由此，我们获得了块间的处理方式。
### 块内
接下来介绍的是利用位掩码的方法，这种方法块长一般取 $w$。
$$
m(i,j)=\begin{cases}1&a_j<\min\{a_i,\dots,a_{j-1}\}\\0&\mathrm{otherwise}.\end{cases}
$$
那么，$m(ib+j,ib+j+1),m(ib+j,ib+j+2)\dots m(ib+j,ib+(b-1))$ 中第 $a_{ib+j}-x$ 个 $1$ 的位置就对应 $\mathrm{FS}(ib+j,x)$，如果不存在这样的位置，则说明答案不在块内。
我们将 $m(ib+j,ib+j+1),m(ib+j,ib+j+2)\dots m(ib+j,ib+(b-1))$ 压入一个数 $m_{ib+j}$ 内，查询即为查找第 $k$ 个为 $1$ 的二进制位位置，这一操作可以进行一些预处理后 $O(1)$ 实现。（据说存在部分硬件支持相关指令直接查询，我不太了解这方面）
由此，我们获得了块内的处理方式。
至此，我们获得了解决 LA 问题的线性预处理，常数在线查询的算法。
我看的这个论文最后给了点申必常数优化，我是完全没看懂，贴个[链接](https://arxiv.org/pdf/0909.1030.pdf)。
下面是我写的实现，很烂，没有任何常数优化，轻喷。
```cpp
#include<iostream>
#include<vector>
#include<bit>
using std::cin,std::cout;
unsigned s;
inline unsigned get(){
s^=s<<13;
s^=s>>17;
s^=s<<5;
return s;
}
int n,q,rt,p[500010],cnt,dfn[1000010],tmp[500010],d[500010];
unsigned long long t[1000010];
std::vector<int> v[500010],f[16010],g[16010];
void dfs(int x){
dfn[p[x]=cnt++]=x;
for(auto u:v[x]){
d[u]=d[x]+1,dfs(u);
dfn[cnt++]=x;
}
}
int lbt(int x,int y){
if(x<=0) return 0;
return y&~(std::bit_floor(unsigned(--x^y))-1);
}
int o[65536][16],pc[65536];
int squery(unsigned long long p,int x){
int u=p&65535;
if(x<pc[u]) return o[u][x];
x-=pc[u],p>>=16,u=p&65535;
if(x<pc[u]) return 16+o[u][x];
x-=pc[u],p>>=16,u=p&65535;
if(x<pc[u]) return 32+o[u][x];
x-=pc[u],u=p>>16;
if(x<pc[u]) return 48+o[u][x];
return -1;
}
int query(int x,int k){
if(d[dfn[x]]<=k) return dfn[x];
if(x&63){
int u=squery(t[x],d[dfn[x]]-k);
if(u!=-1) return dfn[x+u];
x=(x+64)&~63;
if(d[dfn[x]]==k) return dfn[x];
}
int i=x>>6;
int p=d[dfn[x]]-k;
if(p<=128) return g[i][p-1];
p>>=6;
if(p<=(int)f[i].size()) return query(f[i][p-1]<<6,k);
return query(lbt(i-p+1,i)<<6,k);
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
for(int i=0;i<65536;i++){
int cnt=0;
for(int j=0;j<16;j++) if(i>>j&1) o[i][cnt++]=j;
pc[i]=cnt;
}
cin>>n>>q>>s;
for(int i=1,x;i<=n;i++){
cin>>x;
if(x) v[x].push_back(i);
else rt=i;
}
dfs(rt);
int m=(cnt+63)>>6;
for(int i=0;i<m;i++) f[i].resize(std::min(d[dfn[i<<6]]>>6,3*(i&-i))),g[i].resize(std::min(d[dfn[i<<6]],128));
for(int i=cnt-1;~i;i--){
tmp[d[dfn[i]]]=i;
if((i&63)==0){
int k=i>>6;
for(unsigned j=0;j<f[k].size();j++) f[k][j]=tmp[d[dfn[i]]-((j+1)<<6)]>>6;
for(unsigned j=0;j<g[k].size();j++) g[k][j]=dfn[tmp[d[dfn[i]]-j-1]];
}
}
for(int l=0;l<cnt;l+=64){
int r=std::min(l+63,cnt-1);
static int stk[100];
int tp=0;
stk[++tp]=r,t[r]=1;
for(int i=r-1;i>=l;i--){
t[i]=t[i+1]<<1|1;
while(tp&&d[dfn[i]]<=d[dfn[stk[tp]]]) t[i]^=1ull<<(stk[tp]-i),--tp;
stk[++tp]=i;
}
}
long long int ans=0;
int lans=0;
for(int i=1;i<=q;i++){
int x=(get()^lans)%n+1;
int k=(get()^lans)%(d[x]+1);
ans^=1ull*i*(lans=query(p[x],d[x]-k));
}
cout<<ans<<'\n';
return 0;
}
```