BZOJ3052/UOJ#58 [wc2013]糖果公园 莫队 带修莫队 树上莫队

时间：2024-01-16 22:02:20

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ3052.html

题目传送门 - BZOJ3052

题目传送门 - UOJ#58

题意

　　给定一棵树，有 $n$ 个节点。有 $m$ 种颜色，第 $i$ 个节点的颜色为 $c_i$ 。

　　给定参数 $v_{1},v_2,\cdots,v_m$ 和 $w_1,w_2,\cdots ,w_n$ ，具有以下意义：

　　　　第 $i$ 次遇到颜色为 $j$ 的节点，新得到的收益为 $v_{j}\times w_i$ 。

　　现在有 $q$ 次操作，操作有以下两种类型：

　　1.　给定 $x,y$ ，询问一个人从节点 $x$ 走到节点 $y$ 得到的总收益。

　　2.　给定 $x,y$ ，把节点 $x$ 的颜色改成 $y$ 。

　　请你对于每一个询问输出结果。

　　$1\leq n,m,q\leq 10^5,1\leq v_i,w_i\leq 10^6\ \ \ \ \ \ \ \rm{Time\ limit = 8s} $

题解

　　树上带修莫队模板题。

　　把树上询问转化成括号序列，变成区间问题。然后上带修莫队。

　　注意询问的时候的特殊情况，例如 $x$ 和 $y$ 存在子孙或祖先关系时，括号序列区间的取值有所不同。

　　时间复杂度 $O(n^\frac{5}{3})$ 。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int read(){

	char ch=getchar();

	int x=0;

	while (!isdigit(ch))

		ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+ch-48,ch=getchar();

	return x;

}

const int N=100005;

struct Gragh{

	static const int M=N*2;

	int cnt,y[M],nxt[M],fst[N];

	void clear(){

		cnt=0;

		memset(fst,0,sizeof fst);

	}

	void add(int a,int b){

		y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;

	}

}g;

struct Query{

	int L,R,id,LCA;

	LL ans;

	Query(){}

	Query(int _L,int _R,int _id,int _LCA){

		L=_L,R=_R,id=_id,LCA=_LCA;

	}

}Q[N];

struct Operation{

	int x,v1,v2,id;

	Operation(){}

	Operation(int _x,int _v1,int _v2,int _id){

		x=_x,v1=_v1,v2=_v2,id=_id;

	}

}O[N];

int n,m,q,Qcnt,Ocnt;

int depth[N],fa[N][20],in[N],out[N],id[N<<1],bID[N<<1],Time;

int v[N],w[N],c[N],dc[N];

int tax[N],opt[N];

void dfs(int x,int pre,int d){

	fa[x][0]=pre,depth[x]=d,id[in[x]=++Time]=x;

	for (int i=1;i<17;i++)

		fa[x][i]=fa[fa[x][i-1]][i-1];

	for (int i=g.fst[x];i;i=g.nxt[i])

		if (g.y[i]!=pre)

			dfs(g.y[i],x,d+1);

	id[out[x]=++Time]=x;

}

int LCA(int x,int y){

	if (depth[x]<depth[y])

		swap(x,y);

	for (int i=16;i>=0;i--)

		if (depth[x]-(1<<i)>=depth[y])

			x=fa[x][i];

	if (x==y)

		return x;

	for (int i=16;i>=0;i--)

		if (fa[x][i]!=fa[y][i])

			x=fa[x][i],y=fa[y][i];

	return fa[x][0];

}

bool cmp(Query a,Query b){

	if (bID[a.L]!=bID[b.L])

		return bID[a.L]<bID[b.L];

	if (bID[a.R]!=bID[b.R])

		return bID[a.R]<bID[b.R];

	return a.id<b.id;

}

bool cmpid(Query a,Query b){

	return a.id<b.id;

}

LL ans=0;

void update(int i){

	int x=id[i];

	if (!opt[x])

		ans+=1LL*v[c[x]]*w[++tax[c[x]]];

	else

		ans-=1LL*v[c[x]]*w[tax[c[x]]--];

	opt[x]^=1;

}

void update_Time(int i){

	int x=O[i].x,a=O[i].v1,b=O[i].v2;

	if (c[x]!=a)

		swap(a,b);

	if (opt[x])

		ans-=1LL*v[c[x]]*w[tax[c[x]]--];

	c[x]=b;

	if (opt[x])

		ans+=1LL*v[c[x]]*w[++tax[c[x]]];

}

void solve(){

	sort(Q+1,Q+Qcnt+1,cmp);

	O[0].id=0,O[Ocnt+1].id=q+1;

	memset(tax,0,sizeof tax);

	memset(opt,0,sizeof opt);

	int L=1,R=0,t=0;

	for (int i=1;i<=Qcnt;i++){

		while (L<Q[i].L)

			update(L++);

		while (L>Q[i].L)

			update(--L);

		while (R<Q[i].R)

			update(++R);

		while (R>Q[i].R)

			update(R--);

		while (O[t+1].id<Q[i].id)

			update_Time(++t);

		while (O[t].id>Q[i].id)

			update_Time(t--);

		Q[i].ans=ans+1LL*v[c[Q[i].LCA]]*w[tax[c[Q[i].LCA]]+1];

	}

	sort(Q+1,Q+Qcnt+1,cmpid);

}

int main(){

	n=read(),m=read(),q=read();

	for (int i=1;i<=m;i++)

		v[i]=read();

	for (int i=1;i<=n;i++)

		w[i]=read();

	g.clear();

	for (int i=1,a,b;i<n;i++){

		a=read(),b=read();

		g.add(a,b);

		g.add(b,a);

	}

	for (int i=1;i<=n;i++)

		dc[i]=c[i]=read();

	Time=0;

	dfs(1,0,0);

	for (int i=1;i<=n*2;i++)

		bID[i]=(i-1)/pow(n,0.666);

	Qcnt=Ocnt=0;

	for (int i=1;i<=q;i++){

		int opt=read(),x=read(),y=read();

		if (!opt){

			O[++Ocnt]=Operation(x,dc[x],y,i);

			dc[x]=y;

		}

		else {

			if (in[x]>in[y])

				swap(x,y);

			int lca=LCA(x,y);

			if (x==lca)

				Q[++Qcnt]=Query(in[x],in[y],i,0);

			else

				Q[++Qcnt]=Query(out[x],in[y],i,lca);

		}

	}

	solve();

	for (int i=1;i<=Qcnt;i++)

		printf("%lld\n",Q[i].ans);

	return 0;

}

　　

相关文章