题解 P2137 【Gty的妹子树】

· · 题解

翻了一下题解区发现好像没有块状链表的题解...那我就写一发吧。

记分块大小为 T ，不妨令 n,m 同级，此算法的时间复杂度为

在 T 取 \sqrt{n\log_2n} 时有最优时间复杂度 O(n(\sqrt{n\log_2n}+\log^2n)) 。

空间复杂度为 O(n\log_2n)。

接下来进入正题。

块状链表

块状链表，通俗地说，就是一种结合了分块和链表两种数据结构优势的数据结构。

它可以做到 O(\sqrt{n}) 在任意位置 插入/删除 元素、O(\sqrt{n}) （或者 O(1)） 定位一个元素、以及维护当前序列上的一些东西。

链表结构（本题）

int pii::p 值域为 [1,...,sz] ，表示块内的 dfs 序。

int pii::v p 对应的节点的权值。

int pii::Id p 对应的节点在原树上的标号。

pii v[][] 用来存储每个块的信息。（不要跟上文的 v 弄混！）

int sz[] 每个块的 size 。

int Nx[] 表示某一个块在 dfs 序上的后继，为0表示是最后一个块。

int Las[] 记录一个块内 dfn 最大的节点。

int bel[] 记录一个树上的节点所属的块标号。

对于这道题而言，我们可以随时保证块中所有 pii 的权值 v 单调递增，方法参见下文。

void split(x)（核心操作）

目的：将块 x 分裂成两块。

开一个新块，记其为 New ，然后修改 Nx[New]=Nx[x],Nx[x]=New。

记 mid=sz[x]/2 。

将 v[x][i] 中 p 值大于 mid 的减去 mid ，并分到新块中。

重计算受影响的 sz[] 、 Las[] 和 bel[] 。

由于原本 v[x][i] 的权值就单调递增，分裂为两个子序列，均匀分配给两个块之后也一定满足单调性。

void split(int x)
{
    Nx[++total]=Nx[x],Nx[x]=total;
    int spl=sz[x]>>1;
    Las[total]=Las[x];
    register int i,p=0;
    for(i=1;i<=sz[x];i++)
    {
        pii t=v[x][i];
        if(t.p==spl)Las[x]=t.Id;
        if(t.p>spl)t.p-=spl,v[total][++sz[total]]=t,bel[t.Id]=total;
        else v[x][++p]=t;
    }sz[x]=p;
}

回到这题上，我们发现我们的每个询问是在树的dfs序上，因此就比较适合用块状链表维护。

  1. 如何处理询问？

我们随时保证每个块内的结构体的权值单调递增，这样询问一个整块时就可以在 O(\log_2n) 使用 二分/upper_bound 求出解。

显而易见的是，通过 bel 数组，我们能快速定位询问的左端点（因为询问的区间左端点就是询问点所在位置）。

我们发现，我们接下来能通过判断一个块的 Las 是否在询问点的子树内，来 O(\frac{n}{T}\log_2n) 求出询问区间的右端点在哪个块上。

由于新建一个节点，不会影响其他点的 fa ，所以可以倍增维护每个点的 2^k 级 fa 从而在 O(\log_2n) 时间内判断一个点是否在另一个点的子树中。

对于两侧的散块，直接暴力计算贡献是 O(T\log_2n)的，复杂度将退化到 O((\frac{n}{T}+T)\log_2n) = O(\sqrt{n}\log_2n)。

考虑优化这个算法。

我们发现，散块中在询问点子树内的点一定在 dfs 序上是连续的一段，并且你已经知道了这些散块在询问点子树内的点的左端点。（如果询问左端点和右端点在同一个块内，那么左端点就是询问的左端点，否则左端点显然是 dfs 序最小的节点）

因此，我们就可以进行令人感到愉悦的二分。

二分右端点，复杂度降到了 O(\log_2^2n) 。

此时，我们成功把询问复杂度优化到了 O(\frac{n}{T}\log_2n+T+\log^2n) ，最优为 O(\sqrt{n\log_2n}+\log^2n) 。

  1. 如何处理添加节点？

添加节点时，用同上的方法定位父节点所在块与其准确位置。

我们可以不妨假设添加的节点的 dfs 序成为了其父节点的 dfs 序 +1 。

这样相当于所有 dfs 序大于父节点的 dfs 序都增加 1。

我们不难发现，只有父节点所属块的一部分 p 受到了影响。

暴力更新这些 p ，然后插入新的节点，同时用插入排序的方式将块内的权值顺序更新。

另外，不要忘了求一下新插入节点的 fa 数组。

复杂度 O(T+\log_2n) 。

不要直接 sort ，不然复杂度会退化至 O(T\log_2n) 。

  1. 如何处理节点权值修改？

我们仍然可以定位这个节点，然后暴力修改。

修改之后，把这个点丢出来进行插入排序。

复杂度 O(T) 。

于是，我们在 O(n(\sqrt{n\log_2n}+\log^2n)) 的时间内通过了此题。

P.S. 如果复杂度证明不正确，可以私信我。

（此算法常数并不小，有时候还跑不过 O(n\sqrt{n}\log_2n) 的时间分块...）

以下是完整代码：

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
struct pii
{int p,v,Id;};
bool operator<(const pii x,const pii y)
{return x.v<y.v;}
pii v[2222][2222];
int sz[111111],Nx[111111],Las[111111];
int rank(pii x,int p)
{return v[p]+sz[p]+1-std::upper_bound(v[p]+1,v[p]+sz[p]+1,x);}  //二分整块
int n,m,blo=360,last=0,total=1;
std::vector<int>w[111111];
int g[111111],bel[111111];
void split(int x)  //分裂块 x 
{
    Nx[++total]=Nx[x],Nx[x]=total;
    int spl=sz[x]>>1;
    Las[total]=Las[x];
    register int i,p=0;
    for(i=1;i<=sz[x];i++)
    {
        pii t=v[x][i];
        if(t.p==spl)Las[x]=t.Id;
        if(t.p>spl)t.p-=spl,v[total][++sz[total]]=t,bel[t.Id]=total;
        else v[x][++p]=t;
    }sz[x]=p;
}
int dep[111111],fa[111111][22];
#define lowbit(x) (x&-x)
int rv[111111];
bool isin(int x,int y)  //判断 x 是否在 y 子树内
{
    register int i=dep[x]-dep[y];
    if(i<0)return 0;
    for(;i;i-=lowbit(i))x=fa[x][rv[lowbit(i)]];
    return x==y;
}
int rev(int x,int r,int p)  //暴力统计块 x 的答案 
{
    int L=0,D=1,R=sz[p]+1;
    register int i;
    for(i=1;i<R;i++)v[0][v[p][i].p]=v[p][i];
    for(i=1;i<R;i++)if(v[0][i].Id==r){D=L=i;break;}
    while(L+1<R)  //二分询问子树的右端点
    {
        int mid=(L+R)>>1;
        if(isin(v[0][mid].Id,r))L=mid;
        else R=mid;
    }int ret=0;
    for(i=D;i<R;i++)ret+=v[0][i].v>x;
    return ret;
}
int query(int p,int x)
{
    int ans=0,in=0;
    for(register int i=1;i;i=Nx[i])
    {
        if(bel[p]==i)in=1,ans+=rev(x,p,i);
        else if(in)
        {
            if(!isin(Las[i],p)){ans+=rev(x,p,i);break;}
            else ans+=rank(pii{0,x,0},i);
        }
    }return ans;
}
void insert(int f,int d)  //插入新的节点
{
    int vc=bel[f],cg=0;n++;
    pii verd=pii{0,d,n};
    register int i;
    fa[n][0]=f,dep[n]=dep[f]+1,bel[n]=vc;
    for(i=0;fa[n][i];i++)fa[n][i+1]=fa[fa[n][i]][i];
    for(i=1;i<=sz[vc];i++)if(v[vc][i].Id==f){i=v[vc][i].p+1;break;}
    verd.p=i;
    for(i=1;i<=sz[vc];i++)if(v[vc][i].p>=verd.p)v[vc][i].p++,cg=1;
    if(!cg)Las[vc]=n;
    for(i=1;i<=sz[vc];i++)
        if(v[vc][i].v>verd.v){pii gg=verd;verd=v[vc][i],v[vc][i]=gg;}
    v[vc][++sz[vc]]=verd;
    if(sz[vc]>blo*2)split(vc);
}
void modify(int x,int d)  //修改点权
{
    int vc=bel[x];
    register int i;
    for(i=1;i<=sz[vc];i++)
        if(v[vc][i].Id==x){v[vc][i].v=d;break;}
    pii tp;
    for(i=2;i<=sz[vc];i++)
        if(v[vc][i]<v[vc][i-1])
            tp=v[vc][i],v[vc][i]=v[vc][i-1],v[vc][i-1]=tp;
    for(i=sz[vc];i^1;i--)
        if(v[vc][i]<v[vc][i-1])
            tp=v[vc][i],v[vc][i]=v[vc][i-1],v[vc][i-1]=tp;
}
int ss=0;
void dfs(int p=1,int f=0)  //预处理初始树
{
    fa[p][0]=f,dep[p]=dep[f]+1,ss++;
    int GG=blo*1.9;
    if(ss>GG)ss-=GG,Nx[total]=total+1,total++;
    v[total][++sz[total]]=pii{ss,g[p],p},bel[p]=total;
    register int i;
    for(i=0;fa[p][i];i++)fa[p][i+1]=fa[fa[p][i]][i];
    for(auto t:w[p])if(t^f)dfs(t,p);
}
void precalc()
{
    dfs();
    for(register int i=1;i<=total;i++)
        Las[i]=v[i][sz[i]].Id,std::sort(v[i]+1,v[i]+sz[i]+1);
}
void solve()
{
    int o,u,x;
    scanf("%d%d%d",&o,&u,&x),u^=last,x^=last;
    if(o&1)modify(u,x);
    else if(o&2)insert(u,x);
    else printf("%d\n",last=query(u,x));
}
int main()
{
    register int i;
    for(i=0;i<=16;i++)rv[(1<<i)]=i;
    scanf("%d",&n);
    for(i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y),w[x].push_back(y),w[y].push_back(x);
    }for(i=1;i<=n;i++)scanf("%d",g+i);
    precalc(),scanf("%d",&m);
    for(i=1;i<=m;i++)solve();
}