CF878E Numbers on the blackboard
好题。看到这个东西考虑打表一下最后每个点系数，需要一定的眼力才能看出相当于一个除了只有第一个是 1，后面的点每次最多比前面一个乘二的序列。知道结论证明就可以简单归纳了。
然后考虑答案的形态，发现如果我们称每次乘二的一段为连续段，那么对于最后一个连续段的开头，我们可以发现它要么直接取 \(2\) 要么还不如跟上一个连续段接起来，所以答案一定是若干个从一开始的连续段。
于是我们可以扫描右端点拿单调栈维护这个东西，区间询问就离线一下用并查集搞，复杂度 \(O(n\alpha(n))\)。
#include <cstdio>
#include <vector>
using namespace std;
int read(){/*...*/}
const int N=100003,P=1000000007,Lim=1000000010;
typedef long long ll;
int n,q,a[N],f[N];
int pos[N],res[N],id[N];
int s[N],bn[N],sb[N];
vector<int> vec[N];
int calc(int l,int r){
int tmp=(s[l]-(ll)s[r]*bn[r-l])%P;
if(tmp<0) return tmp+P;
return tmp;
}
int rt(int x){
if(f[x]==x) return x;
return f[x]=rt(f[x]);
}
int stk[N],val[N],vv[N],sm[N],tp;
int main(){
n=read();q=read();sb[0]=bn[0]=1;
for(int i=1;i<=n;++i){
a[i]=read();
sb[i]=min(sb[i-1]<<1,Lim);
bn[i]=bn[i-1]<<1;
if(bn[i]>=P) bn[i]-=P;
}
for(int i=1;i<=n+1;++i) f[i]=i;
for(int i=1;i<=q;++i){
pos[i]=read();
res[i]=a[pos[i]++];
if(res[i]<0) res[i]+=P;
vec[read()].emplace_back(i);
}
for(int i=n;i;--i){
s[i]=s[i+1]<<1;
if(s[i]>=P) s[i]-=P;
s[i]+=a[i];
if(s[i]<0) s[i]+=P;
if(s[i]>=P) s[i]-=P;
}
for(int i=1;i<=n;++i){
int cur=a[i],cc=a[i],las=i;
if(cc<0) cc+=P;
while(tp&&cur>=0){
int x=stk[tp];
f[las]=las+1;
cur=min(val[tp]+(ll)cur*sb[las-x],(ll)Lim);
cc=(vv[tp]+(ll)cc*bn[las-x])%P;
las=x;--tp;
}
stk[id[las]=++tp]=las;
val[tp]=cur;vv[tp]=cc;
sm[tp]=sm[tp-1]+vv[tp];
if(sm[tp]>=P) sm[tp]-=P;
id[i+1]=tp+1;
for(int x:vec[i]){
int pp=rt(pos[x]);
int tmp=calc(pos[x],pp);
tmp+=sm[tp];
if(tmp>=P) tmp-=P;
tmp-=sm[id[pp]-1];
if(tmp<0) tmp+=P;
tmp<<=1;
if(tmp>=P) tmp-=P;
res[x]+=tmp;
if(res[x]>=P) res[x]-=P;
}
}
for(int i=1;i<=q;++i) printf("%d\n",res[i]);
return 0;
}