盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 5021 Revenge of kNN II(二分+树状数组)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5021

题意

给定n个点,每个点有一个值。现在有一些询问,每次用离某点距离最小的K个点的平均值来更新该点的值,如果有两个点距离相同,去index小的点。

思路

  1. 可以用二分来求每次离该点最近的K个点,二分离该点的距离值即可。注意一些细节问题
  2. 用树状数组来维护距离和

代码

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
int n, q;
int x[N], v[N], rk[N], p[N];
pair<int, int> d[N];
double c[N], b[N];
int main () {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d%d", x + i, v + i);
d[i] = make_pair(x[i], i);
c[i] = 0;
}
sort(d + 1, d + n + 1);
for (int i = 1; i <= n; i++) {
rk[d[i].second] = i;
b[i] = v[d[i].second];
p[i] = d[i].first;
for (int j = i; j <= n; j += j & -j) c[j] += b[i];
}
double ans = 0;
while(q--) {
int i, k, dis;
scanf("%d%d", &i, &k);
dis = x[i];
i = rk[i];
int l = 1, r = 1e9, mid;
while(l < r) {
mid = (l + r) >> 1;
int sum = upper_bound(p + 1, p + n + 1, dis + mid) - lower_bound(p + 1, p + n + 1, dis - mid);
if (sum >= k + 1) r = mid;
else l = mid + 1;
}
int L = lower_bound(p + 1, p + n + 1, dis - r) - p;
int R = upper_bound(p + 1, p + n + 1, dis + r) - p - 1;
if (L + k != R) {
if (d[L].second < d[R].second) --R;
else ++L;
}
double sum = 0;
for (int j = R; j > 0; j -= j & -j) sum += c[j];
for (int j = L - 1; j > 0; j -= j & -j) sum -= c[j];
sum -= b[i];
sum /= k;
ans += sum;
for (int j = i; j <= n; j += j & -j) c[j] += sum - b[i];
b[i] = sum;
}
printf("%.3lf\n", ans);
}
return 0;
}