洛谷 5398 「Ynoi 2018」GOSICK

发表于 | 分类于 | 13

「点缀光辉的第十四分块」。

首先二离没话说。
然后发现这个贡献貌似有点麻烦。

以下复杂度中均视 n,m 和值域同阶。

设 c(x,[l,r]) 表示 x 对 [l,r] 的贡献。
那么根据套路需要计算两种贡献：

第一种，形如 c(i,[1,i))：
即求出 [1,i) 内 ai 的倍数 / 约数个数。
前者可以对于 j∈[1,i)，枚举 aj 的约数累加贡献；
后者可以枚举 ai 的约数累加出现次数作为贡献。

第二种，形如 c(i,[1,x]) (i∈[l,r])：
即求出 [1,x] 内 ai 的倍数 / 约数个数。
前者同样是平凡的，考虑同上处理。
但对于后者，考虑到如此询问有 O(n√n) 种，则不能沿用以上做法。

考虑对于 j∈[1,x]，枚举 aj 的倍数累加贡献。但这样在 aj 较小时是 O(n) 的。
那么自然而然想到根号分治，设阈值 T，当 aj>T 时直接如此累加贡献。
否则，实际上可以考虑一个这样的方式：枚举一个不超过 T 的 d 计算其贡献，具体地，求出 [1,x] 内 d 的出现次数乘以 [l,r] 内 d 的倍数的个数。
注意到后者实际上可以用前缀和处理，而前者仍然是平凡的。

这样算下来时间复杂度是 O(n√n+n2T+nT)，空间复杂度是 O(nT)。
看起来 T=√n 就行了，但是这题太紧了，导致空间开不下，而线性空间的处理方式会被卡 cache。
于是 T 取小一点，我块长取 799，T 取 150，然后就直接过去了完全没卡常（
（当时是因为洛谷评测机变快了 lxl 没发现所以没卡我，不过现在也只要不用 vector 预处理每个数的约数，然后带个 O2 就能过了）

另外，一开始全 WA 差点吓死我，拍了一下发现调试信息没删，删了就过了（

代码： 

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int N = 5e5;
const int BLK = 799;
const int LIM = 150;
int n,m,a[N + 5];
int D[(N << 5) + 5],*d[N + 5],c[N + 5];
int block = BLK,pos[N + 5];
int lim = LIM;
long long ans[N + 5];
struct s_query
{
    int l,r,id;
    long long ans;
    inline bool operator<(const s_query &o) const
    {
        return pos[l] ^ pos[o.l] ? l < o.l : ((pos[l] & 1) ? r < o.r : r > o.r);
    }
} qry[N + 5];
struct s_contrib
{
    int l,r,id,w;
};
vector<s_contrib> vec[N + 5];
int cnt1[N + 5],cnt2[N + 5],cnt3[N + 5];
int sum1[N + 5],sum2[N + 5];
int cnt[N + 5][LIM + 5];
int main()
{
    for(register int i = 1;i <= N;++i)
        for(register int j = i;j <= N;j += i)
            ++c[j];
    d[1] = D;
    for(register int i = 1;i <= N;++i)
        d[i + 1] = d[i] + c[i],c[i] = 0;
    for(register int i = 1;i <= N;++i)
        for(register int j = i;j <= N;j += i)
            d[j][++c[j]] = i;
    read(n),read(m);
    for(register int i = 1;i <= n;++i)
        read(a[i]),pos[i] = (i - 1) / block + 1;
    for(register int i = 1;i <= m;++i)
        read(qry[i].l),read(qry[i].r),qry[i].id = i;
    for(register int i = 1;i <= n;++i)
    {
        sum1[i] = cnt1[a[i]];
        for(register int j = 1;j <= c[a[i]];++j)
            sum2[i] += cnt2[d[a[i]][j]],++cnt1[d[a[i]][j]];
        for(register int j = 1;j <= lim;++j)
            cnt[i][j] = cnt[i - 1][j] + !(a[i] % j);
        ++cnt2[a[i]];
    }
    sort(qry + 1,qry + m + 1);
    for(register int i = 1,l = 1,r = 0;i <= m;++i)
    {
        l < qry[i].l && (vec[r].push_back((s_contrib){l,qry[i].l - 1,i,-1}),1);
        for(;l < qry[i].l;qry[i].ans += sum1[l] + sum2[l],++l);
        l > qry[i].l && (vec[r].push_back((s_contrib){qry[i].l,l - 1,i,1}),1);
        for(;l > qry[i].l;qry[i].ans -= sum1[l - 1] + sum2[l - 1],--l);
        r < qry[i].r && (vec[l - 1].push_back((s_contrib){r + 1,qry[i].r,i,-1}),1);
        for(;r < qry[i].r;qry[i].ans += sum1[r + 1] + sum2[r + 1],++r);
        r > qry[i].r && (vec[l - 1].push_back((s_contrib){qry[i].r + 1,r,i,1}),1);
        for(;r > qry[i].r;qry[i].ans -= sum1[r] + sum2[r],--r);
    }
    memset(cnt1,0,sizeof cnt1),memset(cnt2,0,sizeof cnt2);
    for(register int i = 1;i <= n;++i)
    {
        for(register int j = 1;j <= c[a[i]];++j)
            ++cnt1[d[a[i]][j]];
        ++cnt2[a[i]];
        if(a[i] > lim)
            for(register int j = a[i];j <= N;j += a[i])
                ++cnt3[j];
        for(vector<s_contrib>::iterator it = vec[i].begin();it != vec[i].end();++it)
        {
            for(register int j = it->l;j <= it->r;++j)
                qry[it->id].ans += it->w * (cnt1[a[j]] + cnt3[a[j]] - 2 * (j <= i));
            for(register int j = 1;j <= lim;++j)
                qry[it->id].ans += (long long)it->w * cnt2[j] * (cnt[it->r][j] - cnt[it->l - 1][j]);
        }
    }
    for(register int i = 1;i <= m;++i)
        ans[qry[i].id] = (qry[i].ans += qry[i - 1].ans) + qry[i].r - qry[i].l + 1;
    for(register int i = 1;i <= m;++i)
        printf("%lld\n",ans[i]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment