题解 P2137 【Gty的妹子树】

Mr_Spade · 2018-07-10 20:54:32 · 题解

为什么这道题没有题解啊，那不如我来贡献一发吧。

做完之后去网上搜了一下其它做法，发现居然要树分块，这不是超麻烦的吗。所以我们可以考虑另一种分块方法：对时间分块。

对时间分治是需要离线的，但是对时间分块是可以在线的。

我们先可以考虑静态的情况，如果这道题是静态的询问，那么我们只要根据dfs序列建一棵归并树(线段树的一种，每个节点保存这个区间的权值排序过以后的序列)，再进行区间查询就可以了。

那么如果在查询之前进行过若干次修改的话，我们可以暴力扫描一遍这些修改，对查询的答案计算贡献。分两种修改讨论：

如果是修改点权，我们只要先查询这个点是否在被查询的点的子树内，再查询它的修改对答案是否有影响就可以了。

如果是添加一个点，也是类似的，查询是否在这棵子树内以及是否对答案有影响即可。

那么如何查询一个点是否在被查询点的子树内呢？我们可以在添加点的时候预先进行倍增处理这个点向上跳2^i层的祖先，这样只要用倍增数组往上跳就可以查询了。

综合一下之前的讨论，如果我们在查询之前的修改不超过\sqrt m次时，就在归并树上查询后暴力扫描修改计算贡献；如果修改超过了\sqrt m次时，我们只要根据修改重建一下归并树就可以清除掉这些修改，可以发现归并树的重建不会超过\sqrt m次。

来分析一下复杂度，为了省事我们把n和m看成是同阶的，瓶颈显然在暴力扫描计算贡献和归并树的重建上，计算贡献时，最多扫描O(\sqrt n)次修改，每次需要O(\log n)的复杂度(倍增)，所以这部分的复杂度是O(n\sqrt n \log n)。而重建归并树每次是O(n\log n)的，一共O(\sqrt n)次，因此这部分的复杂度也是O(n\sqrt n \log n)。

因此复杂度是O(n\sqrt n \log n)，通过了这道题。

细节可以参考代码注释

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using std::upper_bound;
using std::merge;
using std::vector;
inline int read()
{
    int res=0;
    char x;
    while((x=getchar())<'0'||x>'9');
    for(;x>='0'&&x<='9';x=getchar())
        res=res*10+x-'0';
    return res;
}
inline void write(int x)
{
    if(x>=10)
        write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=1e5+5,LGN=25;
int n,m,unit,tot,idx,lastans;
int w[N],wi[N],id[N],deep[N],size[N];
int p[N][LGN];//倍增数组
int v[N<<1],first[N],next[N<<1];
struct cell
{
    int opt,u,x,y;
};
vector<cell> V;
struct node
{
    int l,r;
    vector<int> V;
}sgt[N<<2];
void build(int now,int l,int r)//构建归并树
{
    sgt[now].l=l;sgt[now].r=r;
    sgt[now].V.clear();
    if(l==r)
    {
        sgt[now].V.push_back(wi[l]);
        return;
    }
    int mid=(l+r)>>1;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    sgt[now].V.resize(r-l+1);
    merge(sgt[now<<1].V.begin(),sgt[now<<1].V.end(),sgt[now<<1|1].V.begin(),sgt[now<<1|1].V.end(),sgt[now].V.begin());
    return;
}
int query(int now,int l,int r,int k)//查询
{
    if(sgt[now].l>r||sgt[now].r<l)
        return 0;
    if(sgt[now].l>=l&&sgt[now].r<=r)
        return sgt[now].V.end()-upper_bound(sgt[now].V.begin(),sgt[now].V.end(),k);
    return query(now<<1,l,r,k)+query(now<<1|1,l,r,k);
}
inline void add_edge(int from,int to)
{
    tot+=2;
    v[tot+1]=from;v[tot]=to;
    next[tot]=first[from];first[from]=tot;
    next[tot+1]=first[to];first[to]=tot+1;
    return;
}
void dfs(int now,int father)//dfs，用于在重建归并树之前更新一些数据
{
    register int go;
    id[now]=++idx;size[now]=1;
    wi[id[now]]=w[now];/*这个是为了方便建归并树*/p[now][0]=father;
    for(go=first[now];go;go=next[go])
        if(v[go]!=father)
        {
            deep[v[go]]=deep[now]+1;
            dfs(v[go],now);
            size[now]+=size[v[go]];
        }
    return;
}
inline bool anc(int u,int v)//查询v是否在u的子树内
{
    int res=v;
    register int i;
    if(deep[v]<deep[u])
        return 0;
    for(i=20;~i;i--)
        if((deep[v]-deep[u])>>i&1)
            res=p[res][i];
    return res==u;
}
inline void rebuild()//更新并重建
{
    V.clear();
    idx=0;dfs(1,0);
    build(1,1,n);
    return;
}
signed main()
{
    int from,to;
    int u,x,res;
    register int i,j;
    n=read();
    for(i=1;i<=n-1;i++)
    {
        from=read();to=read();
        add_edge(from,to);
    }
    for(i=1;i<=n;i++)
        w[i]=read();
    idx=0;dfs(1,0);
    for(i=1;i<=n;i++)
        for(j=1;j<=20;j++)
            p[i][j]=p[p[i][j-1]][j-1];
    build(1,1,n);
    m=read();unit=ceil(sqrt(m)*5);//块大小
    while(m--)
        switch(read())
        {
            case 0:
                u=read()^lastans;x=read()^lastans;
                res=query(1,id[u],id[u]+size[u]-1,x);
                for(i=0;i<(int)V.size();i++)
                    if(V[i].opt==1)
                    {
                        if(((V[i].x>x)^(V[i].y>x))&&anc(u,V[i].u))
                            res+=(V[i].y>x)?1:-1;
                    }
                    else
                    {
                        if((V[i].y>x)&&anc(u,V[i].u))
                            res++;
                    }
                write(lastans=res);putchar('\n');
                break;
            case 1:
                u=read()^lastans;x=read()^lastans;
                V.push_back(cell{1,u,w[u],x});w[u]=x;
                if((int)V.size()>=unit)
                    rebuild();
                break;
            case 2:
                u=read()^lastans;x=read()^lastans;
                V.push_back(cell{2,n+1,u,x});
                add_edge(u,++n);
                w[n]=x;deep[n]=deep[u]+1;
                p[n][0]=u;
                for(i=1;i<=20;i++)
                    p[n][i]=p[p[n][i-1]][i-1];
                if((int)V.size()>=unit)
                    rebuild();
                break;
        }
    return 0;
}