【题解】P2137 Gty的妹子树

ExplodingKonjac · 2021-09-11 10:40:23 · 题解

【原题链接】

解题思路

其实我是跟着平衡树的标签找到这里，然后写了一发块状链表。

好像题解区里唯一一个块状链表题解和我的思路也不太一样。

首先这题需要维护子树操作，所以需要使用 dfs 序转化为序列问题，这样单点修改和子树查询都可以用（树套树？）维护。

考虑一下给节点 u 添加一个儿子后 dfs 序会变成什么样。假设我们对于每个节点用两个位置 lb_u,\ rb_u 来记录其在 dfs 序中的区间左右端点，那么我们就是在 lb_u 的后面（当然也可以是 rb_u 的前面）插入一对新的 lb_v,\ rb_v。

既然有了插入操作，你可以选择写平衡树套线段树，并且毫无疑问地爆时间爆空间。

但是我们有一个很优秀的支持插入的数据结构——块状链表。

插入操作不再赘述。对于每一个块，维护其本身代表的序列 a，以及排序后的序列 b。整块查询时，可以用 \text{upper\_bound} 在 b 中找到第一个大于 x 的位置 pos，该块的贡献就是 size-pos+1。

零散块就直接在 a 数组中暴力计算。

现在只剩下最后一个问题：由于 dfn 序列是不断变化的，我们怎么知道 lb_u,\ rb_u 的位置标号呢？嗯，分块当然可以直接维护，但是我选择了再用一棵 \text{Splay} 维护位置。

代码实现

#include <bits/stdc++.h>
using namespace std;

/*
  省略100多行的快读快写，即后面的qin、qout
  【广告】https://www.luogu.com.cn/blog/explodingkonjac/fast-io
*/

typedef long long LL;
int n,m,zt[60005],w[30005];
struct Edge{ int to,nxt; }e[60005];
int cnt,hd[30005];
inline void addEdge(int u,int v)
    { e[++cnt]=(Edge){v,hd[u]},hd[u]=cnt; }
void dfs(int u,int fa)
{
    zt[++cnt]=u;
    for(int i=hd[u];i;i=e[i].nxt)
        if(e[i].to!=fa)
            dfs(e[i].to,u);
    zt[++cnt]=-u;
}
struct SplayNode
{
    int siz;
    SplayNode *ch[2],*fa;
    SplayNode(): siz(1)
        { ch[0]=ch[1]=fa=nullptr; }
}*rt;
typedef SplayNode *pNode;
#define which(i) (i->fa->ch[1]==i)
inline void pushup(pNode i)
{
    i->siz=1;
    if(i->ch[0])    i->siz+=i->ch[0]->siz;
    if(i->ch[1])    i->siz+=i->ch[1]->siz;
}
inline void rotate(pNode i)
{
    pNode f=i->fa,gf=f->fa;
    bool x=which(i);
    i->fa=gf;
    if(gf)  gf->ch[which(f)]=i;
    f->ch[x]=i->ch[!x];
    if(f->ch[x])    f->ch[x]->fa=f;
    i->ch[!x]=f,f->fa=i;
    pushup(f),pushup(i);
}
inline void splay(pNode x,pNode y=nullptr)
{
    for(pNode f;(f=x->fa)!=y;rotate(x))
        if(f->fa!=y)
            rotate(which(f)==which(x)?f:x);
    if(!y)  rt=x;
}
pNode insert(int k)
{
    pNode i=rt,x;
    while(true)
    {
        int sz=i->ch[0]?i->ch[0]->siz:0;
        if(sz>=k)   i=i->ch[0];
        else
            if(!(k-=sz+1))
            {
                x=new SplayNode,x->ch[1]=i->ch[1],x->fa=i;
                if(i->ch[1])    i->ch[1]->fa=x;
                return i->ch[1]=x,pushup(x),splay(x),x;
            }
            else    i=i->ch[1];
    }
}
int getRank(pNode i)
    { return splay(i),(i->ch[0]?i->ch[0]->siz:0)+1; }
pNode lb[60005],rb[60005];
void build1(int l,int r,pNode &i=rt,pNode f=nullptr)
{
    if(l<=r)
    {
        i=new SplayNode,i->fa=f;
        int mid=(l+r)>>1;
        (zt[mid]>0?lb[zt[mid]]:rb[-zt[mid]])=i;
        build1(l,mid-1,i->ch[0],i);
        build1(mid+1,r,i->ch[1],i);
        pushup(i);
    }
}
int SIZE;
struct Block
{
    int cnt,*a,*b;
    Block *nxt;
    Block(): cnt(0),nxt(nullptr)
        { a=new int[SIZE+5],b=new int[SIZE+5]; }
    inline bool full()
        { return cnt==SIZE; }
    inline void update()
        { memcpy(b+1,a+1,cnt*4),sort(b+1,b+cnt+1); }
}*head;
void build2(Block *&i,int j=1)
{
    i=new Block;
    for(;j<=2*n && !i->full();j++)
        i->a[++i->cnt]=zt[j]>0?w[zt[j]]:-1;
    i->update();
    if(j<=2*n)  build2(i->nxt,j);
}
Block *find(int &x)
{
    Block *i=head;
    for(;i->cnt<x;x-=i->cnt,i=i->nxt);
    return i;
}
void insert(int p,int x)
{
    Block *i=find(p),*j;
    if(i->full())
    {
        j=i->nxt;
        if(!j || j->full())
            i->nxt=new Block,i->nxt->nxt=j,j=i->nxt;
        for(int k=++j->cnt;k>1;k--) j->a[k]=j->a[k-1];
        j->a[1]=(p==SIZE)?x:i->a[SIZE];
        j->update();
    }
    else    i->cnt++;
    for(int k=i->cnt;k>p+1;k--) i->a[k]=i->a[k-1];
    i->a[p+1]=x,i->update();
}
int main()
{
    qin>>n,SIZE=sqrt(n);
    int x,y,ans=0;
    for(int i=1;i<n;i++)    qin>>x>>y,addEdge(x,y),addEdge(y,x);
    for(int i=1;i<=n;i++)   qin>>w[i];
    cnt=0,dfs(1,0),build1(1,2*n),build2(head);
    qin>>m;
    while(m--)
    {
        int opt,l,r;
        Block *i,*j;
        qin>>opt>>x>>y,x^=ans,y^=ans;
        if(opt==0)
        {
            ans=0;
            l=getRank(lb[x]),r=getRank(rb[x]),i=find(l),j=find(r);
            if(i==j)
                for(int k=l;k<=r;k++)   ans+=(i->a[k]>y);
            else
            {
                for(int k=l;k<=i->cnt;k++)  ans+=(i->a[k]>y);
                while((i=i->nxt)!=j)
                    ans+=i->cnt-(upper_bound(i->b+1,i->b+i->cnt+1,y)-i->b)+1;
                for(int k=1;k<=r;k++)   ans+=(j->a[k]>y);
            }
            qout.writeln(ans);
        }
        else if(opt==1)
        {
            l=getRank(lb[x]),i=find(l);
            i->a[l]=y,i->update();
        }
        else
        {
            l=getRank(lb[x]),++n;
            insert(l,-1),rb[n]=insert(l);
            insert(l,y),lb[n]=insert(l);
        }
    }
    return qout.flush(),0;
}