[蓝桥杯 2022 省 A] 推导部分和

[蓝桥杯 2022 省 A] 推导部分和

题目描述

对于一个长度为 $N$ 的整数数列 $A_1,A_2,\cdots A_N$，小蓝想知道下标 $l$ 到 $r$ 的部分和 $\sum _{i=l}^r{A}_i=A_l+A_{l+1}+\cdots +A_r$ 是多少?

然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 $M$ 个部分和的值。其中第 $i$ 个部分和是下标 $l_i$ 到 $r_i$ 的部分和 ${\sum }_{j=l_i}^{r_i}=A_{l_i}+A_{l_i+1}+\cdots +A_{r_i}$, 值是 $S_i$ 。

输入格式

第一行包含 3 个整数 $N、M$ 和 $Q$。分别代表数组长度、已知的部分和数量 和询问的部分和数量。

接下来 $M$ 行，每行包含 $3$ 个整数 $l_i,r_i,S_i$。

接下来 $Q$ 行，每行包含 $2$ 个整数 $l$ 和 $r$，代表一个小蓝想知道的部分和。

输出格式

对于每个询问, 输出一行包含一个整数表示答案。如果答案无法确定, 输出 UNKNOWN。

样例 #1

样例输入 #1

5 3 3
1 5 15
4 5 9
2 3 5
1 5
1 3
1 2
1
2
3
4
5
6
7

样例输出 #1

15
6
UNKNOWN
1
2
3

提示

对于 $10\%$ 的评测用例, $1\le N,M,Q\le 10,-100\le S_i\le 100$ 。

对于 $20\%$ 的评测用例, $1\le N,M,Q\le 20,-1000\le S_i\le 1000$ 。

对于 $30\%$ 的评测用例, $1\le N,M,Q\le 50,-10000\le S_i\le 10000$ 。

对于 $40\%$ 的评测用例, $1\le N,M,Q\le 1000,-10^6\le S_i\le 10^6$ 。

对于 $60\%$ 的评测用例, $1\le N,M,Q\le 10000,-10^9\le S_i\le 10^9$ 。

对于所有评测用例, $1\le N,M,Q\le 10^5,-10^{12}\le S_i\le 10^{12},1\le l_i\le r_i\le N$, $1\le l\le r\le N$ 。数据保证没有矛盾。

蓝桥杯 2022 省赛 A 组 J 题。

---

分析：

居然是一道图论建模题。。
对于一个部分和的关系，利用前缀和的思想，我们可以理解为是：
$s[r]-s[l-1]=v$
其实类比差分约束的思想就是让$l-1$到$r$之间连一条长度为v的边
$(l-1,r,v),(r,l-1,-v)$
建完边之后各个部分和之间的关系也就一目了然了
接下来我们只需要利用$DFS$或者$BFS$遍历这张图，用并查集将具有相同标准的前缀和放在一个块里（一个快里面的任何数都可以作为标准），在一个块里的任何两个数我们都能知道他们之间的部分和

---

Code

#include
using namespace std;

#define int long long

const int N = 2e5+100;
int n,m,q;
int Hom[N],cnt = 0;
bool vi[N];
struct Node{
	int y,Next,v;
}e[2*N];
int Linkk[N] , len;
int s[N];
int fa[N];

void Insert(int x,int y,int v){
	e[++len] = (Node){y,Linkk[x],v};
	Linkk[x] = len;
}

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

void Dfs(int x,int vv){
	vi[x] = 1;
	s[x] = vv;
	for (int i = Linkk[x]; i; i = e[i].Next){
		int y = e[i].y;
		if (vi[y]) continue;
		fa[Getfa(y)] = Getfa(x);
		Dfs(y,vv+e[i].v);
	}
}

signed main(){
	scanf("%lld %lld %lld",&n,&m,&q);
	for (int i = 1,x,y,v; i <= m; i++)
	  cin>>x>>y>>v,Insert(x-1,y,v),Insert(y,x-1,-v);
	for (int i = 0; i <= n; i++) fa[i] = i;
	for (int i = 0; i <= n; i++)
	  if (!vi[i]) Dfs(i,0);
	for (int i = 1; i <= q; i++){
		int l,r;
		cin>>l>>r;
		if (Getfa(l-1)!=Getfa(r)) {cout<<"UNKNOWN"<<endl;continue;}
		printf("%lld\n",s[r]-s[l-1]);
	}
	return 0;
}
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
41
42
43
44
45
46
47
48
49
50
51