您的位置: 首页  >  文章  >  【树链剖分】【离线操作】【SDOI2014】旅行

【树链剖分】【离线操作】【SDOI2014】旅行

分类: 文章 • 2025-01-05 14:42:58

（rhj ak ioi!!!）
【题目描述】
【树链剖分】【离线操作】【SDOI2014】旅行
【输入】
输入的第一行包含整数 N，Q 依次表示城市数和事件数。
接下来 N 行，第 i+1行两个整数 Wi ，Ci 依次表示记录开始之前，城市 i 的评级和信仰。
接下来 N−1 行每行两个整数 x，y 表示一条双向道路。
接下来 Q 行，每行一个操作，格式如上所述。

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

【样例输入】
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

【样例输出】
8
9
11
3
提示
对所有的数据，N,Q≤10^5, C≤10^5 ，对所有 QS 和 QM 事件，起点和终点城市的信仰相同；在任意时刻，城市的评级总是不大于 10^4的正整数，且宗教值不大于 C。

【思路】

这道题似乎可以动态开点。不过这里采用离线做法。（本来我以为离线做法做不了 ）这道题的离线思路和[SDOI2008]郁闷的小J差不多，依次处理每个宗教。对于宗教的修改才做，我们可以把节点在原宗教上的影响赋为0，然后再进行新宗教上的单点修改（即拆成两个单点修改）。然后就只需要保证处理完每个宗教以后删除所有的节点（这个删除操作只需要删除最终树上该宗教的点，就可以保证时间复杂度）。
代码：（260行的丑代码）

#include<bits/stdc++.h>
#define re register
#define lc (p<<1)
#define rc (p<<1|1)
#define len(p) (t[p].r-t[p].l+1)
using namespace std;
long long n,m,a,b;
struct node{
	long long u,v;
}e[2000001];
struct tree{
	long long l,r;
	long long sum;
	long long mx;
}t[4000001];
struct que{
	long long col;
	long long ans;
	long long u,v;
	long long opt;
	long long tim;
}q[1000001];
/*
opt:
2 单点修改
3 询问sum
4 询问mx
*/
long long f[1000001];
long long nxp[2000001];
long long cnt=0;
inline void add(long long u,long long v)
{
	e[++cnt].u=u;
	e[cnt].v=v;
	nxp[cnt]=f[u];
	f[u]=cnt;
}
long long son[1000001];
long long siz[1000001];
long long dep[1000001];
long long fa[1000001];
long long top[1000001];
long long seg[1000001];
long long rev[1000001];
void dfs1(long long u,long long ff)
{
	dep[u]=dep[ff]+1;
	fa[u]=ff;
	siz[u]=1;
	for(long long re i=f[u];i;i=nxp[i])
	{
		long long v=e[i].v;
		if(!dep[v])
		{
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[son[u]]<siz[v])son[u]=v;
		}
	}
}
long long tot=0;
void dfs2(long long u)
{
	if(son[u])
	{
		seg[son[u]]=++tot;
		rev[tot]=son[u];
		top[son[u]]=top[u];
		dfs2(son[u]);
	}
	for(long long re i=f[u];i;i=nxp[i])
	{
		long long v=e[i].v;
		if(!top[v])
		{
			top[v]=v;
			seg[v]=++tot;
			rev[tot]=v;
			dfs2(v);
		}
	}
}
long long sum=0,mx=0,id=0;
long long val[1000001];
inline void pushup(long long p)
{
	t[p].sum=t[lc].sum+t[rc].sum;
	t[p].mx=max(t[lc].mx,t[rc].mx);
}
void build(long long p,long long l,long long r)
{
	t[p].l=l;
	t[p].r=r;
	if(l==r)return;
	long long mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(p);
}
void change(long long p,long long k,long long v)
{
	long long l=t[p].l,r=t[p].r;
	if(l==r)
	{
		t[p].mx=t[p].sum=v;
		return;
	}
	long long mid=(l+r)>>1;
	if(k<=mid)change(lc,k,v);
	if(k>mid)change(rc,k,v);
	pushup(p);
}
void ask(long long p,long long ql,long long qr)
{
	long long l=t[p].l,r=t[p].r;
	if(ql<=l&&qr>=r)
	{
		sum+=t[p].sum;
		mx=max(mx,t[p].mx);
		return;
	}
	long long mid=(l+r)>>1;
	if(ql<=mid)ask(lc,ql,qr);
	if(qr>mid)ask(rc,ql,qr);
}
long long root=1;
int tt=0;
void query(long long x,long long y)
{
	long long fx=top[x],fy=top[y];
	sum=0;mx=-0x7f7f7f7f;
	while(fx!=fy)
	{
		if(dep[fx]<dep[fy])
		{
			swap(fx,fy);
			swap(x,y);
		}
		ask(1,seg[fx],seg[x]);
		x=fa[fx];
		fx=top[x];
	}
	if(dep[x]>dep[y])swap(x,y);
	ask(1,seg[x],seg[y]);
}
int num=0;
long long col[100001];
inline bool cmp1(que a,que b)
{
	if(a.col==b.col)return a.tim<b.tim;
	return a.col<b.col;
}
inline bool cmp2(que a,que b)
{
	return a.tim<b.tim;
}
int main()
{
	scanf("%lld",&n);scanf("%lld",&m);
	for(long long re i=1;i<=n;i++)
	{
		scanf("%lld%lld",&val[i],&col[i]);
		q[++num].opt=2;
		q[num].tim=0;
		q[num].col=col[i];
		q[num].u=i;
		q[num].ans=val[i];
	}
	for(int re i=1;i<n;i++)
	{
		scanf("%lld%lld",&a,&b);
		add(a,b);
		add(b,a);
	}
	rev[1]=tot=seg[1]=top[1]=1;
	dfs1(1,0);
	dfs2(1);
	build(1,1,tot);
	while(m--)
	{
		char c[10];
		scanf("\n%s%lld%lld",c+1,&a,&b);
		if(c[1]=='C'&&c[2]=='C')
		{
			q[++num].u=a;
			q[num].tim=++tt;
			q[num].col=col[a];
			q[num].ans=0;
			q[num].opt=2;
			col[a]=b;
			q[++num].u=a;
			q[num].tim=++tt;
			q[num].col=col[a];
			q[num].ans=val[a];
			q[num].opt=2;
		}
		if(c[1]=='C'&&c[2]=='W')
		{
			q[++num].u=a;
			q[num].tim=++tt;
			q[num].col=col[a];
			q[num].ans=b;
			q[num].opt=2;
			val[a]=b;
		}
		if(c[1]=='Q'&&c[2]=='S')
		{
			q[++num].u=a;
			q[num].col=col[a];
			q[num].v=b;
			q[num].opt=3;
			q[num].tim=++tt;
		}
		if(c[1]=='Q'&&c[2]=='M')
		{
			q[++num].u=a;
			q[num].col=col[a];
			q[num].v=b;
			q[num].opt=4;
			q[num].tim=++tt;
		}
	}
	for(int re i=1;i<=n;i++)
	{
		q[++num].u=i;
		q[num].tim=tt+1;
		q[num].col=col[i];
		q[num].ans=0;
		q[num].opt=2;
	}
	sort(q+1,q+num+1,cmp1);
	for(int re i=1;i<=num;i++)
	{
		int opt=q[i].opt;
		if(opt==2)
			change(1,seg[q[i].u],q[i].ans);
		if(opt==3)
		{
			query(q[i].u,q[i].v);
			q[i].ans=sum;
		}
		if(opt==4)
		{
			query(q[i].u,q[i].v);
			q[i].ans=mx;
		}
	}
	sort(q+1,q+num+1,cmp2);
	for(int re i=1;i<=num;i++)
	{
		int opt=q[i].opt;
		if(opt==3||opt==4)
		{
			printf("%lld\n",q[i].ans);
		}
	}
}

相关推荐