NOI

[NOI 2012] 魔幻棋盘

给一个N*M的正整数矩阵, 支持子矩阵加, 子矩阵gcd查询. 所有查询均包含某个特定的点(X, Y). (NM ≤ 5*10^5, 操作数T≤10^5, 保证所有时刻矩阵中的数为小于2^62的正整数) 具体输入格式, BZOJ上的描述有误, 参考原题面. 一个关于gcd的结论: . 通常我们从右往左用, 也就是更相减损术.

一维 一个长为N的序列, 支持区间加, 区间gcd查询.

x1 x2 x3 x1 x2-x1 x3-x2

gcd(x1, x2-x1, x3-x2) = gcd(x1, x2, x3-x2) = gcd(x1, x2, x3)

差分, 得到数组D. 维护A和D, A只用支持区间修改和单点查询. D的修改为两个单点修改. 查询[l, r]转化为gcd(A[l], D[l+1..r]).

二维 本题.

将矩阵以(X, Y)为中心二维差分. 也就是说, 寻求矩阵D, 使得A[i][j]为D的某个子矩阵之和. 这样做的正确性在于, 我们可以像上面那样, 反复运用规则和.

具体怎么搞方法比较多......我的搞法每个象限, 每个半轴, 坐标原点各建一棵线段树. 可以把它们通通塞到一棵二维线段树里, 这样, 修改讨论一下, 查询直接上. 这些线段树应该是互不相关的, 边界处差分的时候应把边界外的数视为0.

开始没注意到这一点, 对着数据二分许久才解决问题. 唉, 发现象限的边界有误, 却没想想坐标轴是否也有类似的问题. 还得到了一个教训, 去除数据中的询问这种机械而浩大的文本处理工作还是交给程序来办比较好......官方的数据对这种错误挺强, 然而据说随便改几个点或者只改靠近(X, Y)的几个点是可以AC的......

每个测试点5s, 上面的算法即便每次最多修改21个点, 还是可以AC (然而CodeVS只给4s TAT) 的. 运行速度快一些的方法是, 把轴 "包含" 到象限里, 这样最多改9个点. 以(X,Y)=(1,1)为例. 也就是说, 先前, 现在. 讨论起来等号的处理要注意一下. 其实我不知道大家是怎么讨论清楚的......除了用许多的if, 也可以像上面一样拆到四个象限里, 但包含等号, 然后去重.

先这样吧. 我也不知道这种思路简单讨论繁杂的题目价值大不大. 为啥不规定X=1, Y=1......QAQ

关于二维数组, 虽然说要尽量避免动态内存, 但是为了方便我还是new了一发. 看到一种不错的写法, 弄一个struct, 开一维数组, 重载[]运算符.

{% raw %}
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
 
using namespace std;
typedef long long ll;
 
const int MAX_N = 5e5;
 
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a%b) : a;
}
 
inline ll abs(ll x)
{
    return x > 0 ? x : -x;
}
 
int N, M;
ll** A, ** D;
 
namespace S {
    struct Node {
        Node* lc, * rc;
        ll v;
    } nodes[4*MAX_N], * nil = nodes, * root[4*MAX_N];
 
    int x, y, x1, y1, x2, y2;
    ll ans;
 
    inline void init()
    {
        *nil = (Node){nil, nil, 0};
        fill_n(root+1, 4*N-1, nil);
    }
 
    inline Node* new_node()
    {
        static Node* cur = nodes + 1;
        *cur = *nil;
        return cur++;
    }
     
    void modify_c(Node* &T, int l, int r, Node* L, Node* R)
    {
        if (T == nil)
            T = new_node();
        if (l == r)
            T->v = L == nil ? D[x][y] : gcd(L->v, R->v);
        else {
            int m = (l+r)/2;
            if (y <= m)
                modify_c(T->lc, l, m, L->lc, R->lc);
            else
                modify_c(T->rc, m+1, r, L->rc, R->rc);
            T->v = gcd(T->lc->v, T->rc->v);
        }
    }
 
    void modify_r(int o, int l, int r)
    {
        if (l == r)
            modify_c(root[o], 1, M, nil, nil);
        else {
            int m = (l+r)/2;
            if (x <= m)
                modify_r(o*2, l, m);
            else
                modify_r(o*2+1, m+1, r);
            modify_c(root[o], 1, M, root[o*2], root[o*2+1]);
        }
    }
 
    void query_c(Node* T, int l, int r)
    {
        if (y1 <= l && r <= y2)
            ans = gcd(ans, T->v);
        else {
            int m = (l+r)/2;
            if (y1 <= m)
                query_c(T->lc, l, m);
            if (y2 > m)
                query_c(T->rc, m+1, r);
        }
    }
 
    void query_r(int o, int l, int r)
    {
        if (x1 <= l && r <= x2)
            query_c(root[o], 1, M);
        else {
            int m = (l+r)/2;
            if (x1 <= m)
                query_r(o*2, l, m);
            if (x2 > m)
                query_r(o*2+1, m+1, r);
        }
    }
 
    inline ll query(int x1_, int y1_, int x2_, int y2_)
    {
        ans = 0; x1 = x1_; y1 = y1_; x2 = x2_; y2 = y2_;
        return query_r(1, 1, N), ans;
    }
 
    inline void modify(int x_, int y_, ll a)
    {
        if (x_ < 1 || x_ > N || y_ < 1 || y_ > M)
            return;
        D[x = x_][y = y_] += a;
        modify_r(1, 1, N);
    }
}
 
using S::query;
using S::modify;
 
ll a;
 
inline void m_2D(int x1, int y1, int x2, int y2)
{
    modify(x1, y1, a);
    modify(x1, y2, -a);
    modify(x2, y1, -a);
    modify(x2, y2, a);
}
 
inline void m_1D(int x1, int y1, int x2, int y2)
{
    modify(x1, y1, a);
    modify(x2, y2, -a);
}
 
int main()
{
    int T, X, Y;
    scanf("%d%d%d%d%d", &N, &M, &X, &Y, &T);
     
    S::init();
 
    A = new ll*[N+1];
    For (i, 1, N) {
        A[i] = new ll[M+1];
        For (j, 1, M)
            scanf("%lld", &A[i][j]);
    }
     
    D = new ll*[N+1];
    For (i, 1, N)
        D[i] = new ll[M+1];
 
    int d[4][2] = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
    Rep (k, 0, 4)
        for (int i = X + d[k][0]; i > 0 && i <= N; i += d[k][0])
            for (int j = Y + d[k][1]; j > 0 && j <= M; j += d[k][1]) {
                int x = i-d[k][0], y = j-d[k][1];
                D[i][j] = A[i][j] - (x == X ? 0 : A[x][j])
                    - (y == Y ? 0 : A[i][y]) + (x == X || y == Y ? 0 : A[x][y]);
            }
    D[X][Y] = A[X][Y];
    For (j, Y+1, M)
        D[X][j] = A[X][j] - (j-1 == Y ? 0 : A[X][j-1]);
    Down (j, Y-1, 1)
        D[X][j] = A[X][j] - (j+1 == Y ? 0 : A[X][j+1]);
    For (i, X+1, N)
        D[i][Y] = A[i][Y] - (i-1 == X ? 0 : A[i-1][Y]);
    Down (i, X-1, 1)
        D[i][Y] = A[i][Y] - (i+1 == X ? 0 : A[i+1][Y]);
     
    For (i, 1, N) For (j, 1, M) modify(i, j, 0);
     
    while (T--) {
        int op, x1, y1, x2, y2;
        scanf("%d%d%d%d%d", &op, &x1, &y1, &x2, &y2);
         
        if (op) {
            scanf("%lld", &a);
            if (x2 > X && y2 > Y) // (x1, y1) (x2, y2) (X+1, Y+1)
                m_2D(max(x1, X+1), max(y1, Y+1), x2+1, y2+1);
            if (x2 > X && y1 < Y) // (x1, y2) (x2, y1) (X+1, Y-1)
                m_2D(max(x1, X+1), min(y2, Y-1), x2+1, y1-1);
            if (x1 < X && y1 < Y) // (x2, y2) (x1, y1) (X-1, Y-1)
                m_2D(min(x2, X-1), min(y2, Y-1), x1-1, y1-1);
            if (x1 < X && y2 > Y) // (x2, y1) (x1, y2) (X-1, Y+1)
                m_2D(min(x2, X-1), max(y1, Y+1), x1-1, y2+1);
 
            int t;
            if (X >= x1 && X <= x2) {
                if (y2 > Y) {
                    t = max(y1, Y+1);
                    m_1D(X, t, X, y2+1);
                }
                if (y1 < Y) {
                    t = min(y2, Y-1);
                    m_1D(X, t, X, y1-1);
                }
            }
            if (Y >= y1 && Y <= y2) {
                if (x2 > X) {
                    t = max(x1, X+1);
                    m_1D(t, Y, x2+1, Y);
                }
                if (x1 < X) {
                    t = min(x2, X-1);
                    m_1D(t, Y, x1-1, Y);
                }
            }
 
            if (X >= x1 && X <= x2 && Y >= y1 && Y <= y2)
                modify(X, Y, a);
        } else
            printf("%lld\n", ::abs(query(X-x1, Y-y1, X+x2, Y+y2)));
    }
 
    return 0;
}
{% endraw %}