题目意思

有 $q$ 个询问，每次询问给定的数 $x$ 经过从 $l$ 到 $r$ 的事件后最大的数取模后是多少。

对于一个 $i$ 事件，可以从一下两种操作中选择一种。

• 将该数乘一个数 $b_i$。
• 将该数加上一个数 $a_i$。

注意，这道题的答案不是取模的最大，而是不取模的数的最大值再取模。

题目思路

首先考虑暴力，对于一个事件我们要从两个操作中选取最优的值。

即我们要比较 $x \times (b_i - 1)$ 和 $a_i$ 哪个更大。

题目的范围告诉我们，$a_i \le 10^9+7$，即，当 $2 \le b_i$，且 $a_i \le x$ 时，我们必选乘法。

因为 $a_i \le x$，则 $a_i \le x \times 1$，则当 $b_i - 1 \ge 1$ 时，必选乘法。

固，$b_i \ge 2$ 且 $x \ge a_i$ 时选乘法。

那什么时候存在 $x \ge a_i$ 呢，对于每一次事件，我们至少会使 $x$ 乘上二，即只要执行 $\log(\frac{10^9+7}{x})$ 次操作即可使得 $x \ge a_i$。

所以我们只要暴力枚举到 $x \ge a_i$，即 $x \ge 10^9 + 7$ 时退出，后面全部连乘就可以了。

但显然，事情没那么简单。

我们设从 $p$ 坐标开始后 $x \ge 10^9+7$，则当满足 $p \le i \le n$ 且 $b_i \le 1$ 时，我们不能选择乘法，而是选择加法。

这里很显然吧，那么设 $ans$ 表示从 $p$ 坐标开始后的最大答案。

则 $ans = ((g_1 + g_2) \times g_3 + g_4+ g_5) \times g_6$ 类似这样的情况。

注意上面的式子只是其中一个例子。具体每一项是加还是乘得看那一项的 $b_i$ 决定。

我们按照上述例子拆开式子。

即 $ans = g_1 \times g_3 \times g_6 + g_2 \times g_3 \times g_6 + g_4 \times g_6 + g_5 \times g_6$。

化简一下上述式子。设 $mul_i$ 表示前 $i$ 个数连乘，观察一下式子，对于每一个进行加法的操作来说，当前的 $a_i$ 应该最终变成 $mul_r \times a_i \div mul_i$。

最终的 $ans = \sum_{i = p}^n mul_r \times a_i \div mul_i$。

提出 $mul_r$ 得，$ans = mul_r \times \sum_{i = p}^n a_i \div mul_i$。

显然，对于 $a_i \div mul_i$ 的前缀和是可以提前维护的。

然后这道题就做完了。

注意，这道题有非常多的细节。

其中有一个细节，即当在暴力枚举的过程中，如果一直遇到 $b_i \le 1$ 的情况，显然我们的速度会变得很慢，会超时。

此时我们只要往下跳到下一个 $b_i \ge 2$ 的位置就可以了，记得答案要加上这段区间的 $a_i$ 和。

还有一点需注意，当开始没有士兵，并且后面一段的 $a_i$ 均为零，则乘法操作是无效的，直接跳到后面的第一个坐标 $j$，使得 $a_j$ 不为零。

用数组维护跳的坐标即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,l,r,mod=1e9+7;
long long a[500005],b[500005],h[5000050],h2[5000050],h3[5000050],ik[5000500],h4[5000050];
int x[500050];
int it[500050];
int fast(int a1,int a2)
{
	int g=1,ans=a1;
	while(a2>0)
	{
		if(a2%2==1) g=g*ans%mod;
		ans=ans*ans%mod;
		a2/=2;
	}
	return g;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
	h[0]=1;
	for(int i=1;i<=n;i++) h2[i]=(h2[i-1]+a[i]);//ai的前缀和 
	for(int i=1;i<=n;i++) h[i]=(h[i-1]*b[i])%mod;//bi的前缀积 
	h3[0]=1; 
	for(int i=1;i<=n;i++) h3[i]=h3[i-1]*fast(b[i],mod-2)%mod;//mul(i) 的逆元，因为后面要用到除法 
	for(int i=1;i<=n;i++)
	{
		h4[i]=h4[i-1];
		if(b[i]==1) h4[i]=h4[i]+a[i]*h3[i]%mod;//维护a[i]/mul(i)的前缀和 
		h4[i]%=mod;
	}
	int lst=n+1,lop=n+1;
	for(int i=n;i>=1;i--)
	{
		it[i]=lst;
		ik[i]=lop;
		if(b[i]!=1) lst=i;//it[i]表示下一个b[j]!=0的位置j 
		if(a[i]!=0) lop=i;
	}
	for(int i=1;i<=q;i++)
	{
		cin>>x[i];
		cin>>l>>r;
		long long ip=l+1,man=x[i];
		if(x[i]==0&&a[ip]==0) ip=max(ip,ik[ip]);//注意当起始x=0时，如果后面的a[i]一直为0，则乘法操作是无效的，所以直接跳到下一个a[i]!=0的情况 
		while(man<mod&&ip<=r)
		{
			if(man*b[ip]>=man+a[ip]) man=man*b[ip];
			else man=man+a[ip];
			man+=(h2[min(r,it[ip]-1)]-h2[ip]);//加上跳过位置的a[i]和 
			ip=it[ip];//一直往下跳 
		}
		man%=mod;
		if(ip>r) cout<<man<<"\n";//如果始终不超过1e9+7则直接输出 
		else
		{	
			man=man*h[r]%mod*h3[ip-1]%mod;//乘上后面的b[i] 
			man=man+(h4[r]+mod-h4[ip-1])%mod*h[r]%mod;//加上每一个a[i]/mul(i)*mul(r) 
			man%=mod;
			cout<<man<<"\n";
		}
	}
    return 0;
}
/*
a[i]/mul(i)*mul(r);
((a+b)*c+d)*e=
b*c*e+d*e+a*c*e
	
*/