题解：P11217 【MX-S4-T1】「yyOI R2」youyou 的垃圾桶

· · 题解

以下设所有垃圾桶当前攻击力总和为 S。

我们考虑暴力，因为生命值 W\le 10^{18}，攻击力是翻倍递增的，因此最多只会打 \log{W} 轮。因此暴力的时间复杂度是 O(nq \log W)。可以获得 20 分。

如果我们假设这场战斗完整地打了 k 轮，那么这 k 轮需要消耗的生命值为 S \times (2^0 + 2^1 + \dots + 2^{k-1}) = S \times (2 ^ k - 1)。

接下来，我们就要求出最大的 m，使得 \sum^{m}_{i=1}a_i \le W - S \times (2 ^ k - 1)。

那么答案即为 k \times n + m。

显然，对于每一次修改，S 只会增加 (r_i - l_i + 1) \times d_i。

因为能打完必须继续打下去，因此对于每一个询问，我们需要求出最大的 k。

假设我们枚举这个 k，用线段树维护区间修改，同时线段树上二分快速求出 m，那么时间复杂度 O(q\log W + q \log n)，预计可以拿到 70 分（实际上可以获得 100）。

我们发现 k 不需要每次都枚举，因为每次操作后，答案只会变小，也就是 k 是递减的。我们只需检验之前求出的 k 是否满足 W \ge S \times (2 ^ k - 1) 即可，不满足再暴力往下求解，这样时间复杂度 O(n \log W + q)。

对于相同的 k，显然 m 也在递减。于是用指针维护 m 的值，同时用两个差分数组维护区间加即可。

对于不同的 k，暴力求解即可。

参考代码：

#include <iostream>
using namespace std;
const int Q = 1000005;
const int N = 200005;
long long l[Q],r[Q];
long long d[Q];
int q;
long long int A,B,C;
int M;
int n;
long long a[N];
long long W;
__int128 S;
long long k,m;
long long lst[N];
long long nxt[N];
__int128 camPa,camPb;
__int128 lastW;
__int128 sumf;
long long ass;
void workfor_new()
{
    long long now = 0;
    lst[n + 1] = nxt[n + 1] = lst[0] = nxt[0] = 0;
    sumf = 0;
    for(int i = 1;i <= n;i ++)
    {
        now = now + lst[i];
        a[i] = a[i] + now;
        lst[i] = nxt[i] = 0;
    }
    long long BASE = (1ll << k) - 1;
    long long ok = W - S * BASE;
    long long ove = (1ll << k);
    for(int i = 1;i <= n;i ++)
    {
        if(ok <= a[i] * ove) 
        {
            m = i - 1;
            lastW = ok;
            break;
        }
        ok -= a[i] * ove;
    }
    return;
}
long long ans;
int main()
{
    //freopen("wxyt20.in","r",stdin);
    //freopen("wxyt20.out","w",stdout);
    cin >> n >> q >> W;
    for(int i = 1;i <= n;i ++)
    cin >> a[i],S += a[i];
    for(int i = 1;i <= q;i ++)
    {
      scanf("%lld%lld%lld",&l[i],&r[i],&d[i]);
    }
    for(k = 60;k >= 0;k --) 
    {
        camPb = S;
        camPb *= ((1ll << k) - 1ll);
        camPa = W;
        if(camPb < camPa) break;
    }

    workfor_new();
    for(int i = 1;i <= q;i ++)
    {
        S = S + (r[i] - l[i] + 1) * d[i];
        camPb = S;
        camPb *= ((1ll << k) - 1ll);
        camPa = W;
        lst[l[i]] += d[i];
        lst[r[i] + 1] -= d[i];
        nxt[r[i]] += d[i];
        nxt[l[i] - 1] -= d[i];
        if(camPb >= camPa)
        {
            for(;k >= 0;k --)
            {
                camPb = S;
                camPb *= ((1ll << k) - 1ll);
                camPa = W;
                if(camPb < camPa) break; 
            }
            workfor_new();
        }
        else
        {
            long long po = (1ll << k); 
            lastW -= (po - 1) * (r[i] - l[i] + 1) * d[i];
            lastW -= d[i] * po * max(min(r[i],m) - l[i] + 1,0ll); 
            if(l[i] <= m + 1 && m < r[i]) sumf += d[i];
            for(;m >= 1;m --)
            {  
                if(lastW > 0) break;
                sumf += nxt[m];
                lastW += (sumf + a[m]) * po; 
            }
        }
        printf("%lld\n",k*n+m);
    }

}