「蓬莱人形」题解

题目大意

Solution

这种有模数、记录数量、范围 1e5 的题，多半是根号分治。

因为模数小时，区间数量多、区间内元素少；模数大时，区间数量少、区间内元素多。相当于两个极端，两种极端各跑一种算法，可以通过。

而通常我们把判断模数是大还是小的阈值设为 $\sqrt{n}$。

对于本题而言，当 $m\leq \sqrt{n}$ 时，我们用 $\sqrt{n}$ 个桶 $sum_{i,j}$ 表示模数为 $i$ 时结果为 $j$ 的数量。

当 $m > \sqrt{n}$ 时，此时 $\lceil \frac{n}{m}\rceil < \sqrt{n}$，所以可以暴力枚举 $\lceil \frac{n}{m}\rceil$。考虑到每个 $\lceil \frac{n}{m}\rceil$ 贡献的是一段区间，我们可以维护一个分块前缀和。

上面是根号分治部分，剩下怎么做呢？

首先区间 $[l,r]$ 直接转化成 $[1,l-1]$ 和 $[1,r]$ 两个区间，用类似前缀和的思想来获得 $[l,r]$ 的贡献。

转化成这样之后就可以把询问离线下来扫描线了。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80


#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ft first
#define sd second

const int N=5e5+5,M=500+5,B=320;

int n,m,sq;
int a[N];
int sum[M][M];
int pre1[M],pre2[M][M];
int qx[N],qy[N],qm[N];
vector<pii> vec[N];
int ans[N];

void add(int x)
{
    int Id=x/B+1,_Id=x%B;
    for(int i=_Id;i<B;i++)
        pre2[Id][i]++;
    for(int i=Id;i<=(100000)/B+1;i++)
        pre1[i]++;
}

int query(int x)
{
    int Id=x/B+1,_Id=x%B;
    return pre1[Id-1]+pre2[Id][_Id];
}

int work(int x,int y,int m)
{
    if(x<y) swap(x,y);
    int l=m-x,r=m-y-1,res=0;
    if(m<sq){
        for(int i=l;i<=r;i++)
            res+=sum[m][i];
        return res;
    }
    for(int L=l,R=r;L<=100000;L+=m,R=min(R+m,100000))
        res+=query(R)-query(L-1);
    return res;
}

signed main()
{
    scanf("%d%d",&n,&m);
    sq=sqrt(n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1,l,r;i<=m;i++){
        scanf("%d%d%d%d%d",&l,&r,&qx[i],&qy[i],&qm[i]);
        qx[i]%=qm[i],qy[i]%=qm[i];
        if(qx[i]==qy[i])
            continue;
        vec[l-1].push_back({i,-1});
        vec[r].push_back({i,1});
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<sq;j++)
            sum[j][a[i]%j]++;
        add(a[i]);
        for(pii j:vec[i]){
            int p=j.ft;
            int tmp=work(qx[p],qy[p],qm[p]);
            if(qx[p]<qy[p])
                tmp=i-tmp;
            ans[p]+=j.sd*tmp;
        }
    }
    for(int i=1;i<=m;i++){
        if(qx[i]==qy[i])
            puts("0");
        else
            printf("%d\n",ans[i]);
    }
    return 0;
}

「蓬莱人形」 题解

题目大意

Solution

代码

「蓬莱人形」题解