P11217 【MX-S4-T1】「yyOI R2」youyou 的垃圾桶 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
实际上整理整理没什么难的。主要是考数据结构,完了时间复杂度 \(O(n\log^2n)\) 的树状数组 + 二分,比 \(O(n\log n)\) 的线段树上二分还快,而且线段树还差 20ms 就爆了,线段树还是得优化常数。
通过推公式,二分找出经过 k 轮(全部都使用),能把血量清零。然后 k - 1, 去找最后一轮实际上用多少,这里主要是求 sum 与 二分,所以可以使用线段树上二分,或者树状数组求和 + 二分。
附上测评结果:
树状数组: 记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
线段树(不卡常):记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
线段树(卡常):记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
树状数组 + 二分
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
using namespace std;
typedef long long LL;
const int N = 200010;
LL n, m, w;
LL tr[N], trs[N];
LL a[N];
LL read()
{
LL x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if(ch == '-' )
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = x * 10 + ch -'0', ch = getchar();
return x * f;
}
int lowbit(int x)
{
return x & -x;
}
void add(LL tr[], int x, LL k)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += k;
}
void addd(int l, int r, LL k)
{
add(tr, l, k);
add(tr, r + 1, -k);
add(trs, l, l * k);
add(trs, r + 1, -(r + 1) * k);
}
LL sum(LL tr[], int x)
{
LL res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
LL ssum(int x)
{
LL a = sum(tr, x), b = sum(trs, x);
return (__int128)a * (x + 1) - b;
}
LL find(LL x, LL sum)
{
LL l = 0, r = 61;
while (l < r)
{
LL mid = l + r >> 1;
if ((__int128)sum * ((1ll << mid) - 1) >= x) r = mid;
else l = mid + 1;
}
return l;
}
LL find2(LL w, LL k)
{
int l = 0, r = n;
while (l < r)
{
int mid = l + r >> 1;
if ((__int128)ssum(mid) * (1ll << k) >= w) r = mid;
else l = mid + 1;
}
return l;
}
int main()
{
// freopen("wxyt4.in", "r", stdin);
// freopen("wxyt4.out", "w", stdout);
cin >> n >> m >> w;
for (int i = 1; i <= n; i ++ )
{
a[i] = read();
add(tr, i, a[i] - a[i - 1]);
add(trs, i, 1ll * i * (a[i] - a[i - 1]));
}
LL last = ssum(n);
while (m -- )
{
LL l, r, d;
l = read();
r = read();
d = read();
addd(l, r, d);
last += (r - l + 1) * d;
LL res = last, ans = 0;
LL k = find(w, res) - 1;
ans = k * n;
ans += find2(w - res * ((1ll << k) - 1), k) - 1;
printf("%lld\n", ans);
}
return 0;
}
线段树上二分
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
using namespace std;
typedef long long LL;
const int N = 200010;
LL n, m, w;
LL a[N];
struct Node
{
int l, r;
__int128 sum, add;
}tr[N * 4];
LL read()
{
LL x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if(ch == '-' )
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = x * 10 + ch -'0', ch = getchar();
return x * f;
}
void pushup(Node &u, Node &l, Node &r)
{
u = {l.l, r.r, l.sum + r.sum};
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void pushdown(Node &u, LL add)
{
u.sum += (u.r - u.l + 1) * add;
u.add += add;
}
void pushdown(int u)
{
pushdown(tr[u << 1], tr[u].add);
pushdown(tr[u << 1 | 1], tr[u].add);
tr[u].add = 0;
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, a[l]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int add)
{
if (l <= tr[u].l && tr[u].r <= r) pushdown(tr[u], add);
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, add);
if (r > mid) modify(u << 1 | 1, l, r, add);
pushup(u);
}
}
LL query(int u, int l, int r)
{
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL sum = 0;
if (l <= mid) sum += query(u << 1, l, r);
if (r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}
}
LL findl(int u, int l, int r, LL k, LL w, LL sum)
{
if (tr[u].l == tr[u].r)
{
if ((__int128)(tr[u].sum + sum) * k < w) return -1;
return tr[u].l;
}
else if (l <= tr[u].l && tr[u].r <= r)
{
pushdown(u);
if ((__int128)(tr[u << 1].sum + sum) * k >= w) return findl(u << 1, l, r, k, w, sum);
else return findl(u << 1 | 1, l, r, k, w, sum + tr[u << 1].sum);
}
}
LL find(LL x, LL sum)
{
LL l = 0, r = 61;
while (l < r)
{
LL mid = l + r >> 1;
if ((__int128)sum * ((1ll << mid) - 1) >= x) r = mid;
else l = mid + 1;
}
return l;
}
signed main()
{
// freopen("wxyt4.in", "r", stdin);
// freopen("wxyt4.out", "w", stdout);
cin >> n >> m >> w;
for (int i = 1; i <= n; i ++ )
{
a[i] = read();
}
build(1, 1, n);
LL last = query(1, 1, n);
while (m -- )
{
LL l, r, d;
l = read();
r = read();
d = read();
modify(1, l, r, d);
last += 1ll * (r - l + 1) * d;
LL res = last, ans = 0;
LL k = find(w, res) - 1;
ans = k * n;
ans += findl(1, 1, n, (1ll << k), w - res * ((1ll << k) - 1), 0) - 1;
printf("%lld\n", ans);
}
return 0;
}
标签:二分,ch,R2,yyOI,int,LL,mid,T1,include
From: https://www.cnblogs.com/blind5883/p/18538631