题解 CF1172F 【Nauuo and Bug】

· · 题解

搞一棵线段树

对于一个区间 [l,r]，维护一个数组 c，c_x 表示最小的初始值使得这个初始值经过 [l,r] 后被减去了 x 个 p

怎么合并信息？设左面减去了 x 个 p，右面减去了 y 个 p，则我们用 c_x 和 c_y 更新 c_{x+y}

什么样的 x,y 是合法的呢？最大的合法的初始值即 c_{x+1}-1 经过左区间后的值要大于 c_y

对于一对合法的 x,y，我们更新 c_{x+y} 为 \min(c_{x+y},\max(c_x,c_y+xp-sum_{ls}))，分别表示初始值对于左区间会被减掉 x 次，对于右区间会被减掉 y 次

具体如何合并呢？这里其他两篇题解说的是有问题的，光是 c 有单调性并不能直接双指针，而是需要 c_{x+1}-1-xp+sum_{ls} 有单调性，即证明 c_{x+1}-c_x\ge p

如何证明？由于 c_x 表示最小的初始值，所以 c_x 经过一段区间后，最大值必定是 0，否则我们可以将初始值调小一点，所以我们需要再增加至少 p 才可以再减掉一个 p

为什么 c_{x+1}-c_x 不一定为 p？对于数列 3 -10000，p=5，则 c_1=2,c_2=10007

另外对于@Ynoi 程序中，第一个 if(y != 0) y --; 其实是挺令人迷惑的，这个其实只是因为如果 y 循环到了上界 +1，这个 y 显然是不合法的，但是我们因为退出了循环没有 y--，所以才有了第一个 if(y != 0) y --;，其实可以写成 if(y>c[rc].n) y--；这样可能好理解一些

对于查询，找最后一个小于等于当前初始值的 c_x 即可，这个部分看代码很好理解的

时间复杂度：O(n\log n+q\log^2 n)，空间复杂度：O(n\log n)

//timeuse:40min
const int N = 1000010;
int n,m;ll p,a[N];
struct tree { int l,r,len;ll sum;vector<ll> c; }t[N << 2];
#define ls now << 1
#define rs now << 1 | 1
void pushup(int now)
{
    t[now].sum = t[ls].sum + t[rs].sum;
    int y = 0;
    for(int x = 0;x <= t[ls].len;x++)
    {
        if(y > t[rs].len) y--;
        for(;y <= t[rs].len;y++)
        {
            ll res = t[rs].c[y] + x * p - t[ls].sum;
            ll maxx = t[ls].c[x + 1] - 1 - x * p + t[ls].sum;
            if(maxx < t[rs].c[y]) { if(y) y--;break; }
            t[now].c[x + y] = min(t[now].c[x + y],max(t[ls].c[x],res));
        }
    }
}
void build(int now,int l,int r)
{
    t[now].l = l,t[now].r = r,t[now].len = r - l + 1;
    for(int i = 1;i <= t[now].len + 2;i++) t[now].c.push_back(LINF);
    t[now].c[0] = -LINF;
    if(l == r) { t[now].sum = a[l],t[now].c[1] = p - a[l];return; }
    int mid = l + r >> 1;build(ls,l,mid),build(rs,mid + 1,r);
    pushup(now);
}
ll query(int now,int l,int r,ll x)
{
    if(t[now].l == l && t[now].r == r)
    {
        ll pos = upper_bound(t[now].c.begin(),t[now].c.end(),x) - t[now].c.begin() - 1;
        return x + t[now].sum - p * pos;
    }
    int mid = t[now].l + t[now].r >> 1;
    if(r <= mid) return query(ls,l,r,x);
    if(l > mid) return query(rs,l,r,x);
    return query(rs,mid + 1,r,query(ls,l,mid,x));
}

int main()
{
    n = read(),m = read(),p = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    build(1,1,n);
    while(m--) { int l = read(),r = read();fprint(query(1,l,r,0)); }
    return 0;
}