省选前校内集训部分题目题解

被宏题和兔题吊着打。

2021.2.22~2021.2.25

因为有事没来学校，故没有做这几天的比赛。

2021.2.26

Nomura2020D Urban Planning

简要题意

有一个 $n$ 个点的无向图，每个点 $i$ 喜欢另一个点 $p_i$，这意味着最终它们得在同一个连通分量内。一开始这张图没有边，确定了 $p_i$ 后，你需要添加尽量少的边，以满足所有点的条件。某些点的 $p_i$ 为 $-1$，这意味着它还不确定喜欢哪个点，那你要帮它确定。假设 $p_i$ 为 $-1$ 的点有 $k$ 个，也就是有 $(n - 1)^k$ 种选取方案，你需要对每种方案都计算出添加的尽量少的边数。输出方案对应的所答案之和对 $10^9 + 7$ 取模。

$2\le n\le 5000$，$-1\le p_i\le n$，$\forall 1\le i\le n,p_i\ne i$。

题解

我们对于 $p_i\ne -1$ 的 $i$ 连一条从 $i$ 到 $p_i$ 的有向边，显然会形成一个内向基环树森林

Code

#include <bits/stdc++.h>
#define il inline
#define ll long long
const int N=5005,P=1e9+7; 
 
int n,m,s,ans,p[N],sz[N],f[N][N],to[N+N],nx[N+N],hd[N],sze; bool o[N];
 
il int ksm(int a,int b){int res=1; for ( ; b; b>>=1,a=(ll)a*a%P) if (b&1) res=(ll)res*a%P; return res;}
 
il void add(int u,int v){to[++sze]=v,nx[sze]=hd[u],hd[u]=sze;}
 
il void dfs(int u,int c)
{
    o[u]=1; if (c<0) sz[-c]++; int i,v;
    for (i=hd[u]; i; i=nx[i])
	if ((v=to[i])!=c) dfs(v,c);
	else s++;
}
 
int main()
{
    scanf("%d",&n); int i,j;
    for (i=1; i<=n; i++) scanf("%d",p+i),~p[i]&&(add(p[i],i),0);
    
    for (i=1; i<=n; i++) if (p[i]<0) m++,dfs(i,-m);
	for (i=1; i<=n; i++) if (!o[i]) dfs(i,i);
	ans=(ll)s*ksm(n-1,m)%P;
    for (i=0; i<=m; i++) for (f[i][0]=j=1; j<=i; j++) f[i][j]=(f[i-1][j]+(ll)f[i-1][j-1]*sz[i])%P;
    if (m) ans=(ans+(ll)(f[m][1]-m)*ksm(n-1,m-1))%P;
    for (j=1,i=2; i<=m; i++) j=(ll)j*(i-1)%P,ans=(ans+(ll)f[m][i]*j%P*ksm(n-1,m-i))%P;
    printf("%d\n",((ll)n*ksm(n-1,m)-ans+P)%P);
 
    return 0;
}

CF1479D Odd Mineral Resource

简要题意

给定一棵 $n$ 个点的树，第 $i$ 个点的颜色是 $a_i$。有 $q$ 询问，每次给定 $u,v,l,r$，求在从 $u$ 到 $v$ 的简单路径上，在 $[l,r]$ 范围内的颜色有没有出现奇数次的。若有，输出任意一个；否则输出 $-1$。

$1\le n,q\le 3\times 10^5$，$1\le a_i\le n$。

题解

这道题和这篇博客中的 D2T2 非常相似。

套路性的，我们对每一个点建一棵线段树，维护它到根路径上的颜色情况，其实相当与建一课主席树。而对于 $u$ 到 $v$ 路径，考虑树上差分，在四棵线段树上一起查即可。

现在我们考虑要维护什么信息，才能查。我们显然要维护一个二进制数 $S$，对于一个路径上的，把四个数按位异或一下就可以了。可是如果直接暴力用二进制数，1<<100000 会直接爆炸，而如果用 bitset 维护，会获得 MLE 的好成绩。

于是我们自然联想到了哈希，但是 CF 的卡哈希文化又让人望而却步。接下来我们用一种骚操作，我们给每种颜色随机随机赋一个不为 $0$ 的权值 $val_c$，每加上了这种颜色 $c$ 一次，就将 $S$ 异或上 $val_c$，这样子一个颜色出现了奇数次，就会留下 $val_c$；出现了偶数次，就会留下 $0$。所以如果一个路径对应的 $S$ 为 $0$，则说明这条路径上的颜色都出现了偶数次，之后就在线段树上二分找到第一个前缀和非 $0$ 的位置即可。

接着再说一下正确概率，如果有两个颜色的 $val_c$ 相同，就会出错，所以正确概率为：

$\begin{aligned} Pr\left[\bigwedge_{i=1}^{q}val_i\right]&=1-Pr\left[\bigvee_{i=1}^{q}\overline{val}_i\right]\\ &\ge 1-\sum_{i=1}^{q}Pr[\overline{val}_i]\\ &=1-\sum_{i=1}^{q}(1-Pr[val_i])\\ &\ge 1-\sum_{i=1}^{q}(1-(1-2^{-64}))\\ &=1-2^{-64}q \end{aligned}$

$q$ 大概是 $2^{18}$ 级别的，所以正确概率不小于 $1-2^{-64}q\ge 1-2^{-46}\approx 1$，所以正确性是可以保证的，除非你太非了/kk。

时间复杂度为 $O((n+q)\log n)$，空间复杂度为 $O(n\log n)$。

本题还有莫队的做法，但是在各方面都被以上做法暴打，故不讲。

Code

#include <bits/stdc++.h>
#define il inline
#define ull unsigned long long
std::mt19937 rd(233);
const int N=6e5+5,M=20*N;

int n,q,tot,a[N],rt[N],ls[M],rs[M]; ull b[N],t[M];
int dep[N],top[N],fa[N],sz[N],son[N],to[N],nx[N],hd[N],sze;

namespace IO
{
    const int S=1<<20|500; char iuf[S+5],*s,*t,ouf[S+5],*o; int p[40],P;
    il char gc(){if (t==s){t=(s=iuf)+fread(iuf,1,1<<20,stdin); if (t==s) return EOF;} return *s++;}
    template<class T=int>il T read()
    {
	T x; char c;
	while ((c=gc())<48||c>57); x=c^48;
	while ((c=gc())>47&&c<58) x=(x<<3)+(x<<1)+(c^48);
	return x;
    }
    il void fs(){if (o-ouf) fwrite(ouf,1,o-ouf,stdout); o=ouf;} il void pc(char c){*o++=c; if (o-ouf==S) fs();}
    template<class T=int>il void print(T x){T y; if (x<0) pc('-'),x=-x; do y=x/10,p[P++]=x-10*y;while (x=y); while (P) pc(p[--P]^48);}
    struct fsr{fsr(){o=ouf;} ~fsr(){fs();}}FF;
}
using IO::read; using IO::print; using IO::pc;

il void add(int u,int v){to[++sze]=v,nx[sze]=hd[u],hd[u]=sze;}

il int LCA(int x,int y)
{
    for ( ; top[x]!=top[y]; x=fa[top[x]]) if (dep[top[x]]<dep[top[y]]) std::swap(x,y);
    return dep[x]<dep[y]?x:y;
}

il void upt(int &p,int q,int l,int r,int x,ull v)
{
    t[p=++tot]=t[q]^v; if (l==r) return; int mid=l+r>>1;
    if (x<=mid) rs[p]=rs[q],upt(ls[p],ls[q],l,mid,x,v);
    else ls[p]=ls[q],upt(rs[p],rs[q],mid+1,r,x,v);
}

il int find(int a,int b,int c,int d,int l,int r,int x,int y)
{
    if (!(t[a]^t[b]^t[c]^t[d])) return -1; if (l==r) return l; int mid=l+r>>1,res=-1;
    if (x<=mid){if ((res=find(ls[a],ls[b],ls[c],ls[d],l,mid,x,y))!=-1) return res;}
    if (y>mid){if ((res=find(rs[a],rs[b],rs[c],rs[d],mid+1,r,x,y))!=-1) return res;}
    return -1;
}

il void dfs1(int u,int p)
{
    fa[u]=p,dep[u]=dep[p]+1,sz[u]=1,
    upt(rt[u],rt[p],1,n,a[u],b[a[u]]); int i,v;
    for (i=hd[u]; i; i=nx[i]) if ((v=to[i])!=p)
    {
        dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[son[u]]) son[u]=v;
    }
}

il void dfs2(int u,int t)
{
    top[u]=t; int i,v;
    if (son[u]) dfs2(son[u],t);
    for (i=hd[u]; i; i=nx[i]) if (!top[v=to[i]]) dfs2(v,v);
}

int main()
{
    n=read(),q=read(); int i,j,u,v,w;
    for (i=1; i<=n; i++) a[i]=read(),b[i]=rd();
    for (i=1; i<n; i++) u=read(),v=read(),add(u,v),add(v,u);
    dfs1(1,0),dfs2(1,1);
	
    while (q--)
	u=read(),v=read(),i=read(),j=read(),w=LCA(u,v),
	print(find(rt[u],rt[v],rt[w],rt[fa[w]],1,n,i,j)),pc('\n');
	
    return 0;
} 

---

2021.3.1

CF1411G No Game No Life

简要题意

有一张 $n$ 个点 $m$ 条边的 DAG。

加下来每一轮会发生如下事情：

1. 在 $[1,n+1]$ 范围内随机一个整数 $x$；
2. 若 $x\ne n+1$，则在第 $x$ 上放一个棋子；
3. 若 $x=n+1$，则两个绝对聪明的人开始在这张 DAG 上玩游戏，游戏规则如下：
   • 两个人轮流操作，每次操作要将一个点上的一个棋子沿着有向边放到另一个点上；
   • 无法操作的人败北。

玩完一遍游戏后不会再进行下一次随机了。

求先手获胜的概率，结果对 $998244353$ 取模。

$1\le n,m\le 10^5$。

题解

根据 $SG$ 函数的定义，我们显然可以知道要搞出一个值为 $1$ 的 $SG$ 函数需要 $1$ 条边，搞出一个值为 $2$ 的 SG 函数需要 $1+2$ 条边，搞出一个值为 $3$ 的 $SG$ 函数需要 $1+2+3$ 条边，$\cdots$，搞出一个值为 $k$ 的 $SG$ 函数需要 $\dfrac{k(k+1)}2$ 条边。所以设 $SG$ 函数的最大值是 $X$，则 $X$ 是 $O(\sqrt{m})$ 的。所以我们可以花费 $O(n\sqrt{m})$ 的复杂度预处理出每个点的 $SG$ 函数。

现在问题变成了选出的点集的 $SG$ 函数的异或和为 $0$ 的概率。此问题我们考虑设 $f_i$ 为选出的点集的 $SG$ 函数的异或和为 $i$ 的概率，$g_i$ 为 $SG$ 函数等于 $i$ 的点数，对于所有 $i\ne 0$ 有：

$f_i=\dfrac{1}{n+1}\sum_{j=0}^X{f_jg_{i\,\mathrm{xor}\,j}}$

介于 $f$ 数组之间的“纠缠”关系，我们不考虑 DP 而考虑高消，但你发现少了一个方程，因为你漏了最显然的一个：

$\sum_{i=0}^X{f_i}=1$

这样就可以 $O(X^3)$ 高消直接做了。

时间复杂度为 $O((n+m)\sqrt{m})$，空间复杂度为 $O(\sqrt{m})$。

本题还有集合幂级数的神仙做法，本人太菜不会，故不讲。

Code

#include <bits/stdc++.h>
#define il inline
#define ll long long
const int N=1e5+5,M=512,P=998244353;

int n,m,sg[N],f[M][M+1],g[M],p[M],to[N+N],nx[N+N],hd[N],sze; bool o[N],O[M];

il int ksm(int a,int b){int res=1; for ( ; b; b>>=1,a=(ll)a*a%P) if (b&1) res=(ll)res*a%P; return res;}

il void add(int u,int v){to[++sze]=v,nx[sze]=hd[u],hd[u]=sze;}

il void dfs(int u)
{
    if (o[u]) return; int i;
    for (i=hd[u]; i; i=nx[i]) dfs(to[i]);
    for (memset(O,0,M),i=hd[u]; i; i=nx[i]) O[sg[to[i]]]=1;
    while (O[sg[u]]) sg[u]++; o[u]=1,g[sg[u]]++;
}

il void gauss()
{
    std::fill(f[0],f[0]+M+1,1); int i,j,k,l;
    for (i=0; i<M; i++) for (j=i+1; j<M; j++) if (f[j][i])
	for (l=(ll)f[j][i]*ksm(f[i][i],P-2)%P,k=i; k<=M; k++) f[j][k]=(f[j][k]-(ll)l*f[i][k]%P+P)%P;
    for (i=M-1; ~i; i--)
    {
        for (j=i+1; j<M; j++) f[i][M]=(f[i][M]-(ll)p[j]*f[i][j]%P+P)%P;
        p[i]=(ll)f[i][M]*ksm(f[i][i],P-2)%P;
    }
}

int main()
{
    scanf("%d%d",&n,&m); int i,j,k;
    while (m--) scanf("%d%d",&i,&j),add(i,j);
    for (i=1; i<=n; i++) dfs(i);
	
    for (k=ksm(n+1,P-2),i=1; i<M; i++) for (f[i][i]=1,j=0; j<M; j++) f[i][j]=(f[i][j]-(ll)k*g[i^j]%P+P)%P;
    gauss(),printf("%d\n",(1-p[0]+P)%P);
	
    return 0;
}

---

2021.3.2

ARC108E Random IS

简要题意

给定一个长度为 $n$ 的排列 $\{a_i\}$，定义一个排列是合法的当且仅当标记的数满足单调递增。每次等概率选择一个未标记过的且标记后序列合法的数标记，无法标记时结束，求期望的标记个数。答案对 $10^9+7$ 取模。

$1\le n\le 2000$，保证 $\{a_i\}$ 是一个 $1\sim n$ 的排列。

题解

我们设 $f_{l,r}$ 为如果 $l,r$ 都被标记了，那么区间 $[l,r]$ 中除了 $l$ 和 $r$ 期望被标记了多少个数。

我们设有 $k$ 个数分别为 $b_1,b_2,\cdots,b_k$ 满足 $\forall 1\le i\le k,a_l<b_i<a_r$，则有：

$f_{l,r}=\begin{cases} 0&k=0\\ \dfrac {\sum_{i=1}^k{f_{l,i}+f_{i,r}}}k+1&k\ne 0 \end{cases}$

暴力转移是 $O(n^3)$ 的，我们拿一个线段树或者树状数组维护 $\sum{f_{l,i}},\sum{f_{i,r}}$ 和满足 $a_l<a_i<a_r$ 的 $i$ 的数量即可。

时间复杂度为 $O(n^2\log n)$，空间复杂度为 $O(n^2)$。

Code

#include <bits/stdc++.h>
#define il inline
#define ll long long
const int N=2005,P=1e9+7;

int n,a[N],I[N],f[N][N],A[N],B[N],C[N][N];

il void upt(int *o,int x,int v){for ( ; x<n+2; x+=x&-x) o[x]=(o[x]+v)%P;}

il int sum(int *o,int x){int res=0; for ( ; x; x-=x&-x) res=(res+o[x])%P; return res;}

il int query(int *o,int x,int y){return (sum(o,y)-sum(o,x)+P)%P;}

int main()
{
    scanf("%d",&n),a[n+1]=n+1; int i,j,k;
    for (i=1; i<=n; i++) scanf("%d",a+i);
    for (I[1]=1,i=2; i<=n; i++) I[i]=(ll)(P-P/i)*I[P%i]%P;
	
    for (j=1; j<n+2; j++) for (memset(A,0,4*n+8),memset(B,0,4*n+8),i=j-1; ~i; i--)
    {
        if (a[i]<a[j])
        {
            f[i][j]=((ll)f[i][j]+query(B,a[i],a[j])+query(C[i],a[i],a[j]))%P;
            if (k=query(A,a[i],a[j])) f[i][j]=((ll)f[i][j]*I[k]+1)%P;
        }
        upt(C[i],a[j],f[i][j]); if (i) upt(A,a[i],1),upt(B,a[i],f[i][j]);
    }
		
    printf("%d\n",f[0][n+1]);
	
    return 0;
}

---

2021.3.3

Tokiomarine2020E O(rand)

简要题意

给定 $n$ 个数 $a_1,a_2,\cdots,a_n$，求在其中选出不超过 $k$ 个数的方案，使得它们的按位与和为 $S$，按位或和为 $T$。

$1\le k\le n\le 50$，$0\le A_i,S,T<2^{18}$，$a_i\ne a_j(i\ne j)$。

题解

题目名称让人感觉是个乱搞题，事实上确实可以过，但是有一个非常靠谱的做法。

我们将 $S$ 和 $T$ 二进制表示，$S=\left(\overline{S_{17}S_{16}\cdots S_1S_0}\right)_2$，$S=\left(\overline{T_{17}T_{16}\cdots T_1T_0}\right)_2$

如果 $S_i=1.T_i=0$，则直接无解；如果 $S_i=T_i=1$，则那些对应的二进制位为 $0$ 的都不合法；如果 $S_i=T_i=0$，则那些对应的二进制位为 $1$ 的都不合法；如果 $S_i=0,T_i=1$，则对应的二进制位为 $0$ 的至少选一个，对应的二进制位为 $1$ 的也至少选一个。

前三类的都很蠢，对于第四类我们考虑容斥。考虑对应位置只选了 $1$ 或者 $0$ 的，对应的二进制数为 $R$，则就是选出 $1\sim k$ 个在这些：$a_1\ \mathrm{and}\ a_2\ \mathrm{and}\cdots\mathrm{and}\ a_n\ \mathrm{and}\ R$ 位置上相等的的数的方案数。

时间复杂度为 $O(2^{18}n^2)$，空间复杂度为 $O(n+\log)$。

Code

#include <bits/stdc++.h>
#define int long long
const int N=55,K=18;
 
int n,s,A,B,ans,m,a[N],b[N],f[N][N],C[N][N]; bool o[N],O[K];
 
signed main()
{
    scanf("%lld%lld%ld%lld",&n,&s,&A,&B); int i,j,k,S,T,p,q;
    for (i=1; i<=n; i++) scanf("%lld",a+i);
    for (i=0; i<=n; i++) for (C[i][0]=j=1; j<=i; j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
	
    for (k=0; k<K; k++)
    {
        if (A>>k&1){for (i=1; i<=n; i++) if (a[i]>>k&1^1) o[i]=1; O[k]=1;}
        if (B>>k&1^1){for (i=1; i<=n; i++) if (a[i]>>k&1) o[i]=1; O[k]=1;} 
    }
    for (i=1; i<=n; i++) if (!o[i]) b[++m]=a[i]; if (!m) return puts("0"),0;
    for (i=1; i<=m; i++) for (j=i+1; j<=m; f[i][j]=T,j++)
	for (T=k=0; k<K; k++) if ((b[i]>>k&1)==(b[j]>>k&1)) T|=1<<k;
	
    for (i=1; i<=m; i++) for (S=0; S<1<<K; S++)
    {
        for (k=q=p=0; !q&&k<K; k++) q=(S>>k&1)&&O[k]; if (q) continue;
        for (j=i+1; j<=m; j++) if ((f[i][j]&S)==S) p++;
        q=__builtin_popcount(S)&1?-1:1;
        for (j=0; j<s; j++) ans+=q*C[p][j];
    }
    printf("%lld\n",ans);
	
    return 0;
}

---

2021.3.4

APC001F XOR Tree

简要题解

给定一棵 $n$ 个点的树，第 $i$ 条边连接 $x_i,y_i$，边权为 $a_i$。

每次操作选择一条简单路径和一个非负整数 $x$，然后把这条路径上的所有边的边权都异或上 $x$。

求把所有边的权值都变为 $0$ 的最小操作次数。

$2\le n\le 10^5$，$0\le a_i\le 15$。

题解

时间复杂度为 $O(n+2^mm)$，空间复杂度为 $O(n+2^m)$。

Code

#include <bits/stdc++.h>
#define il inline
const int N=2e5+5,M=1<<16;

int n,m,s,a[N],b[16],f[M];

il int dfs(int S)
{
    if (~f[S]) return f[S]; if (S<1) return f[S]=0; int i,j,k;
    for (f[S]=1e9,i=1; i<16; i++) if (S>>i&1)
	for (j=1; j<16; j++) if (j!=i&&S>>j&1)
	    k=i^j,f[S]=std::min(f[S],dfs(S^1<<i^1<<j^1<<k)+1+(S>>k&1));
    return f[S];
}

int main()
{
    scanf("%d",&n),memset(f,-1,sizeof f); int i,u,v,w;
    for (i=1; i<n; i++) scanf("%d%d%d",&u,&v,&w),a[u+1]^=w,a[v+1]^=w;
    for (i=1; i<=n; i++) b[a[i]]++;
	
    for (i=1; i<16; i++) s+=b[i]/2,b[i]&1&&(m+=1<<i);
    printf("%d\n",s+dfs(m));
	
    return 0;
}

Diverta2019 Edge Ordering

这个题我是暴力水过的，正解完全不会。咕咕咕。

---

2021.3.5

CF1494F Delete The Edges

简要题意

给定一个 $n$ 个点 $m$ 条边的无向图，保证没有重边与自环。你的目的是要摧毁所有的边，如果你走过一条没有被摧毁的边，则你走过去后，这条边被摧毁。

你有两种模式可以使用：

1. 你只能走没有被摧毁的边；
2. 你开启这个模式后，你必须在第一步走没有被摧毁的边，第二步走被摧毁的边，第三步走被没有摧毁的边，第四步走被摧毁的边 $\cdots$

你可以选定起点，并且一开始你使用的是模式 $1$，且你最多只能使用一次转换模式的操作。判断你是否可以摧毁所有的边，如果可以，输出方案；否则给出无解。

$2\le n\le 3000$，$n-1\le m\le \min\left(\frac{n(n-1)}2,3000\right)$。

题解

你手玩若干数据，发现最后的方案都是形如：$\texttt{欧拉路径}+\ -1\ +\texttt{菊花}$。那怎么证明呢？

于是我们枚举菊花中心，暴力把周围的奇点断掉，跑一遍欧拉回路；又因为除了菊花中心最多只能有一个奇点，于是我们再暴力连上其中的一条边，每次都跑一遍欧拉回路。时间复杂度为 $O((n+m)^2)$，空间复杂度为 $O(n+m)$。

听说有神仙线性做法，但是出题人说难以实现，而且我也不会，故不讲。

Code

#include <bits/stdc++.h>
#define il inline
const int N=6005;

int n,m,s,tp,p[N],st[N]; bool o[N],c[N];
int to[N],nx[N],hd[N],it[N],du[N],d[N],sze=1;

il void add(int u,int v){to[++sze]=v,nx[sze]=hd[u],hd[u]=sze,du[v]++;}

il void dfs(int u){for (int i=it[u]; i; i=it[u]) if (it[u]=nx[i],!o[i>>1]&&!c[i>>1]) o[i>>1]=1,dfs(to[i]); st[++tp]=u;}

il bool ck(int u)
{
    int i,j,x=0; for (i=1; i<=n; i++) x+=d[i]&1; if (x>2) return 0;
    memset(o,0,m+1),tp=0,memcpy(it,hd,4*n+4),tp=0;
    if (!x)
    {
        dfs(u);
        for (i=1; i<=m; i++) if (!o[i]&&!c[i]) return 0;
        return 1;
    }
    if (d[u]&1^1) return 0;
    for (i=1; i<=n; i++) if (d[i]%2&&i!=u)
    {
        dfs(i);
        for (j=1; j<=m; j++) if (!o[j]&&!c[j]) return 0;
        return 1;
    }
    return 0;
}

il void print(int x,int y)
{
    int i; for (printf("%d\n",tp+(s?(y?s+s-1:s+s+1):0)),i=tp; i; i--) printf("%d ",st[i]);
    if (s){for (printf("-1 "),i=s; i; i--) if (p[i]!=y) printf("%d %d ",p[i],x);} exit(0);
}

int main()
{
    scanf("%d%d",&n,&m); int i,u,v;
    for (i=1; i<=m; i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
    
    for (u=1; u<=n; u++)
    {
        s=0,memcpy(d,du,4*n+4),memset(c,0,m+1);
        if (ck(u)) print(u,0);
        for (i=hd[u]; i; i=nx[i]) if (d[v=to[i]]&1)
            c[i>>1]=1,d[u]--,d[v]--,p[++s]=v;
        if (ck(u)) print(u,0);
        for (i=hd[u]; i; i=nx[i]) if (c[i>>1])
        {
            c[i>>1]=0,d[u]++,d[v=to[i]]++;
            if (ck(u)) print(u,v);
            c[i>>1]=1,d[u]--,d[v]--;
        }
    }
    puts("0");
	
    return 0;
}

CF1491H Yuezheng Ling and Dynamic Tree

简要题意

给一颗 $n$ 点的树，其中第 $i(2\le i\le n)$ 个点的父亲是 $a_i$，你需要支持以下两种操作：

1. 给定 $l,r,x$，对于每个 $i\in [l,r]$，$a_i\gets \max(a_i-x,1)$；
2. 给定 $x,y$，询问 $x$ 和 $y$ 的 $LCA$。

$2\le n,q\le 10^5$，$\forall 2\le i\le n,1\le a_i<i$。

题解

首先我们有关键信息 $a_i<i$，我们发现传统的 $\log$ 数据结构没办法搞。于是我们考虑分块。

我们考虑怎么像树剖那样跳 $LCA$，考虑维护 $f_x$ 表示满足它是 $x$ 的祖先，并且它和 $x$ 在同一个块中，但是 $a_{f_x}$ 并不在一个块中。

那么这个 $f_x$ 和树剖中的 $top_x$ 是一个作用，我们像树剖跳 $top_x$ 那样跳 $f_x$，就可以 $O(\sqrt{n})$ 查询两个点的 LCA。

我们考虑修改，我们套路性的给整块打上标记，而对于散块暴力修改。但是我们还需要解决如何重构 $f_x$ 的问题，你发现一个块如果被修改了超过块长次的话，那么就不用改了，因为 $f_x$ 就等于 $x$ 了。于是均摊下来就是对的了。

时间复杂度为 $O((n+q)\sqrt{n})$，空间复杂度为 $O(n)$。

Code

#include <bits/stdc++.h>
#define il inline
#define ll long long
const int N=2e5+5,B=316;

int n,q,b[N],c[N]; ll a[N],lz[N];

il int jump(int x){return x?std::max(a[x]-lz[x/B],0ll):-1;}

il void rebuild(int x,int v)
{
    if (c[x]+v>B) return ; c[x]+=v; int i;
    for (i=x*B; i<x*B+B; i++) b[i]=jump(i)<x*B?i:b[jump(i)];
}

il void add(int x,int y,int v)
{
    int i; for (i=x/B*B; i<x; i++) a[i]+=v;
    for (i=y+1; i<y/B*B+B; i++) a[i]+=v;
    for (i=x/B; i<=y/B; i++) lz[i]+=v,rebuild(i,i!=x/B&&i!=y/B);
}

il int LCA(int x,int y)
{
    for ( ; b[x]!=b[y]; x=jump(b[x])) if (jump(b[x])<jump(b[y])) std::swap(x,y);
    for ( ; x!=y; x=jump(x)) if (x<y) std::swap(x,y); return x;
}

int main()
{
    scanf("%d%d",&n,&q),a[0]=-1; int i,x,y,k;
    for (i=1; i<n; i++) scanf("%d",a+i),a[i]--;
	
    for (add(0,n-1,0); q; q--)
	if (scanf("%d%d%d",&i,&x,&y),i>1) printf("%d\n",LCA(x-1,y-1)+1);
	else scanf("%d",&k),add(x-1,y-1,k);
	
    return 0;
}