[UOJ#274][清华集训2016]温暖会指引我们前行

[UOJ#274][清华集训2016]温暖会指引我们前行

试题描述

寒冬又一次肆虐了北国大地

无情的北风穿透了人们御寒的衣物

可怜虫们在冬夜中发出无助的哀嚎

“冻死宝宝了！”

这时

远处的天边出现了一位火焰之神

“我将赐予你们温暖和希望！”

只见他的身体中喷射出火焰之力

通过坚固的钢铁，传遍了千家万户

这时，只听见人们欢呼

“暖气来啦！”

任务描述

虽然小R住的宿舍楼早已来了暖气，但是由于某些原因，宿舍楼中的某些窗户仍然开着（例如厕所的窗户），这就使得宿舍楼中有一些路上的温度还是很低。

小R的宿舍楼中有n个地点和一些路，一条路连接了两个地点，小R可以通过这条路从其中任意一个地点到达另外一个地点。但在刚开始，小R还不熟悉宿舍楼中的任何一条路，所以他会慢慢地发现这些路，他在发现一条路时还会知道这条路的温度和长度。每条路的温度都是互不相同的。

小R需要在宿舍楼中活动，每次他都需要从一个地点到达另一个地点。小R希望每次活动时经过一条最温暖的路径，最温暖的路径的定义为，将路径上各条路的温度从小到大排序后字典序最大。即温度最低的路温度尽量高，在满足该条件的情况下，温度第二低的路温度尽量高，以此类推。小R不会经过重复的路。由于每条路的温度互不相同，因此只存在一条最温暖的路径。

对于小R的每次活动，你需要求出小R需要走过的路径总长度。如果小R通过当前发现的路不能完成这次活动，则输出 −1。

注意本题中的字典序与传统意义上的字典序定义有所不同，对于两个序列a,b(a≠b)，若a是b的前缀则a的字典序较大，同时可以推出空串的字典序最大。

输入

第一行两个正整数 n,m。表示小R的宿舍楼中有 n 个地点，共发生了 m 个事件。

接下来 m 行，每行描述一个事件，事件分为三类。

1. find id u v t l 表示小R发现了一条连接u和v之间的路，编号为id。相同id的边只会出现一次。

2. move u v 表示小R要从u到达v，你需要计算出最温暖的路径的长度 ，若不能从u到达v，则输出−1。

3. change id l 表示从u到v这条边的长度变为了l（保证在当前时间点这条边存在）。

输出

对于每个询问，输出一行整数，表示最温暖的路径长度。

输入示例

find

find

find

find

move

move

find

move

change

find

find

move

find

move

find

move

move

move

move  

输出示例

-

数据规模及约定

对于find操作：(0≤id<m,0≤u,v<n,u≠v,0≤t≤1000000000,0≤l≤10000)；

对于move操作：(0≤u,v<n)；

对于change操作：(0≤l≤10000)。

对于100%的数据，1≤n≤100000,1≤m≤300000。

题解

维护最大生成树，裸的 LCT。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

using namespace std;

int read() {

	int x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 100010

#define maxq 300010

#define maxnode 400010

#define oo 2147483647

struct Node {

	int t, l, mnid, sum;

	bool rev;

	Node(): rev(0) {}

	Node(int t, int l): t(t), l(l) {}

} ns[maxnode];

int fa[maxnode], ch[maxnode][2], S[maxnode], top;

bool isrt(int u) { return !fa[u] || (ch[fa[u]][0] != u && ch[fa[u]][1] != u); }

void maintain(int o) {

	ns[o].mnid = o; ns[o].sum = ns[o].l;

	for(int i = 0; i < 2; i++) if(ch[o][i]) {

		int son = ns[ch[o][i]].mnid, &me = ns[o].mnid;

		if(ns[son].t < ns[me].t) me = son;

		ns[o].sum += ns[ch[o][i]].sum;

	}

	return ;

}

void pushdown(int o) {

	if(!ns[o].rev) return ;

	swap(ch[o][0], ch[o][1]);

	for(int i = 0; i < 2; i++) if(ch[o][i])

		ns[ch[o][i]].rev ^= 1;

	ns[o].rev = 0;

	return ;

}

void rotate(int u) {

	int y = fa[u], z = fa[y], l = 0, r = 1;

	if(!isrt(y)) ch[z][ch[z][1]==y] = u;

	if(ch[y][1] == u) swap(l, r);

	fa[u] = z; fa[y] = u; fa[ch[u][r]] = y;

	ch[y][l] = ch[u][r]; ch[u][r] = y;

	maintain(y); maintain(u);

	return ;

}

void splay(int u) {

	int t = u; S[top = 1] = t;

	while(!isrt(t)) S[++top] = fa[t], t = fa[t];

	while(top) pushdown(S[top--]);

	while(!isrt(u)) {

		int y = fa[u], z = fa[y];

		if(!isrt(y)) {

			if(ch[y][0] == u ^ ch[z][0] == y) rotate(u);

			else rotate(y);

		}

		rotate(u);

	}

	return ;

}

void access(int u) {

	splay(u); ch[u][1] = 0; maintain(u);

	while(fa[u]) splay(fa[u]), ch[fa[u]][1] = u, maintain(fa[u]), splay(u);

	return ;

}

void makeroot(int u) {

	access(u); ns[u].rev ^= 1;

	return ;

}

void link(int a, int b) {

	makeroot(b); fa[b] = a;

	return ;

}

void cut(int a, int b) {

	makeroot(a); access(b); ch[b][0] = fa[a] = 0; maintain(b);

	return ;

}

int _mnid, _sum;

void query(int a, int b) {

	makeroot(a); access(b);

	_mnid = ns[b].mnid; _sum = ns[b].sum;

	return ;

}

struct Edge {

	int u, v;

	Edge() {}

	Edge(int _, int __): u(_), v(__) {}

} es[maxq];

int pa[maxn];

int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }

int main() {

	int n = read(), q = read();

	for(int i = 1; i <= n; i++) ns[i] = Node(oo, 0), pa[i] = i;

	char cmd[10];

	while(q--) {

		scanf("%s", cmd);

		if(!strcmp(cmd, "find")) {

			int id = read() + n + 1, u = read() + 1, v = read() + 1, t = read(), l = read();

			ns[id] = Node(t, l); es[id-n-1] = Edge(u, v);

			int U = findset(u), V = findset(v);

			if(U == V) {

				query(u, v);

				if(ns[_mnid].t < t) {

					cut(es[_mnid-n-1].u, _mnid);

					cut(_mnid, es[_mnid-n-1].v);

					link(u, id); link(id, v);

				}

			}

			else {

				pa[V] = U;

				link(u, id); link(id, v);

			}

		}

		if(!strcmp(cmd, "move")) {

			int u = read() + 1, v = read() + 1;

			if(findset(u) == findset(v)) query(u, v), printf("%d\n", _sum);

			else puts("-1");

		}

		if(!strcmp(cmd, "change")) {

			int id = read() + n + 1, l = read();

			access(id); ns[id].l = l; maintain(id);

		}

	}

	return 0;

}