BZOJ4538 HNOI2016 网络

这道题解法很多，我知道三种：点分治；利用DFS序转化为平面内求最值问题；直接搞

这题考场上刚了很久，但是最终没有写出来，于是导致第一天雪崩，考试一定要冷静。

做的时候想到了前两种方法，因为第二种比较直观，于是选择了第二种。

但是发现这东西直接维护的话：

1.用3个树套在一起（堆可以用两个优先队列做出来，但是STL似乎很慢），很难写，加复杂度很吓人。

2.用KD-TREE，但是这东西我不熟练，复杂度也不会证明（@Claris说是根号M的）。

又发现题目没有要求强制在线，于是准备用CDQ分治+扫描线+线段树，貌似很容易就会想到这个思路。但写起来发现不是很好写，调了3个小时还没搞出来于是很不甘心，结果最终都没有做出来，浪费了大量的时间。

考完以后看网上的题解却发现考试的时候太naive忽视了最暴力最直观的解法。

插入一条线段，相当于在树上不在这个线段上的点都插入一个值。而线段可以轻松剖分成logN个区间，那么取补集，可以同样转化为logN个区间。那么再套上一个树套树（一个树可以用stl）就能直接修改了。

这种方法最慢的测试点是1.6秒，而TL是2秒。因为树链剖分的常数特别小才能通过，如果是前面的3个树套在一起肯定就过不了了。

该方法代码如下：

/*
* @Author: 逸闲
* @Date:   2016-04-19 15:24:06
* @Last Modified by:   逸闲
* @Last Modified time: 2016-04-19 16:12:03
*/

#include "cstdio"
#include "cstdlib"
#include "iostream"
#include "algorithm"
#include "cstring"
#include "queue"

using namespace std;

#define INF 0x3F3F3F3F
#define MAX_SIZE 200005
#define Eps
#define Mod
#define Get(x, a) (x ? x -> a : 0)
#define L(i) (i ? Mid + 1 : Left)
#define R(i) (i ? Right : Mid)
#define Travel(x) for(typeof(x.begin()) it = x.begin(); it != x.end(); ++it)

inline int Get_Int()
{
	int Num = 0, Flag = 1;
	char ch;
	do
	{
		ch = getchar();
		if(ch == '-')
			Flag = -Flag;
	}
	while(ch < '0' || ch > '9');
	do
	{
		Num = Num * 10 + ch - '0';
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9');
	return Num * Flag;
}

class Heap
{
public:
	priority_queue<int> Exist, Deleted;

	inline void Push(int Value)
	{
		Exist.push(Value);
	}

	inline void Erase(int Value)
	{
		Deleted.push(Value);
	}

	inline int Top()
	{
		while(!Deleted.empty() && Exist.top() == Deleted.top())
		{
			Exist.pop();
			Deleted.pop();
		}
		if(Exist.empty())
			return -1;
		else
			return Exist.top();
	}
};

namespace Segment_Tree
{
	Heap Max[MAX_SIZE * 4];

	void Modify(int Now, int left, int right, int Value, int Flag, int Left, int Right)
	{
		if(left == Left && right == Right)
		{
			if(!Flag)
				Max[Now].Push(Value);
			else
				Max[Now].Erase(Value);
			return;
		}
		int Mid = Left + Right >> 1;
		if(left > Mid || right <= Mid)
		{
			int i = left > Mid;
			Modify(Now << 1 | i, left, right, Value, Flag, L(i), R(i));
			return;
		}
		Modify(Now << 1, left, Mid, Value, Flag, L(0), R(0));
		Modify(Now << 1 | 1, Mid + 1, right, Value, Flag, L(1), R(1));
	}

	int Query(int Now, int Position, int Left, int Right)
	{
		int Ans = Max[Now].Top();
		if(Left != Right)
		{
			int Mid = Left + Right >> 1, i = Position > Mid;
			Ans = max(Ans, Query(Now << 1 | i, Position, L(i), R(i)));
		}
		return Ans;
	}
}

class Edge
{
public:
	int To, Next;
}Edges[MAX_SIZE * 2];

int N, Q, Total;
int Front[MAX_SIZE], A[MAX_SIZE], B[MAX_SIZE], C[MAX_SIZE];

inline void Add_Edge(int From, int To)
{
	Edges[++Total].To = To;
	Edges[Total].Next = Front[From];
	Front[From] = Total;
}

inline void Add_Edges(int From, int To)
{
	Add_Edge(From, To);
	Add_Edge(To, From);
}

vector< pair<int, int> > temp;

namespace Heavy_Light_Decomposition
{
	int Total;
	int Father[MAX_SIZE], Size[MAX_SIZE], Son[MAX_SIZE], Top[MAX_SIZE], DFN[MAX_SIZE], Position[MAX_SIZE], Depth[MAX_SIZE];

	void DFS1(int Now)
	{
		Size[Now] = 1;
		Depth[Now] = Depth[Father[Now]] + 1;
		for(int i = Front[Now]; i; i = Edges[i].Next)
			if(Edges[i].To != Father[Now])
			{
				Father[Edges[i].To] = Now;
				DFS1(Edges[i].To);
				if(Size[Edges[i].To] > Size[Son[Now]])
					Son[Now] = Edges[i].To;
				Size[Now] += Size[Edges[i].To];
			}
	}

	void DFS2(int Now, int top)
	{
		Top[Now] = top;
		DFN[Now] = ++Total;
		Position[Total] = Now;
		if(Son[Now])
			DFS2(Son[Now], top);
		for(int i = Front[Now]; i; i = Edges[i].Next)
			if(Edges[i].To != Father[Now] && Edges[i].To != Son[Now])
				DFS2(Edges[i].To, Edges[i].To);
	}

	inline void Build()
	{
		DFS1(1);
		DFS2(1, 1);
	}

	inline void Get_Interval(int x, int y)
	{
		while(Top[x] != Top[y])
		{
			if(Depth[Top[x]] < Depth[Top[y]])
				swap(x, y);
			temp.push_back(make_pair(DFN[Top[x]], DFN[x]));
			x = Father[Top[x]];
		}
		if(Depth[x] < Depth[y])
			swap(x, y);
		temp.push_back(make_pair(DFN[y], DFN[x]));
	}
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("network.in", "r", stdin);
	freopen("network.out", "w", stdout);
#endif
	cin >> N >> Q;
	for(int i = 1; i < N; ++i)
		Add_Edges(Get_Int(), Get_Int());
	Heavy_Light_Decomposition::Build();
	for(int i = 1; i <= Q; ++i)
	{
		int Op = Get_Int();
		if(Op == 2)
			printf("%d\n", Segment_Tree::Query(1, Heavy_Light_Decomposition::DFN[Get_Int()], 1, N));
		else
		{
			int x, y, v;
			if(Op == 0)
			{
				A[i] = x = Get_Int();
				B[i] = y = Get_Int();
				C[i] = v = Get_Int();
			}
			else
			{
				int k = Get_Int();
				x = A[k];
				y = B[k];
				v = C[k];
			}
			temp.clear();
			Heavy_Light_Decomposition::Get_Interval(x, y);
			sort(temp.begin(), temp.end());
			int Last = 1;
			Travel(temp)
			{
				if(it -> first > Last)
					Segment_Tree::Modify(1, Last, it -> first - 1, v, Op, 1, N);
				Last = it -> second + 1;
			}
			if(Last <= N)
				Segment_Tree::Modify(1, Last, N, v, Op, 1, N);
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
           

PS：HLD好叼啊