线段树套分块/主席树！

我们考虑到ai,p,q比较小(<=10000)，所以分类讨论

若p较大，则kp+q的数量就比较少，可以暴力枚举

若p较小，可以预处理，令g[i][j]表示膜i余j的数的个数

我们取这个界为sqrt(maxp)=100

将询问放到每个节点上，依次处理处[1,i]的答案最后ans(l,r)=ans(r)-ans(l-1)即可

#pragma GCC optimize("O3")#pragma G++ optimize("O3")#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;struct dq{ int p,q,k; }; vector
        
          w[100010];int f[10010],g[110][100],n,m,s[100010],ans[100010]; int main(){	scanf("%d%d",&n,&m);	for(int i=1;i<=n;++i) scanf("%d",s+i);	for(int l,r,p,q,i=1;i<=m;++i){		scanf("%d%d%d%d",&l,&r,&p,&q);		w[l-1].push_back((dq){p,q,i});		w[r].push_back((dq){p,q,i});	}	memset(ans,-1,sizeof ans);	for(int i=0,A,p,q,k;i<=n;++i){		f[s[i]]++;		for(int j=1;j<=100;++j) g[j][s[i]%j]++;		for(int j=0,z=w[i].size();j