Um_nik: Stop learning useless algorithms, go and solve some problems, learn how to use binary search!
有 \(n\) 個物品，每個物品有對應的價格和價值
\(m\) 次詢問，每次詢問會有 \(c\) 的本金，之後無腦選擇能買得起的最貴物品買走（若有多個最貴的就選價值最高的），直到不能買為止，問買走的物品價值和。（\(n \leq 10 ^ 5\)）
首先對物品先按價格， 後按價值從大到小排序。
注意到對於每次購買一段東西，本金減少至少一半，所以消費的次數為 \(O(\log\ n)\) 級別的
這時候我們知道這次購買的右端點 \(r\) （即上次購買的最後一個的下一個）， 則可以利用字首和求出左端點 \(l\)
#include <bits/stdc++.h>
#define int long long
const int N = 1e5 + 5, inf = 1e18;
int n, m, x, ans, last;
int sum[N], v[N];
struct product {
int a, b;
bool operator < (const product &x) const {return a == x.a ? b > x.b : a > x.a;}
} a[N];
signed main() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%lld%lld", &a[i].a, &a[i].b);
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) sum[i] = a[i].a + sum[i - 1];
for (int i= 1; i <= n; ++i) v[i] = a[i].b + v[i - 1];
while (m--) {
scanf("%lld", &x);
last = ans = 0;
while (x) {
int l = std::lower_bound(a + last + 1, a + n + 1, (product){x, inf}) - a;
if (l > n) break;
int r = std::upper_bound(sum + l + 1, sum + n + 1, x - a[l - 1].a) - sum - 1;
x -= sum[r] - sum[l - 1], ans += v[r] - v[l - 1];
last = r;
} printf("%lld\n", ans);
} return 0;
}
有 \(n\) 個點 \(m\) 條邊，邊從 \(1\) 到 \(m\) 編號。要求把 \([1, m]\) 劃分成儘可能多個區間，使得對於每個區間內的邊，都有一個子集能構成一棵邊權和不超過 \(S\) 的生成樹。
多組資料， \(T \leq 5, 2 \leq n, m \leq 10 ^ 5, s \leq 10 ^ 9。\)
如果對每個左端點都進行二分，那麼注意到，每次Check的複雜度是 \(O(k\ \log\ k)\) 的，最壞情況下會有 \(O(\frac{m ^ 2}{n}\ \log^2\ m)\) 的複雜度，喜提 \(TLE\)
對於這種情況，我們一般有兩種辦法：
資料分塊
改進二分
在 \(n, m \leq 10 ^ 5\) 的資料範圍下， \(O(\frac{m ^ 2}{n}\ \log^2\ m)\) 的複雜度在 \(n\) 較小時就炸掉了，於是考慮針對 \(n\) 的大小進行資料分塊
注意到，如果我們直接往裡面加邊並動態維護最小生成樹，直到形成一個滿足條件的生成樹後把圖清空。這樣的做法是 \(O(nm)\) 的
至於如何動態維護最小生成樹，可以在加邊時直接暴力求出