赛时是想到普通的线段树 + 二分 \(O(q\log^2n)\),预期是 70pts,实际 50pts
后面发现又是在 long long
类型的计算中,1ll
写成了 1
,然后爆负数,复杂度就错了,T 了四个点
开题,读起来是一个很套路的题目
要对区间在线修改,区间加、(区间乘?),发现数据很大,那就是线段树、树状数组维护了
思考了一下,答案可以分两部分求解,
一是找到使 youyou 死亡的那一轮,之前轮的贡献可以按题意累加得到,
LL sum = query(1, 1, n), tot = 0ll, last;int cnt = 0ll; // 实际到第 cnt 轮就死亡 while (tot < W){last = tot;tot = sum * (LL)(1ll << cnt) + last;cnt ++;}ans += (LL)((cnt - 1ll) * n); // 所有点覆盖轮 W -= last;
手算了一下时间复杂度应该是 \(O(x)\) 满足 \(sum\sum\limits_{i = 0}^x 2^i = W\),等比数列求和一下近似 \(O(\log n)\)
我一开始测大样例 2s 内本地跑不出来,以为是写假了(就是写假了 qwq,爆负数),然后卡了好久在那想怎么做到 \(sum\cdot 2^x=W\),白给了很多时间
二是确定为第 i 轮死亡时,想到从左往右覆盖具有单调性,可以把死亡位置二分出来,每次求个前缀和
时间复杂度是 \(O(\log^2n)\) 的
需要注意的是,我一开始是考虑第 i 轮要用区间乘实现,后来发现还要还原,有点不可做的感觉
但是再仔细一想,注意到第 i 轮的初始值是整体偏移的,且并不关心单个数值偏移后的具体大小,那我直接求出第一轮的和然后乘上对应的偏移量就可以了
可以拿到 70pts
code
#include <bits/stdc++.h>
#define re register int
#define lp p << 1
#define rp p << 1 | 1
#define int long longusing namespace std;
typedef long long LL;
const int N = 2e5 + 10;
const LL inf = 1e18;int n, T, a[N];
LL W0, ans;
struct Tree
{int l, r, tag;LL sum;
}t[N << 2];inline void push_up(int p)
{t[p].sum = t[lp].sum + t[rp].sum;
} inline void push_down(int p)
{if (t[p].tag){t[lp].sum += (LL)(t[lp].r - t[lp].l + 1) * (LL)t[p].tag;t[rp].sum += (LL)(t[rp].r - t[rp].l + 1) * (LL)t[p].tag;t[lp].tag += t[p].tag;t[rp].tag += t[p].tag;t[p].tag = 0;}
}inline void build(int p, int l, int r)
{t[p].l = l, t[p].r = r;if (l == r){t[p].sum = a[l];return;}int mid = (l + r) >> 1;build(lp, l, mid);build(rp, mid + 1, r);push_up(p);
}inline void update(int p, int l, int r, int k)
{if (l <= t[p].l && t[p].r <= r){t[p].sum += (LL)(t[p].r - t[p].l + 1) * k;t[p].tag += k;return;}push_down(p);int mid = (t[p].l + t[p].r) >> 1;if (l <= mid) update(lp, l, r, k);if (r > mid) update(rp, l, r, k);push_up(p);
}inline LL query(int p, int l, int r)
{if (l <= t[p].l && t[p].r <= r) return t[p].sum;push_down(p);LL res = 0ll;int mid = (t[p].l + t[p].r) >> 1;if (l <= mid) res += query(lp, l, r);if (r > mid) res += query(rp, l, r);return res;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);// freopen("wxyt3.in", "r", stdin);
// freopen("wxyt3.out", "w", stdout);cin >> n >> T >> W0;for (re i = 1; i <= n; i ++) cin >> a[i];build(1, 1, n);while (T --){ans = 0ll; LL W = W0;int L, R, d; cin >> L >> R >> d;update(1, L, R, d);LL sum = query(1, 1, n), tot = 0ll, last;int cnt = 0ll; // 实际到第 cnt 轮就死亡 while (tot < W){last = tot;tot = sum * (LL)(1ll << cnt) + last;cnt ++;}ans += (LL)((cnt - 1ll) * n); // 所有点覆盖轮 W -= last;int l = 1, r = n;while (l < r){int mid = (l + r) >> 1;if (W - query(1, 1, mid) * (LL)(1ll << (cnt - 1ll)) <= 0) r = mid;else l = mid + 1;}ans += (LL)(l - 1ll);cout << ans << '\n';}return 0;
}
瓶颈就是它卡两只 log,,,再考虑到线段树本身常数较大(可能树状数组可以冲一下?
可能有其他做法,std 是 \(O(n\log W + q)\) 的,没去看
消去一只 log 的办法就是在线段树上直接二分,找左右子树,很妙的办法
ac code
#include <bits/stdc++.h>
#define re register int
#define lp p << 1
#define rp p << 1 | 1
#define int long longusing namespace std;
typedef long long LL;
const int N = 2e5 + 10;
const LL inf = 1e18;int n, T, a[N];
LL W0, ans;
struct Tree
{int l, r, tag;LL sum;
}t[N << 2];inline void push_up(int p)
{t[p].sum = t[lp].sum + t[rp].sum;
} inline void push_down(int p)
{if (t[p].tag){t[lp].sum += (LL)(t[lp].r - t[lp].l + 1) * (LL)t[p].tag;t[rp].sum += (LL)(t[rp].r - t[rp].l + 1) * (LL)t[p].tag;t[lp].tag += t[p].tag;t[rp].tag += t[p].tag;t[p].tag = 0;}
}inline void build(int p, int l, int r)
{t[p].l = l, t[p].r = r;if (l == r){t[p].sum = a[l];return;}int mid = (l + r) >> 1;build(lp, l, mid);build(rp, mid + 1, r);push_up(p);
}inline void update(int p, int l, int r, int k)
{if (l <= t[p].l && t[p].r <= r){t[p].sum += (LL)(t[p].r - t[p].l + 1) * k;t[p].tag += k;return;}push_down(p);int mid = (t[p].l + t[p].r) >> 1;if (l <= mid) update(lp, l, r, k);if (r > mid) update(rp, l, r, k);push_up(p);
}inline LL query(int p, int l, int r)
{if (l <= t[p].l && t[p].r <= r) return t[p].sum;push_down(p);LL res = 0ll;int mid = (t[p].l + t[p].r) >> 1;if (l <= mid) res += query(lp, l, r);if (r > mid) res += query(rp, l, r);return res;
}inline int query2(int p, int l, int r, LL W, LL layer)
{if (l == r) return l;push_down(p);int mid = (l + r) >> 1;if (W - t[lp].sum * layer <= 0) return query2(lp, l, mid, W, layer);else return query2(rp, mid + 1, r, W - t[lp].sum * layer, layer);
}signed main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);// freopen("wxyt3.in", "r", stdin);
// freopen("wxyt3.out", "w", stdout);cin >> n >> T >> W0;for (re i = 1; i <= n; i ++) cin >> a[i];build(1, 1, n);while (T --){ans = 0ll; LL W = W0;int L, R, d; cin >> L >> R >> d;update(1, L, R, d);LL sum = query(1, 1, n), tot = 0ll, last;int cnt = 0ll; // 实际到第 cnt 轮就死亡 while (tot < W){last = tot;tot = sum * (LL)(1ll << cnt) + last;cnt ++;}ans += (LL)((cnt - 1ll) * n); // 所有点覆盖轮 W -= last;int pos = query2(1, 1, n, W, (LL)(1ll << (cnt - 1ll))) - 1;cout << ans + pos << '\n';}return 0;
}