对于每一个询问，先对 $x$，$y$，$a_i$ 取模。

然后对 $x$，$y$ 分类讨论：

  • $x = y$ 答案为 $0$
  • $x > y$ 即，$a_i+x$ 取模，$a_i+y$ 不取模。等价于 $a_i \in [m-x,m-y-1]$
  • $x < y$ 等价于 $x > y$ 的反面，像上一种情况计算，然后用总个数减去答案即可。

然后由于答案的可差分性，$[l,r]$ 可以拆分成 $[1,l-1]$ 和 $[1,r]$ 两个区间的询问。

现在我们考虑从前往后扫 $a$，维护每一个询问。

我们考虑对 $m$ 根号分治。

当 $m \leq \sqrt n$ 时：

需要对于每一个 $m \leq \sqrt n$ 支持单点修改，对于每一个询问支持区间查询。

共 $O(n \sqrt n)$ 次修改，$O(n)$ 次查询。

平衡时间复杂度，可以使用数组做到 $O(1)$ 修改，$O(\sqrt n)$ 查询。

当 $m > \sqrt n$ 时：

难点在于 $a_i$ 的取模。

我们可以 $a_i$ 不变，区间同时不断增大 $m$，这样统计是等价的。

需要支持单点修改，区间查询。

同时我们发现这样查询的次数时是 $O(n \sqrt n)$ 的，修改的次数是 $O(n)$。

平衡时间复杂度，使用一个 $O(\sqrt n)$ 修改，$O(1)$ 查询的值域分块即可。

细说分块：

我们维护所有块的前缀和与块内的前缀和即可。

块长 $\sqrt n$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
const int maxm=5e5;
const int B=320;
struct Node{
    int l,r,p,id;
    Node(int il,int ir,int ip,int iid){
        l=il,r=ir,p=ip,id=iid;
    }
    Node(){}
};
int n,q;
int a[maxn+5];
int ans[maxm+5];
int len[maxm+5];
vector<Node> V[maxn+5];
int f[B+5][B+5];
int id[maxn+5];
int L[B+5],R[B+5];
int c[maxn+5];
int s[B+5];
inline void Build(){
    for(int i=1;i<=maxn;i++){
        id[i]=i/B;
        if(!L[id[i]]) L[id[i]]=i;
        R[id[i]]=i;
    }
}
inline void Modify(int x){
    for(int i=id[x];i<=B;i++) s[i]++;
    for(int i=x;i<=R[id[x]];i++) c[i]++;
}
inline int Query(int x){
    return (id[x]?s[id[x]-1]:0)+c[x];
}
signed main(){
    int l,r,x,y,p;
    int tmp;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=q;i++){
        scanf("%d%d%d%d%d",&l,&r,&x,&y,&p);
        x%=p,y%=p;
        if(x==y) continue;
        if(x<y) len[i]=r-l+1,swap(x,y);
        V[l-1].push_back(Node(p-x,p-y-1,p,-i));
        V[r].push_back(Node(p-x,p-y-1,p,i));
    }
    Build();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=B;j++) f[j][a[i]%j]++;
        Modify(a[i]);
        for(Node j:V[i]){
            tmp=0;
            if(j.p<=B) for(int k=j.l;k<=j.r;k++) tmp+=f[j.p][k];
            else for(int k=0;k+j.l<=maxn;k+=j.p)
                tmp+=Query(min(k+j.r,maxn))-Query(k+j.l-1);
            if(j.id<0) ans[-j.id]-=tmp;
            else ans[j.id]+=tmp;
        }
    }
    for(int i=1;i<=q;i++){
        if(len[i]) printf("%d\n",len[i]-ans[i]);
        else printf("%d\n",ans[i]);
    }
    return 0;
}