web analytics

BZOJ1202 [HNOI2005]狡猾的商人 并查集

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1202

分析:

题目大概就是讲给你一些区间和。问你这些有没有冲突.

然而题目给的又那么少.所以很快应该想到前缀和,来解决问题.
好像又没有什么交集来解决问题。

所以这里可以用带权值并查集。

其中V[x]表示x这个点 到它所在联通块的距离.

对于任意给你的区间(x,y);
当x,y都在同一集合里我们只需要判断V[y]-V[x-1]?=Val;
当不在同一集合:

注意下面的x均已经处理成x-1.
p=Find(x),q=Find(y);
我们可以列出几个关系式:
V[x]=S[x]-S[p]
V[y]=S[y]-S[q]
Val=S[y]-S[x]

V[p]=S[p]-S[q]
V[p]=S[x]-V[x]-(S[y]-V[y])
V[p]=V[y]-V[x]+(S[x]-S[y])
V[p]=V[y]-V[x]-Val;

这样就可以并查集合并了.

Update:

又写了一遍.

Post a Comment

You must be logged in to post a comment.