调一晚上我真的要炸了

（AC必关

$O( n \sqrt (n long n) )$

code:

//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
int max(int a,int b){
	return a>b?a:b;
}
int min(int a,int b){
	return a<b?a:b;
}
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
	return;
}
int n,type,i,j,k,q,a[100001],len=750,B=100,block[10000],l,r,L,R,p,x,last,ans;
vector<int> pos[200001],d[225][125][125];
signed main(){
	//freopen("rvmq_sample2.in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();
	type=read();
	for(i=1;i<=n;i++){
		a[i]=read();
		pos[a[i]].push_back(i);
	}
	for(i=1;i<=n;i++){
		block[i]=(i-1)/len+1;
		for(j=1;j<=B;j++){
			d[block[i]][j][a[i]%j].push_back(a[i]);
		}
	}
	for(i=0;i<=block[n];i++){
		for(j=0;j<=B;j++){
			for(k=0;k<=B;k++){
				if(d[i][j][k].size()>1){
					sort(d[i][j][k].begin(),d[i][j][k].end());
				}
			}
		}
	}
	q=read();
	while(q--){
		l=read();
		r=read();
		L=read();
		R=read();
		p=read();
		x=read();
		if(type){
			l^=last;
			r^=last;
			L^=last;
			R^=last;
			p^=last;
			x^=last;
		}
		ans=0;
		if(q>B||(R-((L-x+p-1)/p*p+x))<=32768){
			for(i=(L-x+p-1)/p*p+x;i<=R;i+=p){
				ans+=upper_bound(pos[i].begin(),pos[i].end(),r)-lower_bound(pos[i].begin(),pos[i].end(),l);
			}
			write(ans);
			puts("");
			last=ans;
		}
		else{
			if(block[l]==block[r]){
				for(i=l;i<=r;i++){
					ans+=L<=a[i]&&a[i]<=R&&a[i]%p==x;
				}
				write(ans);
				puts("");
				last=ans;
			}
			else{
				while((l-1)%len){
					ans+=L<=a[l]&&a[l]<=R&&a[l]%p==x;
					l++;
				}
				while(r%len){
					ans+=L<=a[r]&&a[r]<=R&&a[r]%p==x;;
					r--;
				}
				for(i=block[l];i<=block[r];i++){
					ans+=upper_bound(d[i][p][x].begin(),d[i][p][x].end(),R)-lower_bound(d[i][p][x].begin(),d[i][p][x].end(),L);
				}
				write(ans);
				puts("");
				last=ans;
			}
		}
	}
	return 0;
}