自动搬运

查看原文

来自洛谷，原作者为

	registerGen 一切都是野蛮的。要反对这种野蛮，我们必须也学会野蛮。

搬运于2025-08-24 22:51:06，当前版本为作者最后更新于2023-08-15 09:22:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里是官方题解。

春测 2023 T1 加强版。

算法一

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

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

算法二

考虑当 $t=1$ 时怎么做。

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

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

1. $ans_c\gets ans_c+(r-l+1-\sum_{i=l}^rR_i)(m-\sum_{i=1}^mC_i)$；
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;
}