[20220115杂题选讲]Territories

Posted on | In

一道奇怪的贪心题，难点主要在对子矩阵补集的处理上。

题目大意

在一个 $n\times m$ 的矩阵上放置 $k$ 个带点权的点，每个点有一个不能放置的子矩阵，最后一个位置的权值为其上所有点权值和。设 $(i, j)$ 权值为 ${\rm val}(i, j)$，求 $\max\left{\sum\limits_{i,j}\dfrac{\mathrm {val}^2(i,j)-\mathrm {val}(i,j)}{2}\right}$。

$n,m\le 1000$，$1\le k \le 10^5$。

source: 39th Petrozavodsk Programming Camp, Summer 2020; Day 1: Warsaw U Contest, Friday, August 21, 2020.

link: http://qoj.ac/contest/802/problem/1243

思路

注意到 $f(x)=\dfrac{x^2-x}2$ 显然满足 $f(x)+f(y)<f(x+y)$，故应尽量集中点。

首先枚举点 $P$，将所有点放置于点 $P$。接下来我们发现，对于两个相对的大矩阵顶点 $A,B$，任何点不可能同时不能被放置于 $A,B$。再枚举剩下的点优先放的定点 $P_2$，剩下的点放在 $P_2$ 的对边即可。

具体实现时注意可以维护五个二维前缀和：所有子矩阵的权值前缀和、包含四个角的子矩阵的权值前缀和来避免暴力查询。（不知道为什么，大多数人维护了 $16\sim 17$ 个前缀和）

时间复杂度 $\Theta(nm)$，空间复杂度 $\Theta(nm)$。

代码

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
#include <cstdio>
#include <algorithm>
#include <random>

namespace mirai {

constexpr int MAXN = 100000;

int x1[MAXN], x2[MAXN], y1[MAXN], y2[MAXN], pop[MAXN];
int s[1005][1005], s2[4][1005][1005];
bool chk[MAXN];

int main(int argc, char** argv) {
  std::mt19937 rand2(19260817);
  int cnt, n, m;
  std::scanf("%d%d%d", &cnt, &n, &m);
  long long total = 0;
  for (int i = 1; i <= cnt; ++i) {
    std::scanf("%d%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i], &pop[i]);
    total += pop[i];
    s[x2[i]][y2[i]] += pop[i];
    s[x2[i]][y1[i] - 1] -= pop[i];
    s[x1[i] - 1][y2[i]] -= pop[i];
    s[x1[i] - 1][y1[i] - 1] += pop[i];
    auto update = [&](int k) {
      s2[k][x2[i]][y2[i]] += pop[i];
      s2[k][x2[i]][y1[i] - 1] -= pop[i];
      s2[k][x1[i] - 1][y2[i]] -= pop[i];
      s2[k][x1[i] - 1][y1[i] - 1] += pop[i];
    };
    if (x1[i] == 1 && y1[i] == 1) {
      update(0);
    }
    if (x2[i] == n && y1[i] == 1) {
      update(1);
    }
    if (x1[i] == 1 && y2[i] == m) {
      update(2);
    }
    if (x2[i] == n && y2[i] == m) {
      update(3);
    }
  }
  for (int i = n; i >= 1; --i) {
    for (int j = m; j >= 1; --j) {
      s[i][j] += s[i + 1][j] + s[i][j + 1] - s[i + 1][j + 1];
      for (int k = 0; k < 4; ++k) {
        s2[k][i][j] += s2[k][i + 1][j] + s2[k][i][j + 1] - s2[k][i + 1][j + 1];
      }
    }
  }
  long long ans = -1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      long long a1 = total - s[i][j];
      auto count = [&](int k) -> long long {
        long long a2 = s2[k][i][j];
        long long a3 = total - a1 - a2;
        return a2 * (a2 - 1) / 2 + a3 * (a3 - 1) / 2;
      };
      ans = std::max(ans, a1 * (a1 - 1) / 2 + std::max({count(0), count(1), count(2), count(3)}));
    }
  }
  std::printf("%lld\n", ans);
  return 0;
}

}

int main(int argc, char** argv) {
  return mirai::main(argc, argv);
}