lly的数列询问
Description
这个问题很简单，lly lly lly给你一些提示，让你试着确定长度为n n n的数列A [1] A [2] ... A [n]的值，但是他想尽一切办法为大家降低难度：
因此lly lly lly会给定一些对你有用的m m m询问，每次询问lly lly lly会表明L，R，sum[L，R] L，R，sum [L，R] L，R，sum[L，R]：表示区间[L，R]的区间和（保证询问合法），让大家更好的解决这个问题，但是对于每个询问会有一个代价，代价就是（R−L）∗sum[L，R]（R-L）* sum [L，R] （R−L）∗sum[L，R]。
那么问题就转化了，如何花费尽可能小的代价确定这个数列。
Input
输入第一行包括两个整数n,m(1≤n≤2∗105,0≤m≤5∗105)n,m(1 \leq n \leq 2*10^5,0 \leq m \leq 5*10^5)n,m(1≤n≤2∗105,0≤m≤5∗105)。
接下来有mmm行，每行包括三个整数,L,R,sum[L,R],(1≤L≤R≤n,sum[L,R]≤109)L,R,sum[L,R],(1 \leq L \leq R \leq n,sum[L,R] \leq 10^9)L,R,sum[L,R],(1≤L≤R≤n,sum[L,R]≤109)。
Output
输出包含一个整数，即最小花费，如果无论如何都无法确定这个数列就输出“lly tcl!”。
Sample Input 1
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
Sample Output 1
11
Sample Input 2
4 3
1 2 2
2 3 3
1 1 1
Sample Output 2
lly tcl!
Source
nuoyanli
思路
题意：给我们一个长度为 n 的序列，但是我们不知道的它的元素是什么，之后给我们m个是提示，每次提示 给我一个们一个[L, R]区间 的元素和sum[L~R]，每次提示有一个 最小的花费 (R−L)∗sum[L..R](R-L)*sum[L ..R](R−L)∗sum[L..R],问我们找出序列的n个元素是啥，需要的总共的最小花费是多少？
分析：这题真实令人脑洞大开，对于这种区间元素是啥的题竟然可以转化成求 最小生成树 的问题（可惜本巨弱竟毫无察觉 ），对于这一题要求出序列的n个元素是啥？就等价于求出每个位置的前缀和 sum[ i ] ,我们已知 sum[0] = 0, 如果对于序列中的1～n点都 0 点联通(应用最小生成树的地方)的话，那么我们就能够求出所有的 sum[i]，有了所有的sum[ i ] 之后我们通过相邻位置的前缀和相减就能够得到 n 个元素了，对于题目上的m次提示的条件我们就可以转化成 sum[R] - sum[L - 1], 以 L-1点 与R点之间建立一条 权值为 （R-L）* sum[L~R] 的边，这样根据m个条件建完图之后，用 Kruskal 或者 Prim 来跑一边最小生成树（在这个是时候我们要判断这个图能否全部连通），的出来的答案就是 总花费
最后举个例子来证明可行，例如 1-3 的区间和为sum[3] - sum[0], 4 - 6的区间和为sum[6] - sum[4], 我们可以看到 如果 0与6联通 那么区间和 sum[ 6 ] - sum[0] == sum[6] - 0, 而在我们将 1-3、4-6区间，对应的 0 - 3 - 6 （这样我们就使 0 与 6间接联通了）联通的时候，那么这条边的边权和是 (sum[6] - sum[3]) + ( sum[3] - sum[0]) = sum[6] + sum[0], 这样我们就可以得到了 sum[6] 的值了。。。。。。。。。。。。。。。。。
题解
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int Len = 5e5 + 10;
int n,m;
struct Edge
{
ll u,v,w;
bool operator < (const Edge a) const { return w < a. w; }
} edge[Len];
int pre[Len];
ll find(ll x) { return x == pre[x] ? x : pre[x] = find(pre[x]); }
void init()
{
for(int i = 0; i <= n; i ++)
pre[i] = i;
}
int main()
{
/* freopen("A.txt","r",stdin); */
scanf("%d %d", &n, &m);
init();
ll l, r, sum;
for(int i = 0; i < m; i ++)
{
scanf("%lld %lld %lld", &l, &r, &sum);
edge[i] = (Edge){ l-1, r, (r - l)*sum };
}
sort(edge, edge + m);
int cnt = 0;
ll u, v, w, Sp = 0;
for(int i = 0; i < m; i ++)
{
u = edge[i].u, v = edge[i].v, w = edge[i].w;
int fu = find(u);
int fv = find(v);
if(fu != fv)
pre[fu] = fv, cnt ++, Sp += w;
}
if(cnt < n) printf("lly tcl!\n");
else printf("%lld\n", Sp);
return 0;
}
