【洛谷P3313】[SDOI2014]旅行

2024-01-18 14:35:58

题意

题目描述

S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。

为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国*为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。

在S国的历史上常会发生以下几种事件：

“CC x c“：城市x的居民全体改信了c教；

“CW x w“：城市x的评级调整为w;

“QS x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；

“QM x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

输入格式

输入的第一行包含整数N，Q依次表示城市数和事件数。

接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的评级和信仰。 接下来N-1行每行两个整数x，y表示一条双向道路。

接下来Q行，每行一个操作，格式如上所述。

输出格式

对每个QS和QM事件，输出一行，表示旅行者记下的数字。

输入输出样例

输入 #1 
5 6
3 1
2 3
1 2
3 3
5 1
1 2
1 3
3 4
3 5
QS 1 5
CC 3 1
QS 1 5
CW 3 3
QS 1 5
QM 2 4
输出 #1 
8
9
11
3

说明/提示

N，Q < =10^5 ， C < =10^5

数据保证对所有QS和QM事件，起点和终点城市的信仰相同；在任意时

刻，城市的评级总是不大于10^4的正整数，且宗教值不大于C。

题解

刚学完动态开点和可持久化线段树来做这道题，思路秒出：对于每一个宗教开一个线段树即可

然而遇到了几个问题：

  • 一开始想的是修改 x 城市评分/宗教的时候 for 循环一次（我也不知道当时怎么想到这卡住的了），后来才知道不用，只要改 x 原宗教和新宗教的线段树就可以
  • 对动态开点没理解透彻，还在想着主席树里先建一个空树balabala........，实际这里就不用建立空树，只有修改的点才需要开点，而且初始建树和每次修改的函数可以写成一个函数

还学到几个小技巧：

  • 开点的build函数里面传址调用 rt 新开点，注意配合 
    if(!rt) rt=++cnt;

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 2e5+10;
int head[N<<1],hson[N],dep[N],siz[N],f[N];
int ecnt=-1,dfn[N],cntd,pos[N],Q,n,top[N];
int ls[N<<5],rs[N<<5],root[N];
int c[N],val[N],cnt,p[N]; 
struct segment 
{
	int sum,max;
}tree[N<<5];
struct edge    
{
	int nxt,to;
}a[N<<1];
void add(int x,int y)
{
	a[++ecnt].nxt=head[x];
	a[ecnt].to=y;
	head[x]=ecnt;
}
void dfs1(int u,int fa)
{
	siz[u]=1;
	for(int i=head[u];~i;i=a[i].nxt)
	{
		int v=a[i].to;
		if(v==fa) continue;
		dep[v]=dep[u]+1;
		f[v]=u;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[hson[u]]) hson[u]=v;
	}
}
void dfs2(int u,int tp)
{
	dfn[u]=++cntd,pos[cntd]=u,top[u]=tp;
	if(hson[u]) dfs2(hson[u],tp);
	for(int i=head[u];~i;i=a[i].nxt)
	{
		int v=a[i].to;
		if(v==f[u]||v==hson[u]) continue;
		dfs2(v,v);
	}
}
//-------------上面都是板子--------------
/*
int update(int w,int l,int r,int pos)
{
    int rt=++cnt;
    tree[rt].max=max(tree[rt].max,w),tree[rt].sum+=w;
    if (l==r) return rt; int mid=(l+r)>>1;
    if (mid>=pos)ls[rt]=update(w,l,mid,pos);
    else rs[rt]=update(w,mid+1,r,pos);
    return rt;
}

void update(int &rt,int w,int l,int r,int pos)
{
    if (!rt) rt=++cnt;
    tree[rt].max=max(tree[rt].max,w),tree[rt].sum+=w;
    if (l==r) return; int mid=(l+r)/2;
    if (mid>=pos) update(ls[rt],w,l,mid,pos);
    else update(rs[rt],w,mid+1,r,pos);
}
*/
void build(int &rt,int l,int r,int x,int v)
{
	//int rt=++cnt;
	if(!rt) rt=++cnt;
	if(l==r) 
	{
		tree[rt].max=tree[rt].sum=v;//...无语了，又写错了 
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid) build(ls[rt],l,mid,x,v);
	else build(rs[rt],mid+1,r,x,v);
	tree[rt].sum=tree[ls[rt]].sum+tree[rs[rt]].sum;
	tree[rt].max=max(tree[ls[rt]].max,tree[rs[rt]].max);
	return ;
}
/*
void update(int pre,int l,int r,int w,int v,int op)//修改城市评分val 
{
	//int rt=++cnt;
	//ls[rt]=ls[pre],rs[rt]=rs[pre];
	if(l==r) 
	{//这里单点修改应该改val[l] 
		if(op) val[l]=v;
		else val[l]=0;
		return;
	}
	int mid=(l+r)>>1;
	if(w<=mid) update(ls[pre],l,mid,w,v,op);
	else update(rs[pre],mid+1,r,w,v,op);
	tree[pre].sum=tree[ls[pre]].sum+tree[rs[pre]].sum;
	tree[pre].max=max(tree[ls[pre]].max,tree[rs[pre]].max);
}
*/
//这份代码最终没用到change，都改成build了 
void change(int &rt,int l,int r,int x,int v)//修改城市宗教rel,也可以修改城市评分val 
{
	//if(!rt) rt=++cnt;
	if(l==r)
	{//这里单点修改应该改tree[rt] 
		tree[rt].sum=tree[rt].max=v;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) change(ls[rt],l,mid,x,v);
	else change(rs[rt],mid+1,r,x,v); 
	tree[rt].sum=tree[ls[rt]].sum+tree[rs[rt]].sum;
	tree[rt].max=max(tree[ls[rt]].max,tree[rs[rt]].max);
}
int querysum(int u,int l,int r,int x,int y)
{
	//if(!u) return 0; 
	if(x<=l&&r<=y) return tree[u].sum;
	int mid=(l+r)>>1;
	int ret=0;
	if(x<=mid) ret+=querysum(ls[u],l,mid,x,y);
	//printf("(l,r):(%d,%d):%d\n",l,r,ret);
	if(y>mid)  ret+=querysum(rs[u],mid+1,r,x,y);
	return ret;
}
int querymax(int u,int l,int r,int x,int y)
{
	//if(!u) return -1;
	if(x<=l&&r<=y) return tree[u].max;
	int mid=(l+r)>>1;
	int ret=0;
	if(x<=mid) ret=max(ret,querymax(ls[u],l,mid,x,y));
	if(y>mid)  ret=max(ret,querymax(rs[u],mid+1,r,x,y));
	return ret;
}
int Querysum(int x,int y)
{
	int ret=0;
	int rt=root[c[x]];
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ret+=querysum(rt,1,n,dfn[top[x]],dfn[x]);
		x=f[top[x]];
	//	printf("(x,y):(%d,%d)\n",x,y);
	}
	//printf("ret=%d\n",ret);
	if(dfn[x]>dfn[y]) swap(x,y);
	//printf("(x,y):(%d,%d)\n",x,y);
	ret+=querysum(rt,1,n,dfn[x],dfn[y]);
	return ret;
}
int Querymax(int x,int y)
{
	int ret=0;
	int rt=root[c[x]];
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ret=max(ret,querymax(rt,1,n,dfn[top[x]],dfn[x]));
		x=f[top[x]];
	}
	if(dfn[x]>dfn[y]) swap(x,y);
	ret=max(ret,querymax(rt,1,n,dfn[x],dfn[y]));
	return ret;
}
int main()
{
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&Q);
	for(int i=1;i<=n;i++) scanf("%d%d",&val[i],&c[i]),p[i]=c[i];
	for(int i=1;i<n;i++) 
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	//sort(p+1,p+n+1);
	//int tot=unique(p+1,p+n+1)-p-1;//给宗教去重 
	dfs1(1,-1);
	dfs2(1,1);
	//root[0]=build(1,n);
	for(int i=1;i<=n;i++) build(root[c[i]],1,n,dfn[i],val[i]);
	//	root[c[i]]=build(1,n);
	
	//操作的时候要想好是root[c[x]],root[y],dfn[x]......这些乱七八糟的 
	for(int i=1;i<=Q;i++)
	{
		char op[5];
		int x,y;
		scanf("%s%d%d",op+1,&x,&y);
		if(op[2]=='C')
		{
			build(root[c[x]],1,n,dfn[x],0);//把原宗教清零
			build(root[y],1,n,dfn[x],val[x]);//把新宗教更新 
			c[x]=y;
		}
		if(op[2]=='W') 
		{
			build(root[c[x]],1,n,dfn[x],y);
			val[x]=y;
		}
		if(op[2]=='S') printf("%d\n",Querysum(x,y));
		if(op[2]=='M') printf("%d\n",Querymax(x,y));
	}
	return 0;
}
/*自己改的数据 
5 6
1 1
2 3
1 2
1 3
5 1
1 2
1 3
3 4
3 5
QS 1 5
CC 3 1
QS 1 5
CW 3 3
QS 1 5
QM 2 4
*/
上一篇：P3308 [SDOI2014]LIS


下一篇：P3311 [SDOI2014] 数数