- 2026/3/28 16:14 二分中位数的模板如下：
bool check1(long long x) {long long cnt1 = 0, cnt2 = 0;for (long long i = 1; i <= n; i++) {if (a[i].l2 > x) cnt2 += a[i].l1;else cnt1 += a[i].r1;}if ((cnt1 + cnt2) % 2 == 0) return cnt1 >= cnt2;else return cnt1 >= (cnt2 + 1);
}
bool check2(long long x) {long long cnt1 = 0, cnt2 = 0;for (long long i = 1; i <= n; i++) {if (a[i].r2 < x) cnt1 += a[i].l1;else cnt2 += a[i].r1;}if ((cnt1 + cnt2) % 2 == 0) return cnt2 >= cnt1 + 2;else return cnt2 >= cnt1 + 1;
}
// 以上是 check
long long l1 = mx, r1 = 0;
while (l1 > r1) {long long mid = l1 + r1 - 1 >> 1;if (check1(mid)) l1 = mid;else r1 = mid + 1;
}
long long l2 = 0, r2 = mx;
while (l2 < r2) {long long mid = l2 + r2 + 1 >> 1;if (check2(mid)) l2 = mid;else r2 = mid - 1;
}
- 2026/3/28 16:47 记得开
long long
