看思路前需要搞懂的几件事
根据前缀和的思想,a[l] + a[l+1] + … a[r] = s[r] - s[l-1], 因此 l - 1 和 r 为关键信息。
若给出多组区间 l1_r1, l2_r2 … ln_rn ,对于两个区间只要一端端点相同,就可以更新一段新的信息。比如知道3,5 和 1,3 的区间和就可以知道1,5的区间和 或者 知道 1,3 和 1, 2 就可以知道2,3的。
可能出现两组以上区间端点相同的情形(如1,2和2,3和3,5)此时用并查集维护。
将有端点重合的区间放在同一个集合,从集合中选取一个参考点,那么任意端点相对于参考点的距离都可以通过BFS求得。
样例和解释
5 3 3
1 5 15
4 5 9
2 3 5
1 5
1 3
1 21 5 15 相当于知道 s[5] - s[0] = 15
4 5 9 相当于知道 s[5] - s[3] = 9
2 3 5 相当于知道 s[3] - s[1] = 5输出
15
6
UNKNOWN
思路
邻接表存储区间左右端点和数值
并查集维护区间集合
bfs求的每个集合相对于参考点的距离
查询
不在同一集合的两个点区间距离无法查询
在同一个集合的距离等于相对参考点的距离之差
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 2e5 + 10; // 点数不超1e5, 但要考虑边数
typedef long long LL;
int p[N], q[N];
int h[N], e[N], ne[N], idx;
LL w[N], s[N];
bool vis[N];
int n, m, k;
void add(int a, int b, LL c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int find(int x)
{
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
void unite(int x, int y)
{
p[find(x)] = find(y);
}
void bfs(int x)
{
int hh = 0, tt = -1;
q[++tt] = x;
vis[x] = true;
while (hh <= tt)
{
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (vis[j]) continue;
s[j] = s[t] + w[i]; // j到x的相对距离为 t相对于x的距离加 边权
q[++tt] = j;
}
vis[t] = true;
}
}
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) p[i] = i;
memset(h, -1, sizeof h);
while (m--) // 链式前向星存储邻接表
{
int a, b; LL c; cin >> a >> b >> c;
add(a-1, b, c); add(b, a-1, -c); // 双向边,编号从小到大则正,反之为负
unite(a - 1, b); // 合并集合
}
for (int i = 0; i <= n; i++) if (!vis[i]) bfs(i); // 遍历每个集合到参考点的距离
while (k--)
{
int l, r; cin >> l >> r;
if (find(l - 1) != find(r)) cout << "UNKNOWN" << endl; // l-1 和 r 不在同一个集合
else cout << s[r] - s[l - 1] << endl;
}
}
为什么不会超时
Orz
Orz
Orz
Orz
orz