BZOJ 2877 - [Noi2012]魔幻棋盘

#数据结构 #线段树 #二维线段树

Published on 2016-07-09

题目地址

描述

对 $n \times m(n \times m \le 500000)$ 的棋盘完成 $T(T\le 100000)$ 次操作，操作有 2 种：

查询一个矩阵区域的最大公约数。
修改一个矩阵区域的值，将其值统一增加 $c$ 。

保证每个查询操作包含一个特定的点 $(X, Y)$ 。

分析

首先声明，我的做法不需分为 9 种情形讨论，感觉做多余的讨论，是没有理解算法的实质！

首先看 $n = 1$ 的情形，即只有一维。
算法一：由于最大公约数具有可合并的性质，即集合 $A$ 的最大公约数为 $a$ ，集合 $B$ 的最大公约数为 $b$ ，那么集合 $A\cup B$ 的最大公约数为 $\gcd(a, b)$ ，所以我们用线段树维护这个数列。
对于查询操作，可用在线段树上查询，在 $O(\log n)$ 的时间内得出答案。
问题在于修改，一段区间加上一个数，它们的最大公约数完全改变了，与之前的值没有任何的关系，这使得我们必须暴力修改每个位置的值，这样一次修改可能到达 $O(n)$ ，无法承受！

在介绍算法二之前，我们先介绍一个引理，这个引理是由辗转相除法 $\gcd(a, b) = \gcd(b, a \bmod b)$ 扩展得到的：

\gcd(a_1, a_2, \cdots, a_n) = \gcd(a_i, a_2 - a_1, a_3 - a_2, \cdots, a_n - a_{n - 1})(1\le i \le n)

算法二：变换数列，将 $n$ 项的 $A$ 数列，变为 $n - 1$ 项的差分数列 $B$ ， $B_i = A_{i + 1} - A_{i}$ 。则我们不再维护 $A$ 序列，将询问和修改都变到 $B$ 序列上面。
对数列 $A$ 的 $[l, r]$ 区间进行修改，等价于修改 $B_{i - 1}$ 与 $B_{j}$ 两个元素。
对数列 $A$ 的 $[l, r]$ 区间进行查询，等价于查询 $B$ 数列的 $[l, r)$ 与 $B_{Y}$ 的最大公约数（ $B_Y$ 是那个固定的点）。

则成功将区间修改降到了 $O(\log n)$ 级别，可以拿到一维的全部 40 分。
如果将 $n\times m$ 的棋盘用 $n$ 个一维线段树维护的话，总复杂度为 $O(nm + nT(\log m + \log v))$ ，仍然无法承受。

我们要明白，降低修改复杂度的实质是减少每次修改影响的点，一阶差分让每次影响的点只有两个，我们能不能使用二阶差分，来让每次修改也只影响常数个点呢？
介绍算法三之前，我们先看看二维和一维有什么联系：

如上矩阵，其中 $a_{X, Y} = a_{3, 2}$ 用红字突出，是我们每次查询都会包含的点。我们考虑用差分的方式，求出整个矩阵的最大公约数，一行一行的来看。
设 $g_i$ 为第 $i$ 行的最大公约数，对于第一行，其最大公约数：

g_1 = \gcd(a_{1, i}, a_{1, 2} - a_{1, 1}, a_{1, 3} - a_{1, 2}, a_{1, 4} - a_{1, 3})

其中 $a_{1, i}$ 是可以随便选的，我们选 $i = Y$ 即 $a_{1, 2}$ ，扩展到每一行，可以得到：

g_i = \gcd(a_{i, Y}, a_{i, 2} - a_{i, 1}, a_{i, 3} - a_{i, 2}, a_{i, 4} - a_{i, 3})

所以全矩阵的 $\gcd$ 为：

G = \gcd(g_1, g_2, g_3, g_4)

我们提出每个 $g_i$ 里面的 $a_{i, Y}$ ，则：

G = \gcd(a_{1, Y}, a_{2, Y}, a_{3, Y}, a_{4, Y}, G_B)

其中 $G_B$ 新的矩阵 $B$ 的最大公约数，矩阵 $B$ 为：

\begin{matrix} a_{1, 2} - a_{1, 1} & a_{1, 3} - a_{1, 2}&a_{1, 4}-a_{1, 3}\\ a_{2, 2} - a_{2, 1} & a_{2, 3} - a_{2, 2}&a_{2, 4}-a_{2, 3}\\ a_{3, 2} - a_{3, 1} & a_{3, 3} - a_{3, 2}&a_{3, 4}-a_{3, 3}\\ a_{4, 2} - a_{4, 1} & a_{4, 3} - a_{4, 2}&a_{4, 4}-a_{4, 3}\end{matrix}

问题转化为求矩阵 $B$ 的最大公约数，支持子矩阵修改操作，对于矩阵 $B$ 每次还是可能最多影响 $O(n)$ 个点。

相信你已经猜出来了，我们要竖着差分一次！构造一个新的矩阵 $C_{(n - 1)\times (m - 1)}$ ，其中 $C_{i, j} = A_{i + 1, j + 1} - A_{i + 1, j} - A_{i, j + 1} + A_{i, j}$ ，所以 $G_B$ 转化为：

G_B = \gcd(G_C, a_{X, 2} - a_{X, 1}, a_{X, 3} - a_{X, 2}, a_{X, 4}-a_{X, 3})

合并一下，得到：

G = \gcd(a_{1, Y}, a_{2, Y}, a_{3, Y}, a_{4, Y}, a_{X, 2} - a_{X, 1}, a_{X, 3} - a_{X, 2}, a_{X, 4}-a_{X, 3}, G_C)

再用一次算法二之前的等式：

G = \gcd(a_{X, Y}, a_{2, Y} - a_{1, Y}, a_{3, Y} - a_{2, Y}, a_{4, Y} - a_{3, Y} , a_{X, 2} - a_{X, 1}, a_{X, 3} - a_{X, 2}, a_{X, 4}-a_{X, 3}, G_C)

算法三：用两次算法二维护 $G$ 前面的项，对于 $G_C$ ，我们采用二维线段树维护。
这样询问变为两次一维线段树的询问，一次二维线段树的询问。
对于修改，最坏在一维线段树上修改 2 个点，二维线段树上修改 4 个点，仍然是常数个。
总复杂度： $O(nm + T(\log n(\log m + \log V)))$ 。

细节自行脑补。

总结：对于一个算法的优化，我们必须弄清楚实际优化的是什么（本题中是修改的点数），从而才能简单对更高维度更复杂的情况进行扩展。

代码

//  Created by Sengxian on 7/8/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2877 NOI 2012 D1T3 二维差分 + 二维线段树
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline ll ReadLL() {
    static ll n;
    static int ch;
    static bool flag;
    n = 0, ch = getchar(), flag = false;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return flag ? -n : n;
}

const int maxn = 500000 + 3, maxm = 500000 + 3;
const int maxNode = (1 << 19) * 2;

ll gcd(ll a, ll b) {
    return b == 0 ? abs(a) : gcd(b, a % b);
}

#define ls (((o) << 1) + 1)
#define rs (((o) << 1) + 2)
#define mid (((l) + (r)) >> 1)
ll *a[maxm], *b[maxm], c[maxm], d[maxn], val;
struct segment_tree1D {
    ll *g;
    inline void build(int o, int l, int r, const ll *ltree, const ll *rtree) {
        if (l >= r) return g[o] = 0, void();
        if (r - l == 1) g[o] = rtree ? gcd(ltree[o], rtree[o]) : ltree[l];
        else {
            build(ls, l, mid, ltree, rtree), build(rs, mid, r, ltree, rtree);
            g[o] = gcd(g[ls], g[rs]);
        }
    }
    inline ll query(int o, int l, int r, int a, int b) {
        if (r <= a || l >= b) return 0;
        if (l >= a && r <= b) return g[o];
        else {
            ll gg = 0;
            if (mid > a) gg = query(ls, l, mid, a, b);
            if (mid < b) gg = gcd(gg, query(rs, mid, r, a, b));
            return gg;
        }
    }
    inline void modify(int o, int l, int r, int pos, ll v) {
        if (pos < l || pos >= r) return;
        if (r - l == 1) return g[o] += v, void();
        else if (pos < mid) modify(ls, l, mid, pos, v);
        else modify(rs, mid, r, pos, v);
        g[o] = gcd(g[ls], g[rs]);
    }
    inline void modify(int o, int l, int r, int pos, const ll *ltree, const ll *rtree) {
        if (pos < l || pos >= r) return;
        if (r - l == 1) return g[o] = gcd(ltree[o], rtree[o]), void();
        else if (pos < mid) modify(ls, l, mid, pos, ltree, rtree);
        else modify(rs, mid, r, pos, ltree, rtree);
        g[o] = gcd(g[ls], g[rs]);
    }
    segment_tree1D(int m) {
        g = new ll[(1 << (int)(ceil(log2(m)))) * 2];
    }
};


int n, m, xx, yy, t;
namespace segment_tree2D {
    struct seg_node2D {
        segment_tree1D *tree;
        seg_node2D(): tree(NULL) {}
    }segs[maxNode];
    void build2D(int o, int l, int r) {
        if (l >= r) return;
        segs[o].tree = new segment_tree1D(m);
        if (r - l == 1) segs[o].tree->build(0, 0, m, ::b[l], NULL);
        else {
            build2D(ls, l, mid), build2D(rs, mid, r);
            segs[o].tree->build(0, 0, m, segs[ls].tree->g, segs[rs].tree->g);
        }
    }
    int a, c, b, d;
    ll v;
    ll query2D(int o, int l, int r) {
        if (r <= a || l >= b) return 0;
        if (l >= a && r <= b) return segs[o].tree->query(0, 0, m, c, d);
        else {
            ll gg = 0;
            if (mid > a) gg = query2D(ls, l, mid);
            if (mid < b) gg = gcd(gg, query2D(rs, mid, r));
            return gg;
        }
    }
    void modify2D(int o, int l, int r) {
        if (r - l == 1) segs[o].tree->modify(0, 0, m, b, v);
        else {
            if (a < mid) modify2D(ls, l, mid);
            else modify2D(rs, mid, r);
            segs[o].tree->modify(0, 0, m, b, segs[ls].tree->g, segs[rs].tree->g);
        }
    }
}


ll query(int x1, int y1, int x2, int y2) {
    segment_tree2D::a = x1, segment_tree2D::b = x2;
    segment_tree2D::c = y1, segment_tree2D::d = y2;
    return segment_tree2D::query2D(0, 0, n);
}

void modify(int x, int y, ll v) {
    segment_tree2D::a = x, segment_tree2D::b = y;
    segment_tree2D::v = v;
    if (x >= 0 && y >= 0 && x < n && y < m) segment_tree2D::modify2D(0, 0, n);
}

int main() {
    n = ReadLL(), m = ReadLL(), xx = ReadLL() - 1, yy = ReadLL() - 1, t = ReadLL();
    for (int i = 0; i < n; ++i) {
        a[i] = new ll[m + 3], b[i] = new ll[m + 3];
        for (int j = 0; j < m; ++j) a[i][j] = ReadLL(); 
    }
    for (int i = 0; i < n - 1; ++i)
        for (int j = 0; j < m - 1; ++j)
            b[i][j] = a[i + 1][j + 1] - a[i][j + 1] - a[i + 1][j] + a[i][j];
    for (int i = 0; i < m - 1; ++i) c[i] = a[xx][i + 1] - a[xx][i];
    for (int i = 0; i < n - 1; ++i) d[i] = a[i + 1][yy] - a[i][yy];
    val = a[xx][yy];
    segment_tree2D::build2D(0, 0, n);
    segment_tree1D C(m), D(n);
    C.build(0, 0, m, c, NULL), D.build(0, 0, n, d, NULL);

    while (t--) {
        static int type, x1, y1, x2, y2;
        static ll v, gg;
        type = ReadLL();
        if (type == 0) {
            x1 = xx - ReadLL(), y1 = yy - ReadLL(), x2 = xx + ReadLL() + 1, y2 = yy + ReadLL() + 1;
            gg = val;
            gg = gcd(gg, query(x1, y1, x2 - 1, y2 - 1));
            gg = gcd(gg, C.query(0, 0, m, y1, y2 - 1));
            gg = gcd(gg, D.query(0, 0, n, x1, x2 - 1));
            printf("%lld\n", abs(gg));
        } else if (type == 1) {
            x1 = ReadLL() - 1, y1 = ReadLL() - 1, x2 = ReadLL(), y2 = ReadLL(), v = ReadLL();
            if (xx >= x1 && xx < x2 && yy >= y1 && yy < y2) val += v;
            if (xx >= x1 && xx < x2) C.modify(0, 0, m, y1 - 1, v), C.modify(0, 0, m, y2 - 1, -v);
            if (yy >= y1 && yy < y2) D.modify(0, 0, n, x1 - 1, v), D.modify(0, 0, n, x2 - 1, -v);
            modify(x1 - 1, y1 - 1, v), modify(x2 - 1, y1 - 1, -v), modify(x1 - 1, y2 - 1, -v), modify(x2 - 1, y2 - 1, v);
        } else assert(false);
    }
    return 0;
}

HDOJ 5779 - Tower Defence BZOJ 3238 - [Ahoi2013]差异

Sengxian's Blog

BZOJ 2877 - [Noi2012]魔幻棋盘

描述

分析

代码