C++(clang++11) 解法, 执行用时: 1332ms, 内存消耗: 194864K, 提交时间: 2021-05-12 19:42:19

#include  <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=3e5+5,N=20,mod=1e9+7;
int n,a[M],k[M],rt,son[M][2],fa[M][N],dep[M],val[M],prefa[M][N][2],prek[M][N][2],preval[M][N][2];
vector<int> st;
void dfs1(int x)
{
    for(int i=0;i<2;i++)
        if(int y=son[x][i])
        {
            fa[y][0]=x;
            for(int j=1;j<N;j++)fa[y][j]=fa[fa[y][j-1]][j-1];
            dep[y]=dep[x]+1;
            dfs1(y);
            val[x]=(val[x]+val[y])%mod;
        }
        else val[x]=(val[x]+a[x+i])%mod;
    val[x]=(ll)val[x]*k[x]%mod;
}
int getval(int x,int g){return son[x][g]?val[son[x][g]]:a[x+g];}
void dfs2(int x)
{
    for(int i=0;i<2;i++)
        if(int y=son[x][i])
        {
            prefa[y][0][0]=i?prefa[x][0][0]:x;prefa[y][0][1]=i?x:prefa[x][0][1];
            prek[y][0][0]=prek[y][0][1]=k[y];
            preval[y][0][0]=(ll)getval(y,1)*k[y]%mod;preval[y][0][1]=(ll)getval(y,0)*k[y]%mod;
            for(int j=1;j<N;j++)for(int c=0;c<2;c++)
            {
                prefa[y][j][c]=prefa[prefa[y][j-1][c]][j-1][c];
                prek[y][j][c]=(ll)prek[y][j-1][c]*prek[prefa[y][j-1][c]][j-1][c]%mod;
                preval[y][j][c]=((ll)preval[y][j-1][c]*prek[prefa[y][j-1][c]][j-1][c]%mod+preval[prefa[y][j-1][c]][j-1][c])%mod;
            }
            dfs2(y);
        }
}
int lca(int x,int y)
{
    if(dep[y]>dep[x])swap(x,y);
    for(int i=N-1;i>=0;i--)
        if(dep[fa[x][i]]>=dep[y])
            x=fa[x][i];
    if(x==y)return x;
    for(int i=N-1;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int que(int x,int d,int g)
{
    int ans=a[x+g];
    for(int i=N-1;i>=0;i--)
    {
        int t=prefa[x][i][g];
        if(t&&dep[t]>=dep[d])
            ans=((ll)ans*prek[x][i][g]%mod+preval[x][i][g])%mod,x=t;
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d",&k[i]);
        while(!st.empty()&&k[st.back()]>=k[i])
        {
            son[i][0]=st.back();
            st.pop_back();
        }
        if(!st.empty())son[st.back()][1]=i;
        else rt=i;
        st.push_back(i);
    }
    dep[rt]=1;
    dfs1(rt);
    dfs2(rt);
    int q;scanf("%d",&q);
    while(q--)
    {
        int l,r;scanf("%d%d",&l,&r);
        if(l==r)printf("%d\n",a[l]);
        else
        {
            int d=lca(l,r-1);
            int ans=(ll)k[d]*(que(l,d,0)+que(r-1,d,1))%mod;
            printf("%d\n",ans);
        }
    }
	return 0;
}