[Luogu 2486] SDOI2011 染色

树剖水题，线段树维护。
详细题解不写了。
我只想说我写的线段树又变漂亮了qwq
#include <algorithm>

#include <cstdio>

#include <cstring>

const int MAXN=100010;

int n,m;

class HLD

{

	private:

		bool vis[MAXN];

		int num;

		static int rank[MAXN];

		static struct Node

		{

			int v,depth,father,son,top,size,DFN;

		}s[MAXN];

		class SegmentTree

		{

			private:

				struct Node

				{

					int v,left,right,lazy,color[2];

					Node *c[2];

					Node(int l,int r):left(l),right(r),lazy(0)

					{

						memset(color,0,sizeof color);

						c[0]=c[1]=nullptr;

						if(l==r)

						{

							v=1;

							color[0]=color[1]=s[rank[l]].v;

							return;

						}

						int mid=l+r>>1;

						c[0]=new Node(l,mid);

						c[1]=new Node(mid+1,r);

						PushUp();

					}

					~Node(void)

					{

						if(c[0]!=nullptr)

							delete c[0];

						if(c[1]!=nullptr)

							delete c[1];

					}

					void Modify(int x)

					{

						v=1;

						lazy=color[0]=color[1]=x;

					}

					void PushUp(void)

					{

						v=c[0]->v+c[1]->v;

						color[0]=c[0]->color[0];

						color[1]=c[1]->color[1];

						if(c[0]->color[1]==c[1]->color[0])

							--v;

					}

					void PushDown(void)

					{

						if(c[0]!=nullptr)

							c[0]->Modify(lazy);

						if(c[1]!=nullptr)

							c[1]->Modify(lazy);

						lazy=0;

					}

					int Color(int x)

					{

						if(left==right)

							return color[0];

						if(lazy)

							PushDown();

						int mid=left+right>>1;

						if(x>mid)

							return c[1]->Color(x);

						else

							return c[0]->Color(x);

					}

					void Change(int l,int r,int v)

					{

						if(l==left && r==right)

						{

							Modify(v);

							return;

						}

						if(lazy)

							PushDown();

						int mid=left+right>>1;

						if(r<=mid)

							c[0]->Change(l,r,v);

						else if(l>mid)

							c[1]->Change(l,r,v);

						else

						{

							c[0]->Change(l,mid,v);

							c[1]->Change(mid+1,r,v);

						}

						PushUp();

					}

					int Query(int l,int r)

					{

						if(l==left && r==right)

							return v;

						int mid=left+right>>1;

						if(lazy)

							PushDown();

						if(r<=mid)

							return c[0]->Query(l,r);

						else if(l>mid)

							return c[1]->Query(l,r);

						else

						{

							int ans=c[0]->Query(l,mid)+c[1]->Query(mid+1,r);

							if(c[0]->color[1]==c[1]->color[0])

								--ans;

							return ans;

						}

					}

				}*root;

			public:

				SegmentTree(int n)

				{

					root=new Node(1,n);

				}

				~SegmentTree(void)

				{

					delete root;

				}

				int Color(int x)

				{

					return root->Color(x);

				}

				void Change(int l,int r,int v)

				{

					root->Change(l,r,v);

				}

				int Query(int l,int r)

				{

					return root->Query(l,r);

				}

		}*T;

		struct Edge

		{

			int to;

			Edge *next;

			Edge(int to,Edge* next):to(to),next(next){}

			~Edge(void)

			{

				if(next!=nullptr)

					delete next;

			}

		}*head[MAXN];

		void AddEdges(int u,int v)

		{

			head[u]=new Edge(v,head[u]);

			head[v]=new Edge(u,head[v]);

		}

		void DFS1(int u,int k)

		{

			s[u].depth=k;

			s[u].size=1;

			int v;

			for(Edge *i=head[u];i!=nullptr;i=i->next)

				if(!s[v=i->to].size)

				{

					DFS1(v,k+1);

					s[v].father=u;

					s[u].size+=s[v].size;

					if(s[v].size>s[s[u].son].size)

						s[u].son=v;

				}

		}

		void DFS2(int u,int top)

		{

			s[u].top=top;

			s[u].DFN=++num;

			rank[num]=u;

			vis[u]=true;

			if(s[u].son)

				DFS2(s[u].son,top);

			int v;

			for(Edge *i=head[u];i!=nullptr;i=i->next)

				if(!vis[v=i->to])

					DFS2(v,v);

		}

	public:

		HLD(int n):num(0)

		{

			memset(s,0,sizeof s);

			std::fill(head+1,head+n+1,nullptr);

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

				scanf("%d",&s[i].v);

			for(int i=1,u,v;i<n;++i)

			{

				scanf("%d %d",&u,&v);

				AddEdges(u,v);

			}

			DFS1(1,1);

			DFS2(1,1);

			T=new SegmentTree(n);

		}

		~HLD(void)

		{

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

				delete head[i];

			delete T;

		}

		void Change(int x,int y)

		{

			int a,b,v;

			scanf("%d",&v);

			while((a=s[x].top)^(b=s[y].top))

				if(s[a].depth>s[b].depth)

				{

					T->Change(s[a].DFN,s[x].DFN,v);

					x=s[a].father;

				}

				else

				{

					T->Change(s[b].DFN,s[y].DFN,v);

					y=s[b].father;

				}

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

				T->Change(s[x].DFN,s[y].DFN,v);

			else

				T->Change(s[y].DFN,s[x].DFN,v);

		}

		void Query(int x,int y)

		{

			int a,b,ans=0;

			while((a=s[x].top)^(b=s[y].top))

				if(s[a].depth>s[b].depth)

				{

					ans+=T->Query(s[a].DFN,s[x].DFN);

					x=s[a].father;

					if(T->Color(s[a].DFN)==T->Color(s[x].DFN))

						--ans;

				}

				else

				{

					ans+=T->Query(s[b].DFN,s[y].DFN);

					y=s[b].father;

					if(T->Color(s[b].DFN)==T->Color(s[y].DFN))

						--ans;

				}

			ans+=s[x].depth<s[y].depth ? T->Query(s[x].DFN,s[y].DFN) : T->Query(s[y].DFN,s[x].DFN);

			printf("%d\n",ans);

		}

}*T;

int HLD::rank[MAXN];

HLD::Node HLD::s[MAXN];

int main(int argc,char** argv)

{

	scanf("%d %d",&n,&m);

	T=new HLD(n);

	char c;

	for(int i=1,x,y;i<=m;++i)

	{

		scanf("\n%c %d %d",&c,&x,&y);

		if(c=='C')

			T->Change(x,y);

		else

			T->Query(x,y);

	}

	delete T;

	return 0;

}
谢谢阅读。
巴特西

[Luogu 2486] SDOI2011 染色

[Luogu 2486] SDOI2011 染色

最新文章

热门文章
