胡闹 卷积练习题

题目大意

给定两个长度为$n$的非负整数数组$a,b$,求
$$
\sum_{i=1}^n\sum_{j=1}^n\lfloor\sqrt{|a_i-b_j|}\rfloor
$$

Notes

$1\le n\le 10^6$,$0\le a_i,b_i\le 3\times 10^6$,$\sum a_i,\sum b_i\le 10^7$

解析

这个题目啊,interesting。

本来题目名字叫做“卷积练习题”,但是正解和卷积一点关系都没有。

一个套路,我们注意到$0\le a_i$并且$\sum a_i\le10^7$,那么我们知道$a_i$的取值一定是$O(\sqrt{10^7})$的?

为什么呢?考虑抽屉原理。从$0$开始,放$1,2,3,4…$,那么放了$n$个的时候,必然有$\sum a_i\ge\frac{n\times(n-1)}{2}$。

所以$a_i$取值一定是$O(\sqrt{10^7})$的。

我们又注意到,$\lfloor\sqrt{|a_i-b_j|}\rfloor\le \sqrt{10^7}$。

那么就很简单了,枚举$a$中每一个出现的数,然后枚举$\lfloor\sqrt{|a_i-b_j|}\rfloor$,$b$中合法的数一定是在两个区间内,统计的话直接及一个前缀和就好了。

Code

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
#define REP(i, s, e) for (int i = s; i <= e ;i++)
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)

#include <iostream>
#include <cstdio>
#include <cmath>
#define double long double
#define int long long

using namespace std;
const int maxn = 1e6 + 10, maxL = 4200000;

int n, ans, a[maxn], b[maxn], cnt[3000005];
int s[3000005];
signed main()
{
#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif
cin >> n;
REP(i, 1, n) scanf("%lld", a + i), a[i]++;
REP(i, 1, n) scanf("%lld", b + i), b[i]++;
if (n <= 2000)
{
REP(i, 1, n)
REP(j, 1, n)
ans += floor(sqrt(abs(a[i] - b[j])));
}
else
{
REP(i, 1, n) cnt[a[i]]++;
REP(i, 1, n) s[b[i]]++;
REP(i,1,3000001)s[i]+=s[i-1];
REP(A, 1, 3000001)
if (cnt[A])
REP(C, 1, 1732)
{
int l, r;
l = A - C * C - C * 2, r = A - C * C;
if (max(l, 1ll) <= min(r, 3000001ll))
{
chkmax(l, 1ll);chkmin(l, 3000001ll);
chkmax(r, 1ll);chkmin(r, 3000001ll);
ans += C * cnt[A] * (s[r] - s[l-1]);
}
l = A + C * C, r = A + C * C + C * 2;
if (max(l, 1ll) <= min(r, 3000001ll))
{
chkmax(l, 1ll);chkmin(l, 3000001ll);
chkmax(r, 1ll);chkmin(r, 3000001ll);
ans += C * cnt[A] * (s[r] - s[l-1]);
}
}
}
cout << ans << endl;
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×