这题有个在线的做法，时间复杂度 $O((n+q)\sqrt n)$，空间复杂度 $O(n\sqrt n)$，但由于常数问题没有希望过。

鄙人的做法

#include<bits/stdc++.h>
using namespace std;
const int T=337,S=341,maxn=100004,LIM=100000;
int n,q,L,R,x,y,m,lastb;
int blk[maxn],blkl[S],blkr[S],a[maxn],cntsum[S][maxn],remsum[S][S][S]; 

void build(){
	for(int i=1,j=0;i<=n;i++){
		if(i%T==1){
			j++;
			blkl[j]=i;	
		}
		blk[i]=j;
		blkr[j]=i;
	}
	lastb=blk[n];
	for(int i=1;i<=T;i++)
		for(int j=1;j<=n;j++)
			remsum[i][blk[j]][a[j]%i]++;
	for(int i=1;i<=T;i++)
		for(int j=1;j<=lastb;j++)
			for(int k=1;k<=i;k++)
				remsum[i][j][k]+=remsum[i][j][k-1];
	for(int i=1;i<=n;i++)
		cntsum[blk[i]][a[i]]++;
	for(int i=1;i<=lastb;i++)
		for(int j=1;j<=LIM;j++)
			cntsum[i][j]+=cntsum[i][j-1];
	for(int i=1;i<=lastb;i++)
		for(int j=1;j<=LIM;j++)
			cntsum[i][j]+=cntsum[i-1][j];
}

int brute(int l,int r){
	int ret=0;
	for(int i=l;i<=r;i++)
		if((a[i]+x)%m<(a[i]+y)%m)
			++ret;
	return ret;
}

int qsmall(int l,int r){
	int bl=blk[l],br=blk[r],ret=0,tmp=0;
	if(bl==br)
		return brute(l,r);
	tmp=ret=brute(l,blkr[bl])+brute(blkl[br],r);
	for(int i=bl+1;i<br;i++)
		if(x<y)
			ret+=remsum[m][i][m-y-1]+remsum[m][i][m]-remsum[m][i][m-x-1];
		else
			ret+=remsum[m][i][m-y-1]-remsum[m][i][m-x-1];
	return ret;
}

int qbig(int l,int r){
	int bl=blk[l],br=blk[r],ret=0;
	if(bl==br)
		return brute(l,r);
	ret=brute(l,blkr[bl])+brute(blkl[br],r);
	if(x<y)
		for(int i=0;i*m-x-1<=LIM;i++){
			int low=max(0,i*m-x-1),high=min(LIM,(i+1)*m-y-1);
			int ttt=ret;
			ret+=cntsum[br-1][high]-cntsum[br-1][low];
			ret-=cntsum[bl][high]-cntsum[bl][low];
		}
	else
		for(int i=1;i*m-x-1<=LIM;i++){
			int high=min(LIM,i*m-y-1);
			ret+=cntsum[br-1][high]-cntsum[br-1][i*m-x-1];
			ret-=cntsum[bl][high]-cntsum[bl][i*m-x-1];
		}
	return ret;		
}

void read(int &x){
	char c=getchar();x=0;
	for(;c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+(c^48);
}

void write(int x){
	if(x>9)
		write(x/10);
	putchar(x%10+48);
}

signed main(){
	read(n),read(q);
	for(int i=1;i<=n;i++)
		read(a[i]);
	build();
	while(q--){
		read(L),read(R),read(x),read(y),read(m);
		x%=m,y%=m;
		if(x==y){
			puts("0");
			continue;
		}
		if(m<=T)
			write(qsmall(L,R));
		else
			write(qbig(L,R));
		puts("");
	}
	return 0;
}