HDU - 5390 tree （可持久化字典樹+線段樹）

題目vj連結

題面：

題意：

給定一棵有根樹，根節點為1，節點 i i i 的權值為 v i vi vi。

有以下兩種操作：

（1） 0 x y ---- 将節點 x x x 的權值改為 y y y

（2） 1 x ---- 查詢 v x   x o r   v t v_x\space xor\space v_t vx​ xor vt​ 的最大值，其中 t ∈ p a t h ( x , r o o t ) t \in path(x,root) t∈path(x,root)

題解：

①、考慮不帶修改

v x v_x vx​ 是一個已知的定值，查詢 v x v_x vx​ 與一組值 v t v_t vt​ 中的某個數的異或的最大值，用樹上可持久化字典樹即可處理。

空間複雜度 O ( n l o g n ) O(nlogn) O(nlogn)，時間複雜度 O ( n l o g n ) O(nlogn) O(nlogn)

②、考慮修改。

查詢具有特殊性，每次查詢的 v t v_t vt​ 是根節點到 x x x 點這一條鍊上的值。

修改是單點修改。那麼修改一個點之後隻會影響它的子樹。

是以我們把修改單點的值，變為修改子樹。

我們把修改分解為一次删除和一次增加。

即對于子樹中所有的節點到根節點的路徑上減去 v x v_x vx​ 加上 y y y

我們考慮 d f s dfs dfs 序上建立線段樹，我們對于線段樹的每個節點（線段樹的一個節點對應一個區間）建立一棵字典樹。假設我們目前要修改的區間為 [ l , r ] [l,r] [l,r]，線上段樹上進行區間修改。假設目前要修改的區間 [ l , r ] [l,r] [l,r] 覆寫了線段樹上 c n t cnt cnt 點所表示的區間，那麼就在 c n t cnt cnt 節點所在的字典樹上插入元組 ( v a l , o p ) (val,op) (val,op)，其中 v a l val val 表示此次修改的權值， o p op op 表示是删除還是增加。表示該區間所有的節點到根節點的路徑上的值均變化 ( v a l , o p ) (val,op) (val,op)，不再處理 c n t cnt cnt 的子區間。

在區間修改時，我們标記不下傳。

那麼區間 [ l , r ] [l,r] [l,r] 最多覆寫線段樹上 l o g n logn logn個節點，每個節點的修改是 l o g n logn logn的，那麼每修改一次的時間複雜度就是 O ( l o g 2 n ) O(log^2n) O(log2n)

考慮查詢。

假設我們現在要查詢的節點是 x x x 節點，它對應線段樹上的節點為 c n t cnt cnt。

我們考慮到某一位時，該位的真實貢獻值應該為可持久化字典樹上的貢獻加上線段樹上所有能覆寫 c n t cnt cnt 的區間的貢獻。我們知道，這樣的區間至多有 l o g n logn logn 個，每次查詢每一位時我們都需要周遊這 l o g n logn logn個區間。

時間複雜度： O ( l o g 2 n ) O(log^2n) O(log2n)

那麼總的時間複雜度就為 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

現在來分析一下空間複雜度。

每個區間的修改數 v a l val val 至多會分成 l o g n logn logn 個區間的修改，每個修改需要 l o g n logn logn 空間。那麼空間複雜度為 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

代碼：

#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;
}