自动搬运

查看原文

来自洛谷，原作者为

	未来姚班zyl 欢迎加入粉丝团！https://www.luogu.com.cn/team/72518|AFO

搬运于2025-08-24 22:46:24，当前版本为作者最后更新于2024-01-04 08:12:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定一个序列 $a_n$，$q$ 次查询 $[l,r]$ 中有多少 $a_i$ 满足 $a_i+x\mod m<a_i+y\mod m$。

题目分析

首先 $x,y$ 对 $m$ 取模。考虑合法的 $a_i$ 在模 $m$ 意义下的范围。

• 当 $x=y$ 时，无解。

• 当 $x<y$ 时，要么都没取模，要么都取模，则合法的 $a_i\in [0,m-1-y]\cup[m-x,m-1]$。

• 当 $x>y$ 时，只有当 $+x$ 时取模，$+y$ 时不取模才合法，此时 $a_i\in[m-x,m-1-y]$。

所以查询相当于对值域上的 $O(\frac{V}{m})$ 个区间查询，$V$ 为值域。分析时间复杂度时将会更替为 $n$。

很容易考虑到将询问差分成两个前缀，然后扫描线，操作变为插入一个数与查询若干区间。

观察到 $m$ 较小时不如直接大力维护模 $m$ 意义下的取值数量，考虑根号分治，设块长为 $B$。

• 对于 $m\le B$ 的查询，直接暴力维护并暴力查询模 $m$ 意义下的取值数量，复杂度 $O(nB+qB)$。

• 对于 $m>B$ 的查询，考虑直接在值域上暴力修改与查询，树状数组即可，复杂度 $O(n\log n+\frac{n}{B}q\log n)$。

根据基本不懂式，$B$ 取 $O(\sqrt{n\log n})$ 时有理论最优复杂度 $O(q\sqrt{n\log n})$，无法通过此题。所以预测常数更大的在线主席树算法也无法通过此题。

观察到第二部分的查询复杂度太高了，而修改复杂度却小到可以忽略。所以我们使用分块维护第二类的修改和查询，第二类复杂度就能变为 $O(n\sqrt n+\frac{n}{B}q)$，当 $B$ 取 $O(\sqrt n)$ 时有理论最优复杂度 $O(q\sqrt n)$，足以通过此题。

#include<bits/stdc++.h>
#define ll long long
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
#define pb push_back
#define E(x) for(auto y:p[x])
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
inline void pf(ll x){if(x<0) putchar('-'),x=-x;if(x>9)pf(x/10);putchar(x%10+48);}
const int N =1e5+5,M=5e5+5;
using namespace std;
int n=read(),m=read(),a[N],out[M],siz;
int ct[510][510];
struct node{
    int x,y,m,k,id;
};
vector<node>p[N];
#define L(x) (x-1)*340+1
#define R(x) min(x*340,100000)
#define bel(x) (x-1)/340+1
int t[1500],val[N];
inline void add(int x){
    int id=bel(x);
    rep(i,id+1,bel(100000))t[i]++;
    rep(i,x,R(id))val[i]++;
}
inline int query(int x){
    x=min(x,100000);
    if(x<=0)return 0;
    return val[x]+t[bel(x)];
}
signed main(){
    siz=330;
    repn(i)a[i]=read();
    repm(i){
        int l=read(),r=read(),x=read(),y=read(),md=read();
        x%=md,y%=md;
        if(x^y)p[r].pb({x,y,md,1,i}),p[l-1].pb({x,y,md,-1,i});
    }
    repn(i){
        rep(j,1,siz)ct[j][a[i]%j]++;
        add(a[i]);
        E(i)if(y.m<=siz){
            rep(j,0,y.m-1)if((j+y.x)%y.m<(j+y.y)%y.m)out[y.id]+=y.k*ct[y.m][j];
        }
        else {
            int l=0;
            while(l<=100000){
                if(y.x<y.y)out[y.id]+=y.k*(query(l+y.m-1-y.y)+query(l+y.m-1)-query(l-1)-query(l+y.m-y.x-1));
                else out[y.id]+=y.k*(query(l+y.m-1-y.y)-query(l+y.m-y.x-1));
                l+=y.m;
            }
        }
        
    }
    repm(i)pf(out[i]),putchar('\n');
    return 0;
}