春测 2023 T1 加强版 题解

· · 题解

这里是官方题解。

春测 2023 T1 加强版。

算法一

对于一次染色操作，暴力地将相应区域染上相应颜色，最后用桶统计答案。

时间复杂度 \mathcal O(nmq)。

算法二

考虑当 t=1 时怎么做。

将所有操作倒过来考虑。这样一来一个区域只要被染色了，它的颜色就再也不会变了，我们就再也不用管它了。

于是我们只需维护每一行是否全部被染色（记为 R_i）和每一列是否全部被染色（记为 C_i）。每次操作（以 op=1 为例）我们考虑计算新增的被染色的格子数量，要干的事情如下：

  2. 对于所有 l\le i\le r，R_i\gets 1。

我们要进行的操作有：区间求和、区间赋值。这显然可以通过线段树维护。

时间复杂度 \mathcal O(q\log\max\{n,m\})。

p.s. 线段树有 90 分是因为放不了很多那么大的数据，而且基础赛不让把输入格式搞那么复杂（也就是说不让在程序内生成数据

算法三

考虑优化算法二。

我们维护单向链表 nxtR,nxtC，nxtR_i 表示当前的 R 中在 R_i 右边的第一个为 0 的位置，nxtC_i 的定义类似。每次查询我们直接暴力跳 nxt 并统计答案，修改时边跳 nxt 边把当前的 nxt 更新为 nxt_r（如果没有理解这句话，你可以参考 std 中的 Solver::modify 函数和 Solver::query 函数）。

注意到我们查询完一个区间后就要对这个区间做修改，故 R,C 的每个位置最多被访问一次。于是时间复杂度就被均摊成线性了。

时间复杂度 \mathcal O(n+m+q)。

算法四

事实上我们只需要安排一个操作顺序，使得后面的操作不“影响”前面的操作。我们可以先从后往前进行完所有 t=1 的操作，再从前往后进行完所有 t=0 的操作。

时间复杂度 \mathcal O(n+m+q)。

std

#include <algorithm>
#include <cstdio>
using namespace std;

typedef long long ll;

const int N = 2e6;

struct Query { int opt, l, r, c, t; };

int n, m, k, q;
Query qry[N + 10];
ll ans[N + 10];

struct Solver {
  int sum, a[N + 10], nxt[N + 10];

  inline void modify(int ql, int qr) {
    int lst = 0;
    for (int i = ql; i <= qr; i = nxt[i]) {
      if (a[i] == 0) sum++;
      a[i] = 1;
      if (lst) nxt[lst] = nxt[qr];
      lst = i;
    }
  }

  inline int query(int ql, int qr) {
    int res = 0;
    for (int i = ql; i <= qr; i = nxt[i]) {
      res += !a[i];
    }
    return qr - ql + 1 - res;
  }
} tr, tc;

void modify(int id) {
  int opt = qry[id].opt, l = qry[id].l, r = qry[id].r, c = qry[id].c;
  if (opt == 1) {
    int cntr = tr.query(l, r), cntc = tc.sum;
    ans[c] += 1LL * (r - l + 1 - cntr) * (m - cntc);
    tr.modify(l, r);
  } else {
    int cntr = tr.sum, cntc = tc.query(l, r);
    ans[c] += 1LL * (n - cntr) * (r - l + 1 - cntc);
    tc.modify(l, r);
  }
}

int main() {
  scanf("%d%d%d%d", &n, &m, &k, &q);
  for (int i = 1; i <= q; i++)
    scanf("%d%d%d%d%d", &qry[i].opt, &qry[i].l, &qry[i].r, &qry[i].c, &qry[i].t);
  for (int i = 1; i <= n; i++) tr.nxt[i] = i + 1;
  for (int i = 1; i <= m; i++) tc.nxt[i] = i + 1;
  for (int i = q; i >= 1; i--)
    if (qry[i].t) modify(i);
  for (int i = 1; i <= q; i++)
    if (!qry[i].t) modify(i);
  for (int i = 1; i <= k; i++)
    printf("%lld%c", ans[i], " \n"[i == k]);
  return 0;
}