专业型网站和个人网站,长春商城网站开发,建个视频网站多少钱,老榕树网站建设推导部分和 2024-12-11 蓝桥杯每日一题 推导部分和 带权并查集 题目大意 对于一个长度为 ( N ) 的整数数列 A 1 , A 2 , ⋯ , A N A_1, A_2, \cdots, A_N A1,A2,⋯,AN #xff0c;小蓝想知道下标 ( l ) 到 ( r ) 的部分和 ∑ i l r A i A l A l 1 ⋯ A r \sum_{…推导部分和 2024-12-11 蓝桥杯每日一题 推导部分和 带权并查集 题目大意 对于一个长度为 ( N ) 的整数数列 A 1 , A 2 , ⋯ , A N A_1, A_2, \cdots, A_N A1,A2,⋯,AN 小蓝想知道下标 ( l ) 到 ( r ) 的部分和 ∑ i l r A i A l A l 1 ⋯ A r \sum_{il}^r A_i A_l A_{l1} \cdots A_r ∑ilrAiAlAl1⋯Ar 是多少 然而小蓝并不知道数列中每个数的值是多少他只知道它的 ( M ) 个部分和的值。其中第 ( i ) 个部分和是下标 l i l_i li 到 r i r_i ri 的部分和 ∑ j l i r i A j A l i A l i 1 ⋯ A r i \sum_{jl_i}^{r_i} A_j A_{l_i} A_{l_i1} \cdots A_{r_i} ∑jliriAjAliAli1⋯Ari值是 S i S_i Si。 解题思路 这个题的思维难度有点大但是实现来很容易只要理解带权并查集这一概念即可。 先看这个权值是怎么带上的d 数组就是代表每一个值到根节点的一个距离然而当 l 和 r在同一个连通块中的时候之间的距离就是 d[r] - d[l-1] 的值。 每一个连通块代表着是那些可以通过边界值相连的区间的总和在合并的过程中会发生如下图的数值变化如图所示 d[l-1] 的值将会在find函数中通过更新父节点的时候更新成 l-1 到 根节点的距离这时候显然l 和 r 之间的距离就是d[r] - d[l-1] Accepted
#include iostreamusing namespace std;const int N 100010;
typedef long long ll;
ll n,m,q;
ll d[N],p[N];ll find(int x) {if(p[x] ! x) {int t find(p[x]);d[x] d[p[x]];p[x] t;}return p[x];
}int main() {cinnmq;for(int i 1;i n;i) p[i] i;ll l,r,s;while(m--) {cinlrs;ll pl find(l-1),pr find(r);// 直接合并p[pl] pr;d[pl] d[r] - d[l-1] - s;}while(q--) {cinlr;ll pl find(l-1),pr find(r);if(pl ! pr) coutUNKNOWNendl;else coutd[r] - d[l-1]endl;}return 0;
}思考 这个题的思维难度确实高主要就是带权并查集的使用得多想想。 备注 想要一起备赛的同学可以评论区留言
