P9212 题解
_Ch1F4N_
·
·
题解
显然，我们维护的答案具有 可差分 性，所以转换为 [1,r] 上的查询。
首先，对于 x,y,a_i 先对 m 取模不影响结果。
下面为了方便令 v = a_i。
如果 x>y。
则一定是 x+v-m<y+v。
有 m \leq x+v 且 y+v < m。
转化为 m-x \leq v 且 x<m-y。
得到 v \in[m-x,m-y-1]。
如果 x<y。
答案为所有情况减去 x>y 的情况。
然后维护 [1,r] 上的答案可以离线扫描一遍。
至此问题转化成维护一个集合，支持插入一个数以及查询 \bmod m 意义下 \in[m-x,m-y-1] 的数的数量。
考虑根号分治。
那么对于 m \leq \sqrt n，我们记录所有 \bmod M = k(M \leq \sqrt n) 的数的出现次数，询问就直接回答。插入 O(\sqrt n)，查询 O(\sqrt n)。
[如何写值域分块可以参考往期博客讲解](https://www.luogu.com.cn/blog/520748/zhi-yu-fen-kuai-ru-men)
那么就 $O( (n+q) \sqrt n)$ 的做完了。
参考代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+114;
struct Node{
int x,y,M,id,f;//anser[id]+=f*v f = 1 or -1
};
const int top = 100000;
const int B = 556;
vector<Node> A[maxn];//储存离线询问
int a[maxn];
int anser[maxn];//输出答案
struct block{
int pre[1000];
}cnt[1000];
int cnt_pre[1001];
int ans[1001][1001];
int n,q;
inline void change(int x,int val){
int sum = x/B;
x%=B;
if(x==0) sum--,x+=B;
for(int i=x;i<=B;i++) {
cnt[sum].pre[i]+=val;
}
for(int i=sum;i<=B;i++) cnt_pre[i]+=val;
}
inline int query(int l,int r){
if(l>r) return 0;
int lc=l/B;
l%=B;
int rc=r/B;
r%=B;
if(l==0) lc--,l+=B;
if(r==0) rc--,r+=B;
if(lc==rc) return cnt[lc].pre[r]-cnt[rc].pre[l-1];
int res=0;
res+=cnt[lc].pre[B]-cnt[lc].pre[l-1];
res+=cnt[rc].pre[r];
res+=cnt_pre[rc-1]-cnt_pre[lc];
return res;
}
void set_add(int x){//向集合中插入 x
change(x,1);
for(int j=1;j<B;j++){
ans[j][x%j]++;
}
}
inline int set_pre(int m,int k){//mod m 意义下小于等于 k 的数的数量
if(k<0) return 0;
if(m<B)
{
int sum=0;
for(int j=0;j<=k;j++){
sum+=ans[m][j];
}
return sum;
}
else{
int l=m,r=m+k,res=query(1,k);
while(r<top){
res+=query(l,r);
l+=m;
r+=m;
}
if(l<=top)
res+=query(l,top);
return res;
}
}
inline int set_query(int m,int l,int r){//mod m \in [l,r]
if(l>r||l<0||r<0) return 0;
return set_pre(m,r)-set_pre(m,l-1);
}
void scan(){
for(int i=1;i<=n;i++){
set_add(a[i]);
for(int j=0;j<A[i].size();j++){
Node now = A[i][j];
//处理询问 now
if(now.x%now.M==now.y%now.M){
anser[now.id]+=now.f*0;
}
else if(now.x%now.M>now.y%now.M){
int l=now.M-now.x%now.M,r=now.M-now.y%now.M-1;
anser[now.id]+=now.f*set_query(now.M,l,r);
}
else{
int l=now.M-now.y%now.M,r=now.M-now.x%now.M-1;
anser[now.id]+=now.f*(i-set_query(now.M,l,r));
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=q;i++){
int l,r,x,y,m;
cin>>l>>r>>x>>y>>m;
Node R,L;
R.f=1;
R.id=i;
R.M=m;
R.x=x;
R.y=y;
A[r].push_back(R);
L.f=-1;
L.id=i;
L.M=m;
L.x=x;
L.y=y;
A[l-1].push_back(L);
}//询问离线
scan();
for(int i=1;i<=q;i++) cout<<anser[i]<<'\n';
}
```