BZOJ2702 金融风暴 决策单调性

发表于 更新于 分类于 阅读次数：

金融风暴 先orz Claris 好像是很经典的做法。考虑一行左边两个点的答案更新右边的某个点。不难发现是有决策单调性的。右边更新左边同理。那么把每个点的初始距离设置为上方/下方最近的点，并对每一行分分治即可。至于查询用二维ST表就可以。

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
#include <bits/stdc++.h>

inline int rd() {
  int a = 1, b = 0; char c = getchar();
  while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return a ? b : -b;
}

const int N = 1005;

int w, h, n, q, map[N][N], st[11][N][N];
int up[N], f[N], lg[N];

inline void solve(int l, int r, int ql, int qr) {
  int mid = (l + r) >> 1, pos = 0;
  for (int i = ql; i <= qr; ++i) if (~up[i]) {
    int tmp = (mid - i) * (mid - i) + up[i] * up[i];
    if (f[mid] > tmp) {
      f[mid] = tmp;
      pos = i;
    }
  }
  if (pos && l != mid)
    solve(l, mid - 1, ql, pos);
  if (pos && r != mid)
    solve(mid + 1, r, pos, qr);
}

inline int query(int x, int y, int d) {
  int t = lg[d];
  return std::max({
    st[t][x][y], st[t][x + d - (1 << t)][y + d - (1 << t)],
    st[t][x + d - (1 << t)][y], st[t][x][y + d - (1 << t)]
  });
}

int main() {
  for (int i = 2; i < N; ++i)
    lg[i] = lg[i >> 1] + 1;
  w = rd() + 1, h = rd() + 1, n = rd();
  for (int i = 1; i <= n; ++i) {
    int x = rd() + 1, y = rd() + 1;
    map[x][y] = 1;
  }
  memset(up, -1, sizeof(up));
  for (int i = 1; i <= w; ++i) {
    memset(f, 0x3f, sizeof(f));
    for (int j = 1; j <= h; ++j) {
      if (map[i][j]) up[j] = 0;
      else if (~up[j]) ++up[j];
    }
    solve(1, h, 1, h);
    for (int j = 1; j <= h; ++j)
      st[0][i][j] = f[j];
  }
  memset(up, -1, sizeof(up));
  for (int i = w; i >= 1; --i) {
    memset(f, 0x3f, sizeof(f));
    for (int j = 1; j <= h; ++j) {
      if (map[i][j]) up[j] = 0;
      else if (~up[j]) ++up[j];
    }
    solve(1, h, 1, h);
    for (int j = 1; j <= h; ++j)
      st[0][i][j] = std::min(st[0][i][j], f[j]);
  }
  for (int k = 1; k <= 10; ++k)
    for (int i = 1; i + (1 << k) - 1 <= w; ++i)
      for (int j = 1; j + (1 << k) - 1 <= h; ++j)
        st[k][i][j] = std::max({
          st[k - 1][i][j], st[k - 1][i][j + (1 << (k - 1))],
          st[k - 1][i + (1 << (k - 1))][j],
          st[k - 1][i + (1 << (k - 1))][j + (1 << (k - 1))]
        });
  q = rd();
  while (q--) {
    int x = rd() + 1, y = rd() + 1, d = rd();
    if (x - d < 1  x + d > w  y - d < 1  y + d > h) {
      puts("-1"); continue;
    }
    int ans = query(x - d, y - d, d * 2 + 1);
    printf("%.3lf\n", std::sqrt(ans));
  }
  return 0;
}