HDU - 5390 tree （可持久化字典树+线段树）

题面：

题意：
给定一棵有根树，根节点为1，节点 $i$ 的权值为 $v i$ 。
有以下两种操作：
（1） 0 x y ---- 将节点 $x$ 的权值改为 $y$
（2） 1 x ---- 查询 $v_{x} <mtext> </mtext> x o r <mtext> </mtext> v_{t}$ 的最大值，其中 $t \in p a t h (x, r o o t)$

题解：
①、考虑不带修改
$v_{x}$ 是一个已知的定值，查询 $v_{x}$ 与一组值 $v_{t}$ 中的某个数的异或的最大值，用树上可持久化字典树即可处理。
空间复杂度 $O (n l o g n)$ ，时间复杂度 $O (n l o g n)$

②、考虑修改。
查询具有特殊性，每次查询的 $v_{t}$ 是根节点到 $x$ 点这一条链上的值。

修改是单点修改。那么修改一个点之后只会影响它的子树。

所以我们把修改单点的值，变为修改子树。
我们把修改分解为一次删除和一次增加。
即对于子树中所有的节点到根节点的路径上减去 $v_{x}$ 加上 $y$

我们考虑 $d f s$ 序上建立线段树，我们对于线段树的每个节点（线段树的一个节点对应一个区间）建立一棵字典树。假设我们当前要修改的区间为 $[l, r]$ ，在线段树上进行区间修改。假设当前要修改的区间 $[l, r]$ 覆盖了线段树上 $c n t$ 点所表示的区间，那么就在 $c n t$ 节点所在的字典树上插入元组 $(v a l, o p)$ ，其中 $v a l$ 表示此次修改的权值， $o p$ 表示是删除还是增加。表示该区间所有的节点到根节点的路径上的值均变化 $(v a l, o p)$ ，不再处理 $c n t$ 的子区间。

在区间修改时，我们标记不下传。

那么区间 $[l, r]$ 最多覆盖线段树上 $l o g n$ 个节点，每个节点的修改是 $l o g n$ 的，那么每修改一次的时间复杂度就是 $O (l o g^{2} n)$

考虑查询。

假设我们现在要查询的节点是 $x$ 节点，它对应线段树上的节点为 $c n t$ 。
我们考虑到某一位时，该位的真实贡献值应该为可持久化字典树上的贡献加上线段树上所有能覆盖 $c n t$ 的区间的贡献。我们知道，这样的区间至多有 $l o g n$ 个，每次查询每一位时我们都需要遍历这 $l o g n$ 个区间。

时间复杂度： $O (l o g^{2} n)$

那么总的时间复杂度就为 $O (n l o g^{2} n)$

现在来分析一下空间复杂度。
每个区间的修改数 $v a l$ 至多会分成 $l o g n$ 个区间的修改，每个修改需要 $l o g n$ 空间。那么空间复杂度为 $O (n l o g^{2} n)$

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int maxp=100100;
const int up=30;

int head[maxn],ver[maxn],nt[maxn],tot=1;
int st[maxn],ed[maxn],id[maxn],v[maxn],cm=0;
int root1[maxn],root2[maxn<<2];//root1[x] 树上节点x的根，root2[x] 线段树上节点x的根
int t[maxn*30*20][2],sum[maxn*30*20],cnt=0;//空间复杂度实际上应该是O(n logn logMAX)
int n,m;
int p[maxn];//查询时，记录线段树上覆盖当前点的区间

void init(void)
{
    tot=0,cnt=0,cm=0;
    memset(head,0,sizeof(head));
}

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

int newnode(void)
{
    ++cnt;
    t[cnt][0]=t[cnt][1]=sum[cnt]=0;
    return cnt;
}

void _insert(int pre,int now,int val)
{
    int c;
    for(int k=up;k>=0;k--)
    {
        c=(val>>k)&1;
        t[now][c^1]=t[pre][c^1];
        t[now][c]=newnode();
        sum[t[now][c]]=sum[t[pre][c]]+1;
        pre=t[pre][c],now=t[now][c];
    }
}


int ask(int rt,int cnt,int val)
{
    int ans=0,pp=0;
    while(cnt) p[++pp]=root2[cnt],cnt=(cnt>>1);

    int res=0;
    for(int k=up;k>=0;k--)
    {
        int c=(val>>k)&1;
        res=0;
        for(int i=1;i<=pp;i++)
        	res+=sum[t[p[i]][c^1]];
        if(sum[t[rt][c^1]]+res>0)
        {
            rt=t[rt][c^1];
            for(int i=1;i<=pp;i++)
            	p[i]=t[p[i]][c^1];
            ans+=(1<<k);
        }
        else
        {
        	rt=t[rt][c];
        	for(int i=1;i<=pp;i++)
            	p[i]=t[p[i]][c];
		}
    }
    return ans;
}

void dfs(int x,int fa)
{
	st[x]=++cm;
    root1[x]=newnode();
    _insert(root1[fa],root1[x],v[x]);
    for(int i=head[x];i;i=nt[i])
        dfs(ver[i],x);
    ed[x]=cm;
}

struct node
{
	int l,r;
}tr[maxn<<2];

void build(int l,int r,int cnt)
{
	tr[cnt].l=l,tr[cnt].r=r;
	root2[cnt]=newnode();
	if(l==r)
	{
		id[l]=cnt;
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,lc);
	build(mid+1,r,rc);
}

void in(int p,int val,int op)
{
	for(int k=up;k>=0;k--)
	{
		int c=(val>>k)&1;
		if(!t[p][c]) t[p][c]=newnode();
		p=t[p][c];
		sum[p]+=op;
	}
}

void change(int l,int r,int val,int op,int cnt)
{
	if(tr[cnt].l>=l&&tr[cnt].r<=r)
	{
		in(root2[cnt],val,op);
		return ;
	}
	if(tr[cnt<<1].r>=l) change(l,r,val,op,lc);
	if(tr[cnt<<1|1].l<=r) change(l,r,val,op,rc);
}

void doit(void)
{
    scanf("%d%d",&n,&m);
    int pos,x,y;
    for(int i=2;i<=n;i++)
    {
    	scanf("%d",&x);
    	add(x,i);
	}
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);

    dfs(1,0);
    build(1,cm,1);

    for(int i=1;i<=m;i++)
    {
        scanf("%d",&pos);
        if(pos==0)
        {
        	scanf("%d%d",&x,&y);
        	change(st[x],ed[x],v[x],-1,1);
        	v[x]=y;
        	change(st[x],ed[x],v[x],1,1);
		}
		else
		{
			scanf("%d",&x);
			printf("%d\n",ask(root1[x],id[st[x]],v[x]));
		}
    }
}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        init();
        doit();
    }

    return 0;
}