cyh 巨佬举办的比赛。
赛时没时间写题，赛后补一下。
T1:
默认排名第一，对于每次输入，若输入的成绩更优，则将排名降低。这里更劣的成绩没用，因为默认初始排名第一。
T2:
At 上的一道原题。考虑 DP 求解。\(dp_{i, 0/1}\) 分别表示到第 \(i\) 张翻和不翻的总情况数。每次判断翻或不翻和上一张是否相同，若是就转移。别忘记每次取模。
T3:
给出一个一眼的拆式子的方法。
\[\sum_{i = l}^{r} a_i \times (i - l + 1) = \sum_{i = l}^{r} a_i \times (i + 1) - \sum_{i = l}^{r} a_i \times l \]令 \(suma_i = \sum_{j = 1}^{i} a_j\)，\(sumb_i = \sum_{j = 1}^{i} a_j \times (j + 1)\)。相当于求了两个前缀和。每次输出区间的两个值相减即可。
T4:
cyh 提供的分块算法好强大，我根本看不懂（）。
我们发现随着操作次数增加，满足条件的可能性也增加，单调递增。所以考虑二分操作次数 \(mid\)。
考虑如何 \(check\)。用暴力枚举每个位置会 T 飞。我们不妨试着转换一下。给出 \(mid\) 次操作的区间，求序列里是否有任何一个值 \(\ge v\)，就相当于给出 \(mid\) 条线段，每条线段有值为 \(w_i\)，问最大的重叠部分的总值是否 \(\ge v\)。
再考虑如何实现。我们可以把 \(mid\) 条线段打散成 \(mid \times 2\) 个点，标记每个点的位置 \(p\)，所在线段的值 \(w\)，头尾 \(0/1\)。然后以 \(p\) 为关键字由小到大排序。然后依次枚举排序后 \(mid \times 2\) 个点，若为开头，就加上当前线段的值（相当于加入了当前线段），若为结尾，就减去当前线段的值。对于 \(mid \times 2\) 次的枚举，每次判断当前的值是否 \(\ge v\) 即可。
时间复杂度约为 \(O(k \log k \log k)\)，\(check\) 的复杂度在于排序。喜提最优解。
#include <bits/stdc++.h>
typedef long long ll;
#define int long long
const int N = 1e4 + 100;
int n, v, l[N], r[N], w[N];
struct node {
int p, w; bool flag;
bool operator < (const node &b) const {
return p < b.p;
}
}; std::vector <node> vec;
bool check(int mid) {
vec.clear();
for (int i = 1; i <= mid; ++ i) {
vec.push_back((node) {l[i], w[i], 0});
vec.push_back((node) {r[i] + 1, w[i], 1});
}
std::sort(vec.begin(), vec.end());
int tmp = 0;
for (int i = 0; i < vec.size(); ++ i) {
if (vec[i].flag == 0) tmp += vec[i].w;
else tmp -= vec[i].w;
if (tmp >= v) return 1;
}
return 0;
}
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> n >> v;
for (int i = 1; i <= n; ++ i) std::cin >> l[i] >> r[i] >> w[i];
int l = 1, r = n, ans = -1;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
} std::cout << ans;
return 0;
}