题目描述
给定一个长度为 $n$ 的未知序列 ${a_i}$，已知 $m$ 个条件 $l_i, r_i,S_i$，表示 $a_{l_i}+a_{l_i + 1}+\dots +a_{r_i}$ 的和为 $S_i$，要实现 $q$ 次询问，每次询问 $a_l+a_{l+1}+\dots +a_r$ 的值，若无解则输出 UNKNOWN。
算法分析
将区间和拆成前缀和，每一个条件相当于告诉我们，一旦知道 $l_i-1$ 和 $r_i$ 中任何一个下标的前缀和，另一个下标的前缀和也能够得到，这个二元关系可以使用带权并查集来维护，每个点记录它到父节点的区间和，若 $l-1$ 与 $r$ 不连通则说明无解。
某辣鸡网站有锅，交两次相同代码一次 TLE 一次 AC。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| import java.io.*;
import java.util.*;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static int[] fa; static long[] val;
static int find(int x) {
int rt = x; ArrayList<Integer> arr = new ArrayList<>();
while(fa[rt] != rt) { arr.add(rt); rt = fa[rt]; }
for(int i = arr.size() - 1; i >= 0; --i) {
x = arr.get(i);
val[x] += val[fa[x]];
fa[x] = rt;
}
return rt;
}
public static void main(String[] args) throws IOException {
String s = in.readLine(); String[] ss = s.split(" ");
int n = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]), q = Integer.parseInt(ss[2]);
fa = new int[n + 1]; val = new long[n + 1];
for(int i = 0; i <= n; ++i) { fa[i] = i; val[i] = 0; }
while((m--) > 0) {
s = in.readLine(); ss = s.split(" ");
int l = Integer.parseInt(ss[0]), r = Integer.parseInt(ss[1]); long S = Long.parseLong(ss[2]);
int x = find(l - 1), y = find(r);
if(x != y) {
val[y] = val[l - 1] + S - val[r];
fa[y] = x;
}
}
while((q--) > 0) {
s = in.readLine(); ss = s.split(" ");
int l = Integer.parseInt(ss[0]), r = Integer.parseInt(ss[1]);
int x = find(l - 1), y = find(r);
if(x != y) out.write("UNKNOWN\n");
else out.write(String.format("%d\n", val[r] - val[l - 1]));
}
out.flush();
}
}
|