P9212 「蓬莱人形」 题解

· · 题解

题目大意

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

题目分析

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

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

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

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

根据基本不懂式，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;
}