我的世界
题目链接：YBT2023寒假Day12 A
题目大意
有 n 个数，每一秒每个数都会减小 1，而且你可以选一个数让它减小 x，小于 0 的数会变成 0。
给你 s 秒，问你 s 秒操作后所有数中最大的数的最小值是多少。
思路
首先我们考虑二分这个答案，然后考虑能不能达到。
然后发现需要的时间是 \(\sum\limits_{i=1}^n\left\lceil\dfrac{\max\{0,t_i-s-mid\}}{x}\right\rceil\)。
首先去掉 \(\max\)，二分找到第一个 \(t_i-s-mid>0\) 的 \(i\)。
然后处理上取整，考虑 \(\left\lceil t_i/x\right\rceil\) 对于每个数固定，预处理出它的前缀和。
然后减去 \(\left\lceil\dfrac{s+mid}{x}\right\rceil\)，然后考虑错了的部分。
不难发现错了的原因会是 \(t_i\%x>(s+mid)\%x\)，那我们可以开一个值域 \(x\) 的动态开点可持续化线段树，维护每一个前缀（我这里把数从大到小排序所以是前缀）余数为 \(l \sim r\) 的 \(t_i\) 的个数。
然后加上这个个数就行（每次错都会小了 \(1\)）
代码
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const ll N = 1e5 + 100;
ll n, m, x, t[N], rt[N], sum[N];
bool cmp(ll x, ll y) {
return x > y;
}
struct XD_tree {
ll f[N << 7], ls[N << 7], rs[N << 7], tot;
ll insert(ll nw, ll l, ll r, ll pl) {
ll now = ++tot; f[now] = f[nw]; ls[now] = ls[nw]; rs[now] = rs[nw];
f[now]++;
if (l == r) return now;
ll mid = (l + r) >> 1;
if (pl <= mid) ls[now] = insert(ls[now], l, mid, pl);
else rs[now] = insert(rs[now], mid + 1, r, pl);
return now;
}
ll query(ll now, ll l, ll r, ll L, ll R) {
if (!now) return 0;
if (L > R) return 0;
if (L <= l && r <= R) return f[now];
ll mid = (l + r) >> 1, re = 0;
if (L <= mid) re += query(ls[now], l, mid, L, R);
if (mid < R) re += query(rs[now], mid + 1, r, L, R);
return re;
}
}T;
ll check(ll TT) {
ll l = 1, r = n, re = n + 1;
while (l <= r) {
ll mid = (l + r) >> 1;
if (t[mid] <= TT) re = mid, r = mid - 1;
else l = mid + 1;
}
ll num = sum[re - 1] - (re - 1) * (TT / x);
ll lim = TT % x;
ll cnt = T.query(rt[re - 1], 0, x - 1, lim + 1, x - 1);
num += cnt;
return num;
}
int main() {
freopen("bone.in", "r", stdin);
freopen("bone.out", "w", stdout);
// printf("%.3lf", (sizeof(T) + sizeof(t) * 10) / 1024.0 / 1024.0);
scanf("%lld %lld %lld", &n, &m, &x);
for (ll i = 1; i <= n; i++) scanf("%lld", &t[i]);
sort(t + 1, t + n + 1, cmp);
for (ll i = 1; i <= n; i++) sum[i] = sum[i - 1] + (t[i] / x);
for (ll i = 1; i <= n; i++) rt[i] = T.insert(rt[i - 1], 0, x - 1, t[i] % x);
while (m--) {
ll s; scanf("%lld", &s);
ll L = 0, R = 1e18, re = 1e18;
while (L <= R) {
ll mid = (L + R) >> 1;
if (check(mid + s) <= s) re = mid, R = mid - 1;
else L = mid + 1;
}
printf("%lld\n", re);
}
return 0;
}