【Codeforces 878E】Numbers on the blackboard | Mrsrz's blog

贪心

题目大意：

给定一个数列，每个数是整数，你可以执行一个操作：选择一个位置（不能是最后一个位置），令这个位置和其后面的位置分别为 $x,y$，则将这两个位置删除并替换为 $x+2y$。

有多次询问，每次给定 $l,r$，表示对 $l,r$ 区间的数执行 $r-l$ 次操作，剩下的那个数最大是多少。

题解：

观察到，每个数对最终的贡献都是 $2^k$，其中 $k\geq 0$，并且 $\forall i\in[1,n-1]$，都有 $k_i\leq k_{i-1}+1$。

考虑使用贪心的策略，即令正数的系数尽可能大。

我们从左到右加入数，把贡献为正的部分放到一个块里，块 $[l,r]$ 内的每个位置 $i\in[l+1,r]$ 满足 $k_i=k_{i-1}+1$.

当遇到一个负数的时候，给它另外开一个块存。当遇到一个非负数，则往之前那个块合并。如果合并后导致原来一个贡献为负的块贡献变为正了，则继续往前合并，并且仍然保证 $k$ 依次递增的性质（显然这样分配的贡献是最大的）。

于是考虑将询问离线，并依次把每个数加入，用并查集维护一个数所在块（以块的最前端为根，顺便维护块长）。

考虑一段区间的贡献的时候，中间整块部分的维护一下前缀和即可。最左边的一个块可能不是完整的，但是由于 $k$ 递增的性质，所以可以像提取子串哈希值一样，预处理后缀，把这个部分的提取出来即可。

时间复杂度 $O(n\log n)$。

Code：

#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int N=5e5+7,md=1e9+7,inf=2e9+5;
int n,a[N],pr[N],_2[N],L[N],fa[N],f[N],ans[N],ps[N],s[N],m;
vector<pair<int,int> >vec[N];
inline void upd(int&a){a+=a>>31&md;}
void init(int n){for(int i=*_2=1;i<=n;++i)upd(_2[i]=(_2[i-1]<<1)-md);}
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
    fa[y]=x;
    if(L[x]>30&&s[x]>0||s[x]+((LL)s[y]<<L[x])>=inf)s[x]=inf;else s[x]+=s[y]<<L[x];
    f[x]=(f[x]+(LL)f[y]*_2[L[x]])%md;
    L[x]+=L[y];
}
inline int calc(int l,int r){return(pr[l]-(LL)pr[r+1]*_2[r-l+1]%md+md)%md;}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    init(n);
    for(int i=1;i<=n;++i)
        cin>>a[i],upd(f[i]=s[i]=a[i]);
    for(int i=n;i;--i)
        pr[i]=((LL)(pr[i+1]<<1)+a[i]+md)%md;
    for(int i=1;i<=n;++i)fa[i]=i,L[i]=1;
    for(int i=1;i<=m;++i){
        int l,r;
        cin>>l>>r;
        vec[r].emplace_back(l,i);
    }
    for(int i=1;i<=n;++i){
        while(find(i)>1&&s[find(i)]>=0)merge(find(find(i)-1),find(i));
        upd(ps[find(i)]=ps[find(find(i)-1)]+f[find(i)]-md);
        for(auto q:vec[i]){
            int l=q.first,id=q.second;
            ans[id]=((LL)(ps[find(i)]-ps[find(l)]+md)*2+calc(l,find(l)+L[find(l)]-1)+md)%md;
        }
    }
    for(int i=1;i<=m;++i)
        cout<<ans[i]<<'\n';
    return 0;
}