题解：P9212 「蓬莱人形」

· · 题解

题意简述

给定一个长为 n 的序列 a，q 次询问，每次询问给定 l,r,x,y,m，让你求满足有多少个 i \in [l,r] 满足 (a_i+x)\bmod m<(a_i+y)\bmod m，可以认为 n,q 同阶。

题目做法

这个真的太模板了吧。

首先注意到当 x < y 时，你的询问是在查询 a_i + x 与 a_i + y 都比 m 大或都比 m 小的 i 的个数，等价于两段值域数点，当 x > y 时，你的询问是查询 a_i + x 大于 m 而 a_i + y 小于 m 的 i 的个数，也是一段值域数点。

然后看到是在模 m 意义下，其中 m 每次询问给定，那就很难想不到根号分治，于是分成两部分。

考虑预处理出 b_{i,j} 表示 a_j 在模 i 意义下值，然后分块。

如果询问落在散块显然可以直接暴力，对于落在整块的询问可以统计 f_{i,j,k} 表示第 j 个块在模 i 意义下前 k 个数出现了多少次，询问对于每个块差分一下即可，当然你可以将 j 这一位做前缀和，但是没有意义。

你直接把询问拆成 \mathcal O(n \sqrt n) 个，然后做二维数点。

这个二位数点是有 \mathcal O(n) 次修改，\mathcal O(n \sqrt n) 次询问的，你直接使用 \mathcal O(\sqrt n) - \mathcal O(1) 的分块平衡一下就好了。

代码

完全不卡常，超时了应该是你写法错误。

#include<bits/stdc++.h>
//#define int long long
using namespace std;
int B=300,S=300;
int a[1000001],t[401][100001];
int n,m,ans[1000001],f[401][401][401],tot;
struct node{
    int x,a,b,type,id,mm;
}q[3000001];
int bel[1000001],L[1000001],R[1000001];
bool cmp(node x,node y){
    return x.x<y.x;
} 
int pre[1000001],que[1000001];
void add(int x,int v){
    for(int i=bel[x]+1;i<=bel[100000];i++)pre[i]+=v;
    for(int i=x;i<=R[bel[x]];i++)que[i]+=v;
}
int query(int x){
    if(x<=0)return 0;
    return pre[bel[x]]+que[x];
}
signed main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        bel[i]=(i-1)/S+1;
        R[bel[i]]=i;
    }
    for(int i=n;i>=1;i--)L[bel[i]]=i;
    for(int i=1;i<=B;i++){
        for(int j=1;j<=n;j++){
            t[i][j]=a[j]%i;
            f[i][bel[j]][t[i][j]]++;
        }
        for(int j=1;j<=bel[n];j++){
            for(int k=1;k<=i;k++){
                f[i][j][k]+=f[i][j][k-1];
            }
        }
    }
    for(int i=1;i<=m;i++){
        int l,r,x,y,mod;
        scanf("%d %d %d %d %d",&l,&r,&x,&y,&mod);
        x%=mod;y%=mod;
        if(x==y){
            ans[i]=0;
            continue;
        }
        if(mod<=B){
            if(bel[l]==bel[r]){
                for(int j=l;j<=r;j++){
                    if(((t[mod][j]+x>=mod)?(t[mod][j]+x-mod):(t[mod][j]+x))<((t[mod][j]+y>=mod)?(t[mod][j]+y-mod):(t[mod][j]+y)))ans[i]++;
                }
            }else{
                for(int j=l;j<=R[bel[l]];j++){
                    if(((t[mod][j]+x>=mod)?(t[mod][j]+x-mod):(t[mod][j]+x))<((t[mod][j]+y>=mod)?(t[mod][j]+y-mod):(t[mod][j]+y)))ans[i]++;
                }
                for(int j=L[bel[r]];j<=r;j++){
                    if(((t[mod][j]+x>=mod)?(t[mod][j]+x-mod):(t[mod][j]+x))<((t[mod][j]+y>=mod)?(t[mod][j]+y-mod):(t[mod][j]+y)))ans[i]++;
                }
                if(x<y){
                    int b1=mod-y-1,a2=mod-x,b2=mod-1;
                    for(int j=bel[l]+1;j<=bel[r]-1;j++){
                        ans[i]+=f[mod][j][b1]+f[mod][j][b2]-f[mod][j][a2-1];
                    }
                }else{
                    int a=mod-x,b=mod-y-1;
                    for(int j=bel[l]+1;j<=bel[r]-1;j++){
                        ans[i]+=f[mod][j][b]-f[mod][j][a-1];
                    }
                }
            }
        }else{
            if(x<y){
                int a1=0,b1=mod-y-1,a2=mod-x,b2=mod-1;
                q[++tot]={r,a1,b1,1,i,mod};
                q[++tot]={l-1,a1,b1,-1,i,mod};
                q[++tot]={r,a2,b2,1,i,mod};
                q[++tot]={l-1,a2,b2,-1,i,mod};
            }else{
                int a=mod-x,b=mod-y-1;
                q[++tot]={r,a,b,1,i,mod};
                q[++tot]={l-1,a,b,-1,i,mod};
            }
        }
    }
    for(int i=1;i<=100000;i++){
        bel[i]=(i-1)/S+1;
        R[bel[i]]=i;
    }
    for(int i=100000;i>=1;i--)L[bel[i]]=i;
    sort(q+1,q+1+tot,cmp);
    int idx=1;
    while(idx!=tot+1&&q[idx].x==0)idx++;
    for(int i=1;i<=n;i++){
        add(a[i],1);
        while(idx!=tot+1&&q[idx].x==i){
            int a=q[idx].a,b=q[idx].b;
            while(a<=100000){
                ans[q[idx].id]+=(query(min(100000,b))-query(a-1))*q[idx].type;
                a+=q[idx].mm;
                b+=q[idx].mm;
            }
            idx++;
        }
    }
    for(int i=1;i<=m;i++){
        printf("%d\n",ans[i]);
    }
}

/*

先分析一下，
如果 x<y ，则 [kmod,kmod-y-1] 到 [kmod-x,kmod+mod-1] 是满足的
如果 x>y ，那么 [kmod-x,kmod-y-1] 是满足的 
if 模数小于 mod 简单做一下。
if 模数大于 mod，做一个 q*sqrt_n 的扫描线就好了，简单题。 
*/