BZOJ 1146 CTSC 2008 网络管理 Network 树链剖分+二分答案+平衡树

题目大意：有n个路由器，他们由n-1条边连接（形成一棵树）。每一个路由器有一个延时值。有两种操作：

1.查询树上x,y两点之间的路径上第k大的权值是多少

2.修改x位置的权值为y

思路：当我大概想到怎么做这个题的时候，所想的时间复杂度已经达到了O(nlog^4n)，偷偷的瞄了一眼数据范围...（N,Q<=80000，时限50s，小心翼翼的掏出计算器算了一下：8w * log(8w) ^  4 ≈ 56E，心中这样想着：Treap有常数，链剖常数大，二分不稳定的范围好像不止8w...评测机会不会很卡...代码一定很长吧...写出来不就T了么...哎...这个世界啊..然后默默的想关掉页面。这时候，一位学长站在我的后面，我向他倾诉了我的苦衷。他听了之后居然说：

“没事，写吧，我10多秒就过了。。。”

秒就过了。。。就过了。。。过了。。。了。。。。。。

还是正经点说说思路吧。树上路径，lca什么的要不倍增，要不树链剖分，带修改，只能用树链剖分。第k大，就是二分+平衡树，二分第k大是谁，然后压缩上下界。修改的时候要在每个包含这个节点的线段树中的线段中删除这个节点，然后加上要改成的点。

CODE：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 80010
#define LEFT (pos << 1)
#define RIGHT (pos << 1|1)
#define SIZE(a) (a == NULL ? 0:a->size)
using namespace std;

struct Complex{
	int val,random,size,cnt;
	Complex *son[2],*father;

	Complex(int _) {
		val = _;
		random = rand();
		size = cnt = 1;
		son[0] = son[1] = NULL;
	}
	int Compare(int x) {
		if(x == val)	return -1;
		return x > val;	
	}
	void Maintain() {
		size = cnt;
		if(son[0] != NULL)	size += son[0]->size;
		if(son[1] != NULL)	size += son[1]->size;
	}
}*root;

int points,asks;
int src[MAX];
int head[MAX],total;
int next[MAX << 1],aim[MAX << 1];

int deep[MAX],son[MAX],father[MAX];
int top[MAX],pos[MAX],temp[MAX],cnt;

Complex *tree[MAX << 2];

inline void Add(int x,int y);
int PreDFS(int x,int last);
void DFS(int x,int last,int _top);

void BuildTree(int l,int r,int pos);
void Modify(int l,int r,int x,int pos,int _,int __);
int Bisection(int x,int y,int k);
int Ask(int x,int y,int k);
int Ask(int l,int r,int x,int y,int pos,int k);

inline void Rotate(Complex *&a,bool dir);
void Insert(Complex *&a,int x);
void Delete(Complex *&a,int x);
int GetRank(Complex *a,int k);

int main()
{
	cin >> points >> asks;
	for(int i = 1;i <= points; ++i)
		scanf("%d",&src[i]);
	for(int x,y,i = 1;i < points; ++i) {
		scanf("%d%d",&x,&y);
		Add(x,y),Add(y,x);
	}
	PreDFS(1,0);
	DFS(1,0,1);
	BuildTree(1,cnt,1);
	for(int flag,x,y,i = 1;i <= asks; ++i) {
		scanf("%d%d%d",&flag,&x,&y);
		if(!flag) {
			Modify(1,cnt,pos[x],1,y,src[x]);
			src[x] = y;
		}
		else {
			int temp = Bisection(x,y,flag) - 1;
			if(temp == -1)	puts("invalid request!");
			else	printf("%d\n",temp);
		}
	}
	return 0;
}

inline void Add(int x,int y)
{
	next[++total] = head[x];
	aim[total] = y;
	head[x] = total;
}

int PreDFS(int x,int last)
{
	father[x] = last;
	deep[x] = deep[last] + 1;
	int max_size = 0,re = 1;
	for(int i = head[x];i;i = next[i]) {
		if(aim[i] == last)	continue;
		int temp = PreDFS(aim[i],x);
		re += temp;
		if(temp > max_size)
			son[x] = aim[i],max_size = temp;
	}
	return re;
}

void DFS(int x,int last,int _top)
{
	temp[++cnt] = src[x];
	pos[x] = cnt;
	top[x] = _top;
	if(son[x])	DFS(son[x],x,_top);
	for(int i = head[x];i;i = next[i]) {
		if(aim[i] == last || aim[i] == son[x])	continue;
		DFS(aim[i],x,aim[i]);
	}
}

void BuildTree(int l,int r,int pos)
{
	for(int i = l;i <= r; ++i)
		Insert(tree[pos],temp[i]);
	if(l == r)	return ;
	int mid = (l + r) >> 1;
	BuildTree(l,mid,LEFT);
	BuildTree(mid + 1,r,RIGHT);
}

void Modify(int l,int r,int x,int pos,int _,int __)
{
	Delete(tree[pos],__);
	Insert(tree[pos],_);
	if(l == r)	return ;
	int mid = (l + r) >> 1;
	if(x <= mid)	Modify(l,mid,x,LEFT,_,__);
	else	Modify(mid + 1,r,x,RIGHT,_,__);
}

int Bisection(int x,int y,int k)
{
	int l = 0,r = static_cast<int>(1e8),ans = 0;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(Ask(x,y,mid) >= k)
			l = mid + 1;
		else	r = mid - 1,ans = mid;
	}
	return ans;
}

int Ask(int x,int y,int k)
{
	int re = 0;
	while(top[x] != top[y]) {
		if(deep[top[x]] < deep[top[y]])
			swap(x,y);
		re += Ask(1,cnt,pos[top[x]],pos[x],1,k);
	x = father[top[x]];
	}	
	if(deep[x] > deep[y])	swap(x,y);
	re += Ask(1,cnt,pos[x],pos[y],1,k);
	return re;
}

int Ask(int l,int r,int x,int y,int pos,int k)
{
	if(l == x && r == y)	return GetRank(tree[pos],k);
	int mid = (l + r) >> 1;
	if(y <= mid)	return Ask(l,mid,x,y,LEFT,k);
	else if(x > mid)	return Ask(mid + 1,r,x,y,RIGHT,k);
	int left = Ask(l,mid,x,mid,LEFT,k);
	int right = Ask(mid + 1,r,mid + 1,y,RIGHT,k);
	return left + right;
}

inline void Rotate(Complex *&a,bool dir)
{
	Complex *k = a->son[!dir];
	a->son[!dir] = k->son[dir];
	k->son[dir] = a;
	a->Maintain(),k->Maintain();
	a = k;
}

void Insert(Complex *&a,int x)
{
	if(a == NULL) {
		a = new Complex(x);
		return ;
	}
	int dir = a->Compare(x);
	if(dir == -1)
		a->cnt++;
	else {
		Insert(a->son[dir],x);
		if(a->son[dir]->random > a->random)
			Rotate(a,!dir);
	}
	a->Maintain();
}

void Delete(Complex *&a,int x)
{
	int dir = a->Compare(x);
	if(dir != -1)
		Delete(a->son[dir],x);
	else {
		if(a->cnt > 1)
			--a->cnt;
		else {
			if(a->son[0] == NULL)	a = a->son[1];
			else if(a->son[1] == NULL)	a = a->son[0];
			else {
				bool _ = (a->son[0]->random > a->son[1]->random);
				Rotate(a,_);
				Delete(a->son[_],x);
			}
		}
	}
	if(a != NULL)	a->Maintain();
}

int GetRank(Complex *a,int k)
{
	if(a == NULL)	return 0;
	if(k > a->val)	return GetRank(a->son[1],k);
	if(k == a->val)	return a->cnt + GetRank(a->son[1],k);
	return SIZE(a->son[1]) + a->cnt + GetRank(a->son[0],k);
}