自动搬运

查看原文

来自洛谷，原作者为

	yzy1 Меня мое сердце, в тревожную даль зовёт.

搬运于2025-08-24 21:55:40，当前版本为作者最后更新于2022-04-26 07:56:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

DS + 提交答案，还真有人出过这种题啊。

题目大意

给出一个带权二维矩阵 $a$。每次询问一个子矩阵中形如 $(x_1,y_1),(x,_2,y_2)$ 且 $x_1 \le x_2$，$y_1\le y_2$，$a_{x_1,y_1} > a_{x_2,y_2}$ 的点对个数。

算法 $\bf 1$

设 $n \ge m$。对于 $n<m$ 的情况直接将矩阵转置一下，然后 $\operatorname{swap}(n,m)$ 即可。

首先有个显然的暴力：离散化后，莫队扫 $n$ 这一维。开 $O(m^2)$ 个权值树状数组，分别维护当前莫队区间的每一列。开个 $O(m^2)$ 的二维数组 $ans$ 记录答案，$ans(i,j)$ 代表当前莫队区间第 $i$ 列和第 $j$ 列之间对答案的贡献。

时间复杂度为 $O(\dfrac {n}{\sqrt{q}} m^2 \log(nm) + qm^2)$。

我们发现这个算法能在每个点 $120\text{ s}$ 内跑过除了 $6,7$ 外其它所有点。

算法 $\bf 2$

观察测试点 $6$ 的特殊性质。发现这个测试点满足每个格子中的整数都比它上面和左边的格子中的小。换句话说，所有满足 $x_1 \le x_2$，$y_1\le y_2$，$(x_1,y_1)\ne(x_2,y_2)$ 的点对均会对答案产生贡献。

设每次询问的子矩形宽 $x$，高 $y$。则答案为：

$$\sum_{i=1}^x\sum_{j=1}^y ij-1 = \frac{x y (x y + x + y - 3)}{4} $$

算法 $\bf 3$

观察测试点 $7$ 的特殊性质。发现这个测试点矩阵权值只有两种，且为棋盘形分布。

和算法 $\bf 2$ 类似，统计奇数行对奇数行、奇数行对偶数行、偶数行对奇数行、偶数行对偶数行的贡献相加即可。可以每次询问 $O(1)$ 计算答案。

代码参考

算法 $\bf 1$，已除去过长的缺省源。

const int N = 1e6 + 9;
const int M = 6;
const int sz = 200;

int n, m, q, a[M][N];
ll res[M][M], Ans[N];

struct Bit {
  int a[N];
  inline void Add(int p, int x) {
    while (p < N) a[p] += x, p += lb(p);
  }
  inline int Ask(int p) {
    int res = 0;
    while (p) res += a[p], p -= lb(p);
    return res;
  }
} bit[M];

struct Query {
  int l, r, L, R, id;
  inline bool operator<(const Query &x) const {
    return l / sz == x.l / sz ? (r == x.r ? 0 : ((l / sz) & 1) ^ (r < x.r)) : l < x.l;
  }
} Q[N];

inline void AddL(int x) {
  re (i, m)
    bit[i].Add(a[i][x], 1);
  re (i, m) {
    rep (j, i, m)
      res[i][j] += bit[j].Ask(a[i][x] - 1);
  }
}

inline void AddR(int x) {
  re (i, m)
    bit[i].Add(a[i][x], 1);
  re (i, m) {
    rep (j, 1, i)
      res[j][i] += bit[j].Ask(N - 1) - bit[j].Ask(a[i][x]);
  }
}

inline void DelL(int x) {
  re (i, m) {
    rep (j, i, m)
      res[i][j] -= bit[j].Ask(a[i][x] - 1);
  }
  re (i, m)
    bit[i].Add(a[i][x], -1);
}

inline void DelR(int x) {
  re (i, m) {
    rep (j, 1, i)
      res[j][i] -= bit[j].Ask(N - 1) - bit[j].Ask(a[i][x]);
  }
  re (i, m)
    bit[i].Add(a[i][x], -1);
}

signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> m >> n >> q;
  vector<int> vec;
  if (m < n) {
    re (i, m)
      re (j, n)
        cin >> a[i][j], vec.push_back(a[i][j]);
    re (i, q)
      cin >> Q[i].L >> Q[i].l >> Q[i].R >> Q[i].r, Q[i].id = i;
  } else {
    re (i, m)
      re (j, n)
        cin >> a[j][i], vec.push_back(a[j][i]);
    re (i, q)
      cin >> Q[i].l >> Q[i].L >> Q[i].r >> Q[i].R, Q[i].id = i;
    swap(n, m);
  }
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  re (i, m)
    re (j, n)
      a[i][j] = lower_bound(vec.begin(), vec.end(), a[i][j]) - vec.begin() + 1;
  sort(Q + 1, Q + q + 1);
  int l = 1, r = 0;
  re (i, q) {
    if (i % 10000 == 0) dbg(i);
    while (l > Q[i].l) AddL(--l);
    while (r < Q[i].r) AddR(++r);
    while (l < Q[i].l) DelL(l++);
    while (r > Q[i].r) DelR(r--);
    rep (j, Q[i].L, Q[i].R)
      rep (k, j, Q[i].R)
        Ans[Q[i].id] += res[j][k];
  }
  re (i, q)
    cout << Ans[i] << '\n';
  return 0;
}