「NOI2018」归程 - 可持久化并查集

Description

给出一个$n$个点$m$条边的无向连通图，每条边有长度和海拔。$q$次询问，每次给出一个水位线$p$ ，和一个节点$v$，询问从$v$节点开始，经过一段连续的海拔大于$p$的边后，到1号节点的最短路（前缀海拔大于$p$的边不算贡献）

Constraints

$n \leq 200000$

$m, q \leq 400000$

强制在线

Solution

考场上调了一个上午，最后居然还因为数组开小RE两个点，我还是太弱了

显然对于一个点，答案就是它所在的海拔大于$p$的联通块中$dis_i$(表示从1号点的最短路)最小的一个

如果不强制在线的话，我们只需要先跑一遍最短路，然后将询问按$p$排序，用并查集维护联通块和答案即可

如果强制在线，则需要使用可持久化并查集

可持久化并查集实际上就是用主席树来维护可持久化数组（$fa[]$和$ans[]$）

然后就能通过此题了

Code(5KB)

#include <bits/stdc++.h>

#define x first
#define y second
#define x1 X1 
#define x2 X2
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}

inline int read ()
{
	int sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
	return sum * fl;
}

const int Maxn = 300000 + 100, Maxm = 900000 + 100;

int N, M, QQ, K, S, e, Begin[Maxn], To[Maxm], Next[Maxm], W[Maxm], H[Maxm];

inline void Init()
{
	e = 0;
	memset(Begin, 0, sizeof Begin);
}

inline void add_edge (int x, int y, int l, int a)
{
	To[++e] = y;
	Next[e] = Begin[x];
	Begin[x] = e;
	W[e] = l;
	H[e] = a;
}

int Vis[Maxn], Dis[Maxn];

struct node
{
	int a, b;
	bool operator < (const node &x) const { return x.b < b; }
};

inline void Dijkstra()
{
	static priority_queue <node> Q;
	for (int i = 0; i <= N; ++i) Dis[i] = -1, Vis[i] = 0;
	Dis[1] = 0;
	Q.push((node){1, 0});
	while (!Q.empty())
	{
		node tmp = Q.top(); Q.pop();
		int x = tmp.a;
		if (Vis[x]) continue;
		Vis[x] = 1;
		for (int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];
			if (Dis[y] > Dis[x] + W[i] || Dis[y] == -1)
			{
				Dis[y] = Dis[x] + W[i];
				Q.push((node){y, Dis[y]});
			}
		}
	}
}

int HH[Maxm];
struct edge
{
	int x, y, z, h;
}A[Maxm];

inline int cmp1 (int a, int b)
{
	return a > b;
}
inline int cmp2 (edge a, edge b)
{
	return a.h > b.h;
}

int Root[Maxm][2], fa[Maxn], Cnt;

namespace SEG
{
	struct tree
	{
		int lson[2], rson[2], val, fa;
	}Tree[Maxn * 30];

	inline void build (int &root, int l, int r, int op)
	{
		root = ++ Cnt;
		if (l == r)
		{
			if (!op) Tree[root].fa = l;
			else Tree[root].val = Dis[l];
			return ;
		}
		int mid = (l + r) >> 1;
		build (Tree[root].lson[op], l, mid, op);
		build (Tree[root].rson[op], mid + 1, r, op);
	}

	inline void insert (int pre, int &now, int l, int r, int x, int d, int op)
	{
		//if (!now)
		{
			now = ++ Cnt;
			Tree[now].lson[op] = Tree[pre].lson[op];
			Tree[now].rson[op] = Tree[pre].rson[op];
		}
		if (l == r)
		{
			if (!op) Tree[now].fa = d;
			else Tree[now].val = d;
			return ;
		}
		int mid = (l + r) >> 1;
		if (x <= mid) insert (Tree[pre].lson[op], Tree[now].lson[op], l, mid, x, d, op);
		else insert (Tree[pre].rson[op], Tree[now].rson[op], mid + 1, r, x, d, op);
	}

	inline int query (int root, int l, int r, int x, int op)
	{
		if (l == r)
		{
			if (!op) return Tree[root].fa;
			return Tree[root].val;
		}
		int mid = (l + r) >> 1;
		if (x <= mid) return query (Tree[root].lson[op], l, mid, x, op);
		else return query (Tree[root].rson[op], mid + 1, r, x, op);
	}

	inline int find (int root, int x)
	{
		int f = query (root, 1, N, x, 0);
		return f == x ? x : find(root, f);
	}
}

int size[Maxn];

inline int find (int x)
{
	return fa[x] == x ? x : find(fa[x]);
}

inline void Link (int x, int y, int id)
{
	int fx = find(x), fy = find(y);
	if (fx == fy)
		return ;
	//	cout<<x<<" "<<y<<"| "<<fx<<" "<<fy<<" | "<<id<<endl;
	if (size[fx] < size[fy]) swap(fx, fy);
	size[fx] += size[fy];
	fa[fy] = fx;
	SEG :: insert (Root[id - 1][0], Root[id][0], 1, N, fy, fx, 0);
	if (Dis[fy] < Dis[fx])
	{
		Dis[fx] = Dis[fy];
		SEG :: insert (Root[id - 1][1], Root[id][1], 1, N, fx, Dis[fy], 1);
	}
}

int Pos[Maxm];

main()
{
	freopen("return.in", "r", stdin);
	freopen("return.out", "w", stdout);
	int T = read();
	while (T--)
	{
		Init();
		memset(SEG :: Tree, 0, sizeof SEG :: Tree);
		memset(Root, 0, sizeof Root);
		Cnt = 0;
		N = read(), M = read();
		for (int i = 1; i <= M; ++i)
		{
			int x = read(), y = read(), l = read(), a = read();
			A[i] = ((edge){x, y, l, a});
			HH[i] = a;
			add_edge (x, y, l, a);
			add_edge (y, x, l, a);
		}
		Dijkstra();
		sort(HH + 1, HH + M + 1, cmp1); sort(A + 1, A + M + 1, cmp2);
		int tot = unique(HH + 1, HH + M + 1) - HH - 1;
		int MIN = HH[tot];
		HH[++tot] = -0x3f3f3f3f;
		for (int i = 1; i <= N; ++i) fa[i] = i, size[i] = 1;
		SEG :: build (Root[0][0], 1, N, 0);
		SEG :: build (Root[0][1], 1, N, 1);
		int j = 1;
		Pos[1] = 0;
		for (int i = 1; i <= M; ++i)
		{
			Root[i][0] = Root[i - 1][0];
			Root[i][1] = Root[i - 1][1];
			Link(A[i].x, A[i].y, i);
			if (HH[j] != A[i].h) ++j;
			Pos[j + 1] = i;
		}
		for (int i = 1; i <= tot; ++i) HH[i] = -HH[i];
		QQ = read(), K = read(), S = read();
		int ans = 0;
		while (QQ--)
		{
			int v = read(), p = read();
			v = (v + K * ans - 1) % N + 1;
			p = (p + K * ans) % (S + 1);
			if (p < MIN)
				ans = 0;
			else
			{
				p = -p;
				int pos = lower_bound(HH + 1, HH + tot + 1, p) - HH;
				pos = Pos[pos];
				ans = SEG :: query (Root[pos][1], 1, N, SEG :: find (Root[pos][0], v), 1);
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}