关于树链剖分代码Debug
查看原帖
关于树链剖分代码Debug
161296
DarksideCoderω楼主2020/7/23 23:21

题目描述如下

给出一棵有N个点的树,每个点都有一个值ai,两种操作:
1、U x y:修改第x个点的值为y;
2、Q x y:求第x个点到第y个点路径上所有点(包含x和y)的最大值

代码运行错误

//Include
#include<cstdio>
#include<cstring>
using namespace std;
//Basic
namespace Basic
{
	template<typename Type>
	inline Type Max(Type x,Type y)
	{
		if(x>y)return x;
		else   return y;
	}
	template<typename Type>
	inline Type Min(Type x,Type y)
	{
		if(x<y)return x;
		else   return y;
	}
	template<typename Type>
	inline void Swap(Type x,Type y)
	{
		Type tt=x;x=y;y=tt;
		return ;
	}
}
using namespace Basic;
//Const
//Type
namespace Tree
{
	const int Maxn=210000;
	#define ls(x) node[x].lc
	#define rs(x) node[x].rc
	struct _Segment_Tree_Node
	{
		int lc,rc,l,r,s;
	};
	struct _Segment_Tree
	{
		int len;
		_Segment_Tree_Node node[Maxn*2];
		_Segment_Tree(){Clean();}
		inline void Clean(){len=0;}
		inline void Build(int &now,int l,int r)
		{
			now=++len;
			node[now].l=l;
			node[now].r=r;
			if(l==r)
			{
				return;
			}
			else
			{
				int m=(l+r)/2;
				Build(ls(now),l, m );
				Build(rs(now),m+1,r);
			}
		}
		inline void Modify(int now,int pos,int val)
		{
			int l=node[now].l;
			int r=node[now].r;
			if(l==r)
			{
				node[now].s=val;
				return ;
			}
			else
			{
				int m=(l+r)/2;
				if(pos<=m)Modify(ls(now),pos,val);
				else	  Modify(rs(now),pos,val);
				node[now].s=Max(
				node[ls(now)].s,
				node[rs(now)].s);
			}
		}
		inline int Query(int now,int L,int R)
		{
			int l=node[now].l;
			int r=node[now].r;
			if(L<=l&&r<=R)
			{
				return node[now].s;
			}
			else
			{
				int m=(l+r)/2;
				if(m+1<=L)	 return Query(rs(now),L,R);
				else if(m>=R)return Query(ls(now),L,R);
				return Max(
				Query(ls(now),L, m ),
				Query(rs(now),m+1,R));
			}
		}
	};
	struct _Tree_Line
	{
		int x,y,next;
	};
	struct _Tree
	{
		int tot[Maxn],son[Maxn],dep[Maxn],dfn[Maxn],dad[Maxn],top[Maxn],root;
		_Segment_Tree T;int len,last[Maxn];
		_Tree_Line line[Maxn*2];
		_Tree(){Clean();}
		inline void Clean(){len=0;memset(last,-1,sizeof(last));}
		inline void Insert(int x,int y)
		{
			line[len].x=x;line[len].y=y;
			line[len].next=last[x];last[x]=len++;
		}
		inline void Dfs1(int x,int f)
		{
			dep[x]=dep[f]+1;
			dad[x]=f;
			son[x]=0;
			tot[x]=1;
			for(int k=last[x];k!=-1;k=line[k].next)
			{
				int y=line[k].y;
				if(y==f)continue;
				Dfs1(y,x);
				if(tot[son[x]]<tot[y])son[x]=y;
				tot[x]+=tot[y];
			}
		}
		inline void Dfs2(int x,int t)
		{
			static int ts=0;ts++;
			dfn[x]=ts;
			top[x]=t;
			if(son[x])
				Dfs2(son[x],t);
			else
				return;
			for(int k=last[x];k!=-1;k=line[k].next)
			{
				int y=line[k].y;
				if(y==dad[x]||y==son[x])continue;
				Dfs2(y,y);
			}
		}
		inline int Solve(int x,int y)
		{
			int tx=top[x],ty=top[y],ans=0;
			while(tx!=ty)
			{
				if(dep[tx]>dep[ty])
					Swap(x,y),Swap(tx,ty);
				ans=Max(ans,T.Query(root,dfn[ty],dfn[y]));
				y=dad[ty];ty=top[y];
			}
			if(x==y)return Max(ans,T.Query(root,dfn[x],dfn[x]));
			else
			{
				if(dep[x]>dep[y])Swap(x,y);
				return Max(ans,T.Query(root,dfn[x],dfn[y]));
			}
		}
	};
}
using namespace Tree;
//Define
_Tree T;
int n,m;
int arr[Maxn];
//Main
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
	for(int i=1,x,y;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		T.Insert(x,y);
		T.Insert(y,x);
	}
	T.Dfs1(1,0);
	T.Dfs2(1,1);
	T.T.Build(T.root,1,n);
	for(int i=1;i<=n;i++)T.T.Modify(T.root,T.dfn[i],arr[i]);
	char st[3];
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%s",st);
		if(st[0]=='U')
		{
			scanf("%d%d",&x,&y);
			T.T.Modify(T.root,T.dfn[x],y);
		}
		else
		{
			scanf("%d%d",&x,&y);
			printf("%d\n",T.Solve(x,y));
		}
	}
	return 0;
}

这题已经让我心态大崩一天了,恳请大佬相助,码风语法问题@我或自行百度

2020/7/23 23:21
加载中...