P4024 题解

· · 题解

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;
}