本文共 1172 字，大约阅读时间需要 3 分钟。

任何一个子矩阵的和都可以写成如下形式

$(prea[r_1]-prea[l_1-1])\ast (preb[r_2]-preb[l_2-1])$

要让这个和在$[L,R]$内

枚举$prea[r_1]-prea[l_1-1]$，这部分复杂度$O(n^2)$

然后把所有$preb[r_2]-preb[l_2-1]$预处理放在一个数组里

使用二分查找有多少满足条件的即可

#include 
   
    using namespace std;#define int long longconst int maxn = 1e6+10;int n,m,L,R,ans,a[maxn],b[maxn],w[maxn];signed main(){
   	cin >> n >> m >> L >> R;	for(int i=1;i<=n;i++)	cin >> a[i];	for(int i=1;i<=m;i++)	cin >> b[i];	for(int i=1;i<=m;i++)	{
   		int now = 0;		for(int j=i;j<=m;j++)		{
   			now += b[j];			w[++w[0]] = now;		}	}	sort( w+1,w+1+w[0] );	for(int i=1;i<=n;i++)	{
   		int now = 0;		for(int j=i;j<=n;j++)		{
   			now += a[j];			//now*x>=L就是 now*x<=R			int l = L/now-(L%now==0);//需要大于l			int r = R/now;//需要小于等于r			int index1 = upper_bound(w+1,w+1+w[0],l)-w;			int index2 = upper_bound(w+1,w+1+w[0],r)-w; 			if( index1==w[0]+1 )	continue;//没有大于l,直接否			ans += index2-index1;		}	}	cout << ans;}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/112818564 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！