题外话
-
是图老师推的题捏。
-
第 70 道紫，纪念一下。
-
写这题写了好久啊，都要调崩溃了，终于过了/ll
-
之前一直没尝试过写值域分块，今天第一次写竟然没出锅。
\(\text{Links}\)
题意
给定一个长度为 \(n\) \((n\le 10^5)\) 的序列 \(a\) \((1\le a_i\le 10^5)\)，你需要回答 \(q\) \((q\le 5\times 10^5)\) 次询问（非强制在线），每次询问给出参数 \(l,r,x,y,m\) \((1\le l\le r\le n,1\le x,y,m\le 10^5)\)，求有多少个 \(i\in[l,r]\) 满足 \((a_i+x)\mod m\lt (a_i+y)\mod m\)。
题解
先考虑转化一下那个不等式，这一步应该不是很难，我的方法是，肯定先把 \(x,y\) 都对 \(m\) 取模，然后钦定 \(x\lt y\)，然后分别以 \(x\) 和 \(y\) 为断点画出两条以 \(\mod m\) 的余数环断开形成的链。此时容易发现，记 \(a'_i=a_i\mod m\)，则有当 $a'_i\in [0,m-y)\cup [m-x,m) $ 时，\(i\) 满足条件。\(x\gt y\) 的情况交换 \(x\) 和 \(y\)，然后用区间长度减去算出的结果就是答案；\(x=y\) 的情况显然无解。
于是问题转化为每次给定一个下标范围 \([l,r]\) 和一个值域范围 \([x,y]\) 以及 \(m\)，求 \([l,r]\) 中有多少数对 \(m\) 取模后的值在范围 \([x,y]\) 中。
这个计数问题的答案显然具有可差分性，所以我们每次在 \(r\) 的地方存下这个询问，并给它赋一个正号（\(+\)），再在 \(l-1\) 的地方存下这个询问，并给它赋一个负号（\(-\)），然后我们只需要用这种方式把询问离线下来从 \(1\) 到 \(n\) 扫一遍，中途遇到挂了询问的地方就计算 \([1,i]\) 的答案，然后根据 \(+/-\) 把贡献丢给对应的询问就行了。
然后考虑怎么维护这个计数。其实挺简单。
取模。直接上根号分治。设值域上限为 \(V\)。
当 \(m\le \sqrt V\) 时，我们直接开个桶 \(cnt_{i,j}\) 表示 \(\mod i\) 结果为 \(j\) 的数有多少个，每次 \(O(\sqrt V)\) 插入，\(O(\sqrt V)\) 查询即可，则此部分复杂度为 \(O(n\sqrt V+q\sqrt V)\)。
当 \(m\gt \sqrt V\) 时，我们每次把目标值域范围暴力地往上跳，每跳一次上下界同时 \(+m\)，所以最多跳 \(O(\sqrt V)\) 到顶就可以结束了。于是我们每次要回答有多少个 \(i\) 满足 \(a_i\in [l,r]\)，值域分块即可。因为总共有 \(O(q\sqrt V)\) 次查询和 \(O(n)\) 次插入，所以得写一个 \(O(\sqrt V)\) 插入，\(O(1)\) 查询的值域分块来平衡复杂度，每次记录块内前缀和、块内后缀和以及块间前缀和即可。此部分复杂度为 \(O(n\sqrt V+q\sqrt V)\)。
总时间复杂度为 \(O(q\sqrt V+q\sqrt V)\)，只要不是实现得太烂的都能过。
\(\text{Code:}\)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define re register
const int N=1e5+113,M=5e5+113,SQ=370;
int n,m,a[N],L=1,R,cnt[N],ans[M],c[N];
int s[SQ][SQ];
int T,idv[N],vl[N],vr[N],vmax,pre[N],suf[N],sv[N];
struct query{
int f,x,y,mod,id;
};
vector<query>v[N];
#define pb push_back
il int read(){
re 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<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
il void init(){
for(re int i=1;i<=vmax;i++)idv[i]=(i-1)/T+1;
for(re int i=1;i<=idv[vmax];i++)
vl[i]=vr[i-1]+1,vr[i]=i*T;
vr[idv[vmax]]=vmax;
}
il int Ask(int x,int y,int mod){
if(x>y)return 0;
int res=0;
for(re int i=x;i<=y;i++)res+=s[mod][i];
return res;
}
il int solve_le(int l,int r,int x,int y,int mod){
if(mod==1)return 0;
if(x==y)return 0;
bool flg=0;
if(x>y)swap(x,y),flg=1;
int res=Ask(mod-x,mod-1,mod)+Ask(0,mod-y-1,mod);
return flg?r-l+1-res:res;
}
il int GetCntV(int l,int r){
if(idv[l]==idv[r])return (l==vl[idv[l]])?pre[r]:pre[r]-pre[l-1];
return suf[l]+pre[r]+sv[idv[r]-1]-sv[idv[l]];
}
il int solve_gt(int l,int r,int x,int y,int mod){
if(mod==1)return 0;
if(x==y)return 0;
bool flg=0;
if(x>y)swap(x,y),flg=1;
int res=0,now=mod;
if(x){
int l1=mod-x,r1=mod-1;
while(1){
res+=GetCntV(l1,r1);
if(r1==vmax)break;
if(l1+mod>vmax)break;
l1+=mod,r1+=mod;
r1=min(r1,vmax);
}
}
int l2=0,r2=mod-y-1;
while(1){
res+=GetCntV(l2,r2);
if(r2==vmax)break;
if(l2+mod>vmax)break;
l2+=mod,r2+=mod;
r2=min(r2,vmax);
}
return flg?r-l+1-res:res;
}
il void Add(int x){
for(re int i=1;i<=T;i++)s[i][x%i]++;
for(re int i=x;i<=vr[idv[x]];i++)pre[i]++;
for(re int i=vl[idv[x]];i<=x;i++)suf[i]++;
for(re int i=idv[x];i<=idv[vmax];i++)sv[i]++;
}
int main(){
n=read(),m=read();
for(re int i=1;i<=n;i++)a[i]=read(),vmax=max(vmax,a[i]);
T=sqrt(vmax);
for(re int i=1;i<=m;i++){
int l=read(),r=read(),x=read(),y=read(),mod=read();
x%=mod,y%=mod;
if(l>1)v[l-1].pb({-1,x,y,mod,i});
v[r].pb({1,x,y,mod,i});
}
init();
for(re int i=1;i<=n;i++){
Add(a[i]);
for(re query j:v[i]){
if(j.mod>T)ans[j.id]+=j.f*solve_gt(1,i,j.x,j.y,j.mod);
else ans[j.id]+=j.f*solve_le(1,i,j.x,j.y,j.mod);
}
}
for(re int i=1;i<=m;i++)cout<<ans[i]<<'\n';
return 0;
}