题目
题目链接：https://codeforces.com/problemset/problem/878/E
给出 (n) 个数字，每次询问一个区间 ([l,r]) ，对这个区间内部的点进行操作。
每次操作可以合并相邻两个数 (x) , (y) ，将它们变成 (x+2y) 对于每次询问输出当最后只剩下一个数字时，这个数字的最大值。
询问互相独立，答案对 (10^9+7) 取模。
思路
容易发现最后每一个数字权值一定是 (2) 的次幂，并且我们合并一定是先从前往后合并为若干个块，然后再从后往前依次将每一个块往前合并，最后合并成一个块。所以我们就先只进行第一类合并，第二类合并可以直接将后面的块的数的权值乘上 (2)。
假设我们前 (i) 个数已经合并成了若干个块，考虑加入第 (i+1) 个数，如果新开一个块它的权值就是 (1)，否则就是 (2^{l+1})，其中 (l) 是上一个块的长度。
- 如果 (a[i+1]>0)，那么我们肯定将 (i+1) 合并到前一个块中。
- 如果 (a[i+1]leq 0)，我们就新开一个块存它。
注意到将 (i+1) 合并到前一个块中的时候，可能导致前一个块的和也变成正数，此时我们需要一直往前合并直到剩余一个块或该块和为负数。
但是如果直接合并，随便一个长度足够长的正数序列就可以让和超过 long long 范围。但是我们发现最坏情况下，每一个块的和均不小于 (-10^9)，所以整个序列合并之后最坏情况下和不会低于 (-10^9ngeq -10^{14})。所以如果一个块的和超过了 (10^{14})，这个块一定可以一直合并到第一个块，所以我们直接将这一类块的权值赋值为 (+infty)，合并的时候特判一下就好了。这样我们就保证了每一个块的和不会超过 long long 范围。
然后将询问离线，按右端点从小到大排序，找到最左边的块单独拆开来计算，加上右边的块的和乘 (2) 即为答案。
时间复杂度 (O((n+m)log n))。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010,MOD=1e9+7;
const ll Inf=1000000000000000LL;
int n,Q,top,a[N],st[N],ans[N];
ll power[N],inv[N],mul[N],sum[N],sum2[N];
struct node
{
int l,r,id;
}ask[N];
bool cmp(node x,node y)
{
return x.r<y.r;
}
int main()
{
scanf("%d%d",&n,&Q);
power[0]=inv[0]=1;
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
power[i]=power[i-1]*2%MOD;
inv[i]=inv[i-1]*500000004%MOD;
mul[i]=(mul[i-1]+power[i]*a[i])%MOD;
}
for (int i=1;i<=Q;i++)
{
scanf("%d%d",&ask[i].l,&ask[i].r);
ask[i].id=i;
}
sort(ask+1,ask+1+Q,cmp);
for (int i=1,j=1;i<=Q;i++)
{
int l=ask[i].l,r=ask[i].r;
for (;j<=r;j++)
{
st[++top]=j; sum[top]=a[j];
while (top>1 && sum[top]>0)
{
if (st[top]-st[top-1]>=50 || (1LL<<st[top]-st[top-1])>(Inf-sum[top-1])/sum[top]) sum[top-1]=Inf;
else sum[top-1]+=(1LL<<st[top]-st[top-1])*sum[top];
top--;
}
if (sum[top]<Inf) sum2[top]=(sum2[top-1]+sum[top])%MOD;
else sum2[top]=mul[j];
}
st[top+1]=r+1;
int p=upper_bound(st+1,st+2+top,l)-st;
ans[ask[i].id]=((sum2[top]-sum2[p-1])*2+(mul[st[p]-1]-mul[l-1])*inv[l])%MOD;
}
for (int i=1;i<=Q;i++)
printf("%d
",(ans[i]%MOD+MOD)%MOD);
return 0;
}