ICPC上海网络赛C.Triple

发表于 | 阅读数

题意：

给三个数组$A_n,B_n,C_n$,求满足条件的对数有几对？

PS:!! 垃圾板子一时爽，好板子一直爽！！

  • $\left|A-B\right|\leq C$
  • $\left|C-B\right|\leq A$
  • $\left|A-C\right|\leq B$

也就是A，B，C构成三角形。那么只需要满足

所以对于$c$我们可以求出有多少$|a-b|,|a+b|$满足上面等式
此时就可以想到使用$FFT$求出对数。
又根据容斥原理,对于$C$

此题最坑的在于小范围暴力

代码 
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 8e5 + 10;
inline int read()
{
    char c = getchar();
    int x = 0, f = 1;
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
const double Pi = acos(-1.0);
struct complex
{
    double x, y;
    complex(double xx = 0, double yy = 0) { x = xx, y = yy; }
} a[MAXN], b[MAXN];
complex operator+(complex a, complex b) { return complex(a.x + b.x, a.y + b.y); }
complex operator-(complex a, complex b) { return complex(a.x - b.x, a.y - b.y); }
complex operator*(complex a, complex b) { return complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); } //????????????
int N, M;
int l, r[MAXN];
int limit = 1;
void fast_fast_tle(complex *A, int type)
{
    for (int i = 0; i < limit; i++)
        if (i < r[i])
            swap(A[i], A[r[i]]);              //????????
    for (int mid = 1; mid < limit; mid <<= 1) //????????
    {
        complex Wn(cos(Pi / mid), type * sin(Pi / mid)); //???
        for (int R = mid << 1, j = 0; j < limit; j += R) //R???????,j???????????
        {
            complex w(1, 0);                          //?
            for (int k = 0; k < mid; k++, w = w * Wn) //??????
            {
                complex x = A[j + k], y = w * A[j + mid + k]; //????
                A[j + k] = x + y;
                A[j + mid + k] = x - y;
            }
        }
    }
}
int n;
ll sumz[MAXN], sumf[MAXN];
int aa[MAXN], bb[MAXN], cc[MAXN];
void fft1()
{
    M = N;
    for (int i = 1; i <= n; i++)
    {
        a[aa[i]].x++;
    }
    for (int i = 1; i <= n; i++)
    {
        b[bb[i]].x++;
    }
    while (limit <= M + M)
        limit <<= 1, l++;
    for (int i = 0; i < limit; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    fast_fast_tle(a, 1);
    fast_fast_tle(b, 1);
    for (int i = 0; i <= limit; i++)
        a[i] = a[i] * b[i];
    fast_fast_tle(a, -1);
    sumz[0] = (int)(a[0].x / limit + 0.5);
    for (int i = 0; i <= M + M; i++)
        sumz[i] = sumz[i - 1] + (int)(a[i].x / limit + 0.5);

    for (int i = 0; i <= M + M; i++)
        a[i].x = b[i].y = a[i].y = b[i].x = 0;
    for (int i = 0; i < limit; i++)
        r[i] = 0;
}

void fft2()
{
    M = N;
    for (int i = 1; i <= n; i++)
    {
        a[-aa[i] + M].x++;
    }
    for (int i = 1; i <= n; i++)
    {
        b[bb[i] + M].x++;
    }
    M *= 2;
    while (limit <= M + M)
        limit <<= 1, l++;
    for (int i = 0; i < limit; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    fast_fast_tle(a, 1);
    fast_fast_tle(b, 1);
    for (int i = 0; i <= limit; i++)
        a[i] = a[i] * b[i];
    fast_fast_tle(a, -1);
    sumf[0] = (int)(a[M].x / limit + 0.5);
    //cout<<sumf[0]<<endl;
    for (int i = 1; i <= M; i++)
        sumf[i] = (int)(a[M + i].x / limit + 0.5) + (int)(a[M - i].x / limit + 0.5) + sumf[i - 1];
    for (int i = 0; i <= M + M; i++)
        a[i].x = b[i].y = a[i].y = b[i].x = 0;
    for (int i = 0; i < limit; i++)
        r[i] = 0;
}
void FFTslove()
{
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    limit = 1, l = 0;
    fft2();
    limit = 1, l = 0;
    fft1();
}
int f[MAXN], z[MAXN];
void slove()
{
    for (int i = 0; i <= 4 * N; i++)
        sumf[i] = sumz[i] = f[i] = z[i] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            f[abs(aa[j] - bb[i])]++, z[abs(aa[j] + bb[i])]++;
    sumf[0] = f[0];
    sumz[0] = z[0];
    for (int i = 1; i <= N; i++)
        sumf[i] += sumf[i - 1] + f[i], sumz[i] += sumz[i - 1] + z[i];
    ;
}
int T;
int main()
{

    T = read();
    for (int t = 1; t <= T; t++)
    {
        ll ans = 0;
        n = read();
        N = 0;
        for (int i = 1; i <= n; i++)
            aa[i] = read(), N = max(N, aa[i]);
        for (int i = 1; i <= n; i++)
            bb[i] = read(), N = max(N, bb[i]);
        for (int i = 1; i <= n; i++)
            cc[i] = read(), N = max(N, cc[i]);

        if (n <= 1000)
            slove();
        else
            FFTslove();
        for (int i = 1; i <= n; i++)
            ans += sumf[cc[i]] - sumz[cc[i] - 1];
        printf("Case #%d: %lld\n", t, ans);
    }
    return 0;
}