给一个 \(n\) 个点的图，每个点 \(i\) 有点权 \(a_i\)，初始图上没有边，你可以进行如下操作若干次：
- 若 \(S_i+S_j\ge i\times j\times c\)，添加一条边 \((i, j)\)。其中 \(S_i\) 表示 \(i\) 所在连通块的点权和，\(c\) 是一个给定的常数。
问最终能否使图联通。
首先我们有一个简单的 \(O(n^3)\) 做法：暴力 \(O(n^2)\) 寻找能连的边，如果能连 \(n-1\) 次就 yes，否则 no。
考虑优化连边过程。我们发现，合并两个连通块时，我们一定要选连通块中编号最小的点连边，因为这样在 \(S_i+S_j\) 不改变时使 \(i\times j\times c\) 最小，能连边的可能性最大。因此下文提到 \(i,j\) 都默认它们是连通块中编号最小的点。
这时注意到一个特殊的连通块：\(1\) 号点所在的连通块。这个连通块的最小编号是不变的。在手玩半天样例并猜错结论 WA 了一发后，我猜想了这样一个结论：如果 \(i\) 和 \(j\) 能连边，那么 \(1\) 和 \(i\)，\(1\) 和 \(j\) 至少有一组能连边。
更加形式化地：若 \(S_i+S_j\ge i\times j\times c\)，则 \(S_1+S_i\ge i\times c\) 和 \(S_1+S_j\ge j\times c\) 至少有一个成立。
于是按 \(i\times c-a_i\) 由小到大排序再逐个连边就过了。
结论证明（参考了官方题解）：
\[\begin{aligned}
&S_i+S_j\ge i\times j\times c\\
\iff&\frac{S_i+S_j}c\ge i\times j=(i-1)(j-1)+i+j-1\\
\implies&\frac{S_i+S_j}c\ge i+j-1\quad(*)
\end{aligned}
\]
不妨令 \(S_1=0\)，于是我们要证明 \(\frac{S_i}c\ge i\) 或 \(\frac{S_j}c\ge j\)。根据 \((*)\) 式使用反证法易证。
代码：
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i, s, e) for(int i = s, i##E = e; i <= i##E; ++i)
#define per(i, s, e) for(int i = s, i##E = e; i >= i##E; --i)
#define F first
#define S second
#define int ll
#define gmin(x, y) (x = min(x, y))
#define gmax(x, y) (x = max(x, y))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double f128;
typedef pair<int, int> pii;
void solve() {
int n, c;
cin >> n >> c;
vector<pii> a(n + 5);
rep(i, 1, n) cin >> a[i].F, a[i].S = i;
sort(a.begin() + 2, a.begin() + n + 1, [&](pii a, pii b) {
return a.F - a.S * c > b.F - b.S * c;
});
int s = a[1].F;
rep(i, 2, n) {
// cerr << a[i].F << ' ' << a[i].S << endl;
if(a[i].S * c <= s + a[i].F) s += a[i].F;
else { cout << "No\n"; return; }
}
cout << "Yes\n";
}
signed main() {
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#endif
int t; cin >> t;
while(t--) solve();
return 0;
}