采用前缀和的思想对去求解区间和[l,r]的值为d[r] - d[l - 1]
对于任意一组l,r可以采用让l - 1 -> r(连边), 权值就为s
在后续查询结果, 我们可以通过查询l-1和r是否可以连通来判断连通就可以得出答案, 结果就是边权和,
因此这是可以采用建图的方式搜索结点解决
但是普通图论对于数据量大的情况下可能会超时, 对于集合判断是否在同一集合联想到并查集,
维护边权可以采用带权并查集
定义d[x]为x + 1到祖节点的距离也就是[x + 1, px]的区间和
对于求解[l,r]的区间和
先判断是否在同一集合中如果不在就不能得出答案
否则有d[l - 1] = S[l, px], d[r] = S[r, px] ==> S[l, r] = d[l - 1] - d[r]
对于并查集中的操作:
通用套路:借助父节点来更新到祖节点的距离
static int find(int x) {
if (p[x] != x) {
int t = find(p[x]);
d[x] = d[x] + d[p[x]];
p[x] = t;
}
return p[x];
}
并查集合并操作
int pr = find(r)
int pl = find(l - 1)
if (pl == pr) continue;
p[pl] = pr;
/*
l到根节点的距离为d[l - 1], r到根节点的距离为d[r], l到r的距离为s
那么l有两条路到pr
1. l先到pl再到pr, 路径:x = d[l - 1] + d[pl]
2. l先到r再到pr 路径:x = s + d[r]
则pl到pr的距离为d[pl] = s + d[r] - d[l - 1]
*/
d[pl] = s + d[r] - s[l - 1];
import java.util.*;
public class Main {
static final int N = 100010;
static int[] p = new int[N];
static long[] d = new long[N];
static int n, m, q;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
q = sc.nextInt();
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 1; i <= m; i++) {
int l = sc.nextInt(), r = sc.nextInt();
long s = sc.nextLong();
int pl = find(l - 1), pr = find(r);
if (pl == pr) continue;
p[pl] = pr;
d[pl] = s + d[r] - d[l - 1];
}
while (q-- > 0) {
int l = sc.nextInt(), r = sc.nextInt();
if (find(l - 1) == find(r)) {
/*
d[x]存储的是x + 1到px的区间和
因此求解l 到 r的和就是d[l - 1] - d[r]
按照前缀和的思想是d[r] - d[l - 1],这需要改变d数组的含义
改为d[x]表示x + 1到px的权值的负数
那么公式就变为
x = d[l - 1] + d[pl]
x = -s + d[r]
也就是d[pl] = d[r] - d[l - 1] - s;
*/
System.out.println(d[l - 1] - d[r]);
} else System.out.println("UNKNOWN");
}
}
static int find(int x) {
if (p[x] != x) {
int t = find(p[x]);
d[x] = d[x] + d[p[x]];
p[x] = t;
}
return p[x];
}
}