分类：cqd分治

HDU 5721 Palace 求最近点对 + 对答案的贡献


Palace

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

The last trial Venus imposes on Psyche is a quest to the underworld. She is to take a box and obtain in it a dose of the beauty of Prosperina, queen of the underworld.
There are $ n $ palaces in the underworld, which can be located on a 2-Dimension plane with $ (x, y) $ coordinates (where $ x, y $ are integers). Psyche would like to find the distance of the closest pair of two palaces. It is the password to enter the main palace.
However, the underworld is mysterious and changes all the time. At different times, exactly one of the $ n $ palaces disappears.
Psyche wonders what the distance of the closest pair of two palaces is after some palace has disappeared.
Print the sum of the distance after every single palace has disappeared.
To avoid floating point error, define the distance $ d $ between palace $ (x_1, y_1) $ and $ (x_2, y_2) $ as $ d = (x_1 - x_2) ^ 2 + (y_1 - y_2) ^ 2 $.

Input

The first line of the input contains an integer $ T $ $ (1 \le T \le 5) $, which denotes the number of testcases.
For each testcase, the first line contains an integers $ n $ $ (3 \le n \le 10 ^ 5) $, which denotes the number of temples in this testcase.
The following $ n $ lines contains $ n $ pairs of integers, the $ i $-th pair $ (x, y) $ $ (-10 ^ 5 \le x,y \le 10 ^ 5) $ denotes the position of the $ i $-th palace.

Output

For each testcase, print an integer which denotes the sum of the distance after every single palace has disappeared.

Sample Input

1
3
0 0
1 1
2 2

Sample Output

12

Hint

If palace $ (0,0) $ disappears，$ d = (1-2) ^ 2 + (1 - 2) ^ 2 = 2 $; If palace $ (1,1) $ disappears，$ d = (0-2) ^ 2 + (0 - 2) ^ 2 = 8 $; If palace $ (2,2) $ disappears，$ d = (0-1) ^ 2 + (0-1) ^ 2 = 2 $; Thus the answer is $ 2 + 8 + 2 = 12 $。

Source

BestCoder 2nd Anniversary
 

题意

给出n个点的坐标，假设第i个点消失后，最近点对的距离的平方为d，求d的和。

思路

会发现，这n个点的最近点对的距离对答案的贡献系数为(n-2)，因为除了删除这两个最近点对，其它点的删除都不会影响最近点对的距离。后面分别删除这两个点，再求出最近点对的距离求和即可。求最近点对可以用KD-tree或者CDQ分治。
 
KD-tree
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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct FastIO
{
static const int S = 1310720;
int wpos;
char wbuf[S];
FastIO() : wpos(0) {}
inline int xchar()
{
static char buf[S];
static int len = 0, pos = 0;
if(pos == len)
pos = 0, len = fread(buf, 1, S, stdin);
if(pos == len) return -1;
return buf[pos ++];
}
inline int xint()
{
int s = 1, c = xchar(), x = 0;
while(c <= 32) c = xchar();
if(c == '-') s = -1, c = xchar();
for(; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x * s;
}
inline void wchar(int x)
{
if(wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
wbuf[wpos ++] = x;
}
inline void wint(LL x)
{
if(x < 0) wchar('-'), x = -x;
char s[24];
int n = 0;
while(x || !n) s[n ++] = '0' + x % 10, x /= 10;
while(n--) wchar(s[n]);
}
~FastIO()
{
if(wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
}
} io;
const int maxn = 1e5 + 5;
int idx;
struct Point
{
int x[2];
bool enable;
bool operator < (const Point &b) const
{
return x[idx] < b.x[idx];
}
} p[maxn];
LL GetDist(Point &a, Point &b)
{
return (LL)(a.x[0] - b.x[0]) * (a.x[0] - b.x[0]) + (LL)(a.x[1] - b.x[1]) * (a.x[1] - b.x[1]);
}
void build(int L, int R, bool dep = 0)
{
if(L > R) return ;
int mid = L + R >> 1;
idx = dep ;
nth_element(p + L, p + mid, p + R + 1);
build(L, mid - 1, dep ^ 1);
build(mid + 1, R, dep ^ 1);
}
void query(int L, int R, Point &local, int &ansidx, LL &ansdist, bool dep = 0)
{
if(L > R) return;
int mid = L + R >> 1;
pair<int, int> x = make_pair(L, mid - 1), y = make_pair(mid + 1, R);
if(local.x[dep] >= p[mid].x[dep]) swap(x, y);
query(x.first, x.second, local, ansidx, ansdist, dep ^ 1);
if(p[mid].enable)
{
LL dis = GetDist(p[mid], local);
if(dis < ansdist)
{
ansdist = dis;
ansidx = mid;
}
}
if((LL)(local.x[dep] - p[mid].x[dep]) * (local.x[dep] - p[mid].x[dep]) < ansdist)
query(y.first, y.second, local, ansidx, ansdist, dep ^ 1);
}
int n;
int match[maxn];
LL find_closest(int &idx1, int &idx2)
{
memset(match, 0, sizeof(match));
LL mindist = __LONG_LONG_MAX__;
for(int i = 1; i <= n; i++)
{
p[i].enable = 0;
LL dist = __LONG_LONG_MAX__;
int id;
query(1, n, p[i], id, dist);
if(dist < mindist)
{
mindist = dist;
idx1 = i;
idx2 = id;
}
match[i] = id;
p[i].enable = 1;
}
return mindist;
}
LL re_find(int id)
{
LL ret = __LONG_LONG_MAX__ ;
p[id].enable = 0;
for(int i = 1; i <= n; i++)
{
if(i == id) continue;
if(match[i] == id)
{
LL dist = __LONG_LONG_MAX__;
int idt;
p[i].enable = 0;
query(1, n, p[i], idt, dist);
p[i].enable = 1;
ret = min(ret, dist);
}
else ret = min(ret, GetDist(p[i], p[match[i]]));
}
p[id].enable = 1;
return ret;
}
int main()
{
int T = io.xint();
while(T--)
{
n = io.xint();
for(int i = 1; i <= n; i++)
{
p[i].x[0] = io.xint();
p[i].x[1] = io.xint();
p[i].enable = 1;
}
build(1, n);
int idx1, idx2;
LL ans = find_closest(idx1, idx2) * (n - 2);
if(n > 2)
{
ans += re_find(idx1);
ans += re_find(idx2);
}
io.wint(ans);
io.wchar('\n');
}
return 0;
}

 

CDQ分治

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;
struct Point
{
int x, y, idx;
LL operator * (const Point &b) const
{
return (LL)(x - b.x) * (x - b.x) + (LL)(y - b.y) * (y - b.y);
}
};
void cdq(int L, int R, Point p[], int &idx1, int &idx2, LL &dist)
{
if(L >= R) return;
if(L + 1 == R)
{
LL pdist = p[L] * p[R];
if(pdist < dist)
{
dist = pdist;
idx1 = p[L].idx;
idx2 = p[R].idx;
}
return;
}
int mid = L + R >> 1;
cdq(L, mid, p, idx1, idx2, dist);
cdq(mid + 1, R, p, idx1, idx2, dist);
static Point pt[maxn];
int cnt = 0;
for(int i = L; i <= R; i++)
if(abs(p[i].x - p[mid].x) < dist) pt[++cnt] = p[i];
sort(pt + 1, pt + 1 + cnt, [](Point & a, Point & b)
{
if(a.y == b.y) return a.x < b.x;
else return a.y < b.y;
});
for(int i = 1; i <= cnt; i++)
for(int j = i + 1; j <= cnt && pt[j].y - pt[i].y < dist; j++)
{
LL pdist = pt[i] * pt[j];
if(pdist < dist)
{
dist = pdist;
idx1 = pt[i].idx;
idx2 = pt[j].idx;
}
}
}
Point p[maxn], p2[maxn];
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d %d", &p[i].x, &p[i].y);
p[i].idx = i;
}
sort(p + 1, p + 1 + n, [](Point & a, Point & b)
{
if(a.x == b.x)return a.y < b.y;
else return a.x < b.x;
});
LL ans = 0;
LL dist = __LONG_LONG_MAX__;
int idx1, idx2;
cdq(1, n, p, idx1, idx2, dist);
ans += dist * (n - 2);
int cnt = 0;
for(int i = 1; i <= n; i++)
if(p[i].idx != idx1) p2[++cnt] = p[i];
dist = __LONG_LONG_MAX__;
cdq(1, n - 1, p2, idx1, idx1, dist);
ans += dist;
cnt = 0;
for(int i = 1; i <= n; i++)
if(p[i].idx != idx2) p2[++cnt] = p[i];
dist = __LONG_LONG_MAX__;
cdq(1, n - 1, p2, idx2, idx2, dist);
ans += dist;
printf("%lld\n", ans);
}
return 0;
}

 

 

 
 

HDU 5730 Shell Necklace FFT+cdq分治优化DP

http://acm.hdu.edu.cn/showproblem.php?pid=5730

Shell Necklace

Time Limit: 16000/8000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Perhaps the sea‘s definition of a shell is the pearl. However, in my view, a shell necklace with n beautiful shells contains the most sincere feeling for my best lover Arrietty, but even that is not enough.
Suppose the shell necklace is a sequence of shells (not a chain end to end). Considering i continuous shells in the shell necklace, I know that there exist different schemes to decorate the i shells together with one declaration of love.
I want to decorate all the shells with some declarations of love and decorate each shell just one time. As a problem, I want to know the total number of schemes.
Input
There are multiple test cases(no more than 20 cases and no more than 1 in extreme case), ended by 0.
For each test cases, the first line contains an integer n , meaning the number of shells in this shell necklace, where 1≤n≤105 . Following line is a sequence with n non-negative integer a1,a2,…,an, and ai≤107 meaning the number of schemes to decorate i continuous shells together with a declaration of love.
 Output
For each test case, print one line containing the total number of schemes module 313 (Three hundred and thirteen implies the march 13th, a special and purposeful day).
 Sample Input
3
1 3 7
4
2 2 2 2
0
 Sample Output

14 54

Hint
 

For the first test case in Sample Input, the Figure 1 provides all schemes about it. The total number of schemes is 1 + 3 + 3 + 7 = 14.

 

 Author
HIT
 Source
2016 Multi-University Training Contest 1
 题意：装饰一条链上的n个珠子，装饰任意连续i个珠子的方案数是a[i]，每个珠子只能被装饰一次，求装饰这n个珠子的方案数的总数。
思路：很容易得出，装饰前i个珠子的方案数为dp[i]=sigma(dp[j]*a[i-j])  (0<=j<i)。很显然是一个卷积，但是dp同时出现在等号前后，需要用CDQ分治加上FFT优化。对于一个区间[l,r]，我们先求出[l,mid]的答案，在求出[l,mid[对[mid+1,r]的影响。对于l端点，如果要影响到r端点，就需要卷积a[i]的长度r-mid+1。用dp[l~id]和a[1~r-mid+1]进行卷积（FFT）后取出对应位置加到dp上即可。
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
#include<cstdio>
#include<cstring>
#include<cmath>
#define MAXN 400000
const double pi = acos(-1.0);
const int mod = 313;
struct Complex
{
double R, I;
Complex(double real = 0.0, double image = 0.0) { R = real, I = image; }
inline Complex operator + (Complex const &b) const { return Complex(R + b.R, I + b.I); }
inline Complex operator - (Complex const &b) const { return Complex(R - b.R, I - b.I); }
inline Complex operator * (Complex const &b) const { return Complex(R*b.R - I*b.I, I*b.R + R*b.I); }
};
inline int turn(int n)
{
int i = 1;
for (; i < n; i <<= 1);
return i;
}
void build(Complex _P[], Complex P[], int n, int m, int curr, int &cnt)
{
if (m == n) _P[curr] = P[cnt++];
else
{
build(_P, P, n, m << 1, curr, cnt);
build(_P, P, n, m << 1, curr + m, cnt);
}
}
void FFT(Complex P[], int n, int op)
{
static Complex _P[MAXN];
int cnt = 0;
build(_P, P, n, 1, 0, cnt);
memcpy(P, _P, sizeof(Complex)*n);
for (int len = 2; len <= n; len <<= 1)
{
int m = len >> 1;
Complex unit = Complex(cos(pi / m*op), sin(pi / m*op));
for (int i = 0; i < n; i += len)
{
Complex W = Complex(1, 0);
for (int j = 0; j < m; j++, W = W*unit)
{
Complex p = P[i + j], q = P[i + j + m];
P[i + j] = p + W*q;
P[i + j + m] = p - W*q;
}
}
}
}
Complex A[MAXN], B[MAXN];
void FFTMUL(int _len)
{
int len = 1;
while (len < _len) len <<= 1;
len <<= 1;
for (int i = _len; i < len; i++) A[i] = Complex(0, 0), B[i] = Complex(0, 0);
if (len < 256)
{
static int tmp[1024];
for (int i = 0; i < len; i++) tmp[i] = 0;
for(int i=0;i<len/2;i++)
for (int j = 0; j < len/2; j++)阿
{
tmp[i + j] += int(A[i].R*B[j].R + 0.5);
tmp[i + j] %= mod;
}
for (int i = 0; i < len; i++) A[i].R = tmp[i];
return;
}
 
FFT(A, len, 1);
FFT(B, len, 1);
for (int i = 0; i < len; i++) A[i] = A[i] * B[i];
FFT(A, len, -1);
for (int i = 0; i < len; i++) A[i].R /= len;
}
long long dp[MAXN];
int a[MAXN];
void merge(int l1, int r1, int l2, int r2)
{
int len = (r1 - l1 + 1) * 2 + 1;
A[0] = Complex(0, 0);
for (int i = 1; i < len; i++) A[i] = Complex(a[i], 0);
B[0] = Complex(0, 0);
for (int i = l1; i <= r1; i++) B[i - l1 + 1] = Complex(dp[i], 0);
for (int i = r1 - l1 + 2; i < len; i++) B[i] = Complex(0, 0);
FFTMUL(len);
for (int i = l2; i <= r2; i++)
{
dp[i] += int(A[r1 - l1 + 2 + i - l2].R + 0.5);
dp[i] %= mod;
}
}
void CDQ(int l, int r)
{
if (l < r)
{
int mid = l + r >> 1;
CDQ(l, mid);
merge(l, mid, mid + 1, r);
CDQ(mid + 1, r);
}
else
{
dp[l] += a[l];
dp[l] %= mod;
}
}
int main()
{
int n;
while (scanf("%d", &n), n)
{
for (int i = 1; i <= n; i++)dp[i] = 0;
for (int i = 1; i <= 2 * n; i++) a[i] = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
a[i] %= mod;
}
CDQ(1, n);
printf("%lld\n", dp[n]);
}
return 0;
}