IOI2013 Game 二维数点强制在线模板问题

本题在acwing上没有，评测网址请点击”原题链接”按钮进行查看，acwing在标题上限制有点多…

时间限制: 13s 空间限制: 230MB

题目描述

Bazza 和 Shazza 正在玩游戏。游戏在一个 R 行 C 列的网格上进行。其中， R 行
编号为 0, …, R - 1 , C 列编号为 0, …, C - 1 。我们用 (P, Q) 表示位于 P 行 Q 列的单
元格。每个单元格包含一个非负整数，游戏开始时所有单元格内的整数均为零。

游戏如下进行：任意时刻，Bazza 可以做如下动作之一：

• 修改一个单元格 (p, q) 内包含的整数值；
• 要求 Shazza 计算一个给定子矩阵中所有单元格内数字的最大公约数 （$\gcd$），子矩阵的两个对角分别为 (p, q) 和 (u, v) （子矩阵包含给定的两 个对角点）。 Bazza会做 $N_u + N_q$ 次动作(其中，修改单元格内数据 $N_u$ 次，询问GCD $N_q$ 次) 。 你的任务是对 Bazza 提出的问题给出正确答案。

题目要求

本题为一个交互题（需要在你的程序中包含"game.h"头文件），所有操作均为强制在线，你需要实现以下函数。

init()

void init(int R, int C);

其中 R 表示行数，C 表示列数，该函数允许你初始化任何的全局变量和数据结构，保证在最开始调用。在另外两个函数调用之前，只会调用 $1$ 次。

update()

void update(int P, int Q, long long K);

• P: 单元格的行号( $0 ≤ P ≤ R - 1$ )。
• Q: 单元格的列号( $0 ≤ Q ≤ C - 1$ )。
• K: 这个单元格中新的整数( $0 ≤ K ≤ 10^{18}$ )。这个新整数可能与原来的整数相同。

当Bazza改变单元格中的整数时调用此函数，将 (P,Q) 坐标的值改为 K 。

calculate()

long long calculate(int P, int Q, int U, int V);

• P: 子矩阵左上角单元格的行号( $0 ≤ P ≤ R - 1$ )。
• Q: 子矩阵左上角单元格的列号 ( $0 ≤ Q ≤ C - 1$ )。
• U: 子矩阵右下角单元格的行号( $P ≤ U ≤ R - 1$ )。
• V: 子矩阵右下角单元格的列号( $Q ≤ V ≤ C - 1$ )。
• Returns: 子矩阵中所有整数的 $\gcd$ 或者$0$（如果所有的整数都是$0$）。

该函数计算以 (P, Q) 和 (U, V) 为对角点的子矩阵中所有整数的最大公约数。这个范 围是包含单元格 (P, Q) 和 (U, V) 的。 如果这个子矩阵中的所有整数都是 $0$，那么该函数返回 $0$。

本地调试

在本地调试当中，你电脑上的样例评分程序从文件game.in中读入。

该文件格式如下：

第1行: R C N

接下来的 N 行: 每行表示一个动作，以动作发生的先后顺序给出。

表示每个动作的一行的格式如下：

• update(P,Q,K) 表示为： 1 P Q K
• calculate(P,Q,U,V) 表示为： 2 P Q U V，每一次输出一行，表示查询结果。

样例

输入

2 3 9
1 0 0 20 
1 0 2 15 
1 1 1 12 
2 0 0 0 2
2 0 0 1 1
1 0 1 6
1 1 1 14
2 0 0 0 2
2 0 0 1 1

输出

5
4
1
2

数据范围

$1\le R, C\le 10^9, N_u \le 22000, N_q \le 250000$。

思路解析

终于用强制在线的方式解决了这个困扰了我很久的问题了！

二维数点问题算是较为经典的题目了，在不少其他背景的题目中也有转化为二维数点的题。

但是比较遗憾的是，国内现有的二维数点模板题目当中，主要推行以下几种我不是很喜欢的做法。

• 极快的cdq分治离线做法。（需要脑子好，对离散的时间轴和操作想的很清楚，可惜我没脑子QAQ）
• 对空间卡的非常死的kd-Tree查询做法。然而kd-Tree的单次查询时间终究是 $O(\sqrt n)$ 的，在更高维度的查询当中才有更大的优势（毕竟总不能写个树套树套树吧）。
• 2维动态树状数组或Wavelet Matrix。然而这两种做法也是需要先对所有坐标进行离散化再开始查询的。

并没有一个很好的，提供动态开空间的树套树的练习题目。但是本题通过交互题的形式出现，就意味着所有的操作必须强制在线完成，这个就非常的对我的胃口了。

不难发现，在2D查询当中，我们需要采用的做法是树套树，而且还是动态开空间的那种（这个时候练练指针写法就再好不过啦~）

顾名思义，树套树即平衡树套平衡树，在2D查询当中，采用Treap套线段树做法的较多（本题涉及到的 $\gcd$ 运算就更适合用线段树来完成而不是树状数组）。不过我们也可以在插入的时候通过分别计算内外两层树中，不同坐标范围对应节点的最近公共祖先(LCA)来强制保证每一个二叉搜索树为二叉平衡搜索树。

更新和查询区间信息的时候和线段树等二叉平衡搜索树完全一样，只需要收集子节点信息，再汇总一下即可。

此处需要注意的是，该做法的修改操作只能为单点赋值操作，如果我们需要做的是单点加法操作(参见BZOJ4066 简单题)，如果直接修改内层树的update函数，则会出现错误。那么此时我们改成先查询该点的值，再将该点修改为原有值+要加的值即可。（如果提交到对应的题目的话，肯定是无法AC的，因为空间被卡死了，能拿到20分或40分就说明该做法的正确性是无误的）。

该做法甚至漂亮到任何的STL或其他头文件都不需要采用，如果不是交互题的话，用个stdio.h完成输入输出就完事了。

实现代码

// Max Execution time : 2087ms Max Memory : 38440KB
// interaction header
#include "game.h"
typedef long long ll;
struct ii
{
    int first, second;
    ii(int _a = 0, int _b = 0) : first(_a), second(_b) {}
};

inline ll gcd(ll x, ll y)
{
    if (!x)
        return y;
    if (!y)
        return x;
    if (x < 0)
        x = -x;
    if (y < 0)
        y = -y;
    ll t = __builtin_ctzll(x | y);
    x >>= __builtin_ctzll(x);
    do
    {
        y >>= __builtin_ctzll(y);
        if (x > y)
        {
            ll tmp = x;
            x = y;
            y = tmp;
        }
        y -= x;
    } while (y);
    return x << t;
}

inline ll func(ll X, ll Y) { return gcd(X, Y); }

// 2D Dynamic Query Tree from errorgorn

// find lca of 2 nodes
ii lca(int l, int r, int pos)
{
    if (pos < l)
    {
        int p = 32 - __builtin_clz(pos ^ l);
        int lp = (pos >> p) << p;
        return ii(lp, lp + (1 << p) - 1);
    }
    if (r < pos)
    {
        int p = 32 - __builtin_clz(r ^ pos);
        int lp = (l >> p) << p;
        return ii(lp, lp + (1 << p) - 1);
    }
    return ii(pos, 0);
}

struct node
{
    int s, e, m;
    ll val = 0;
    node *l = nullptr, *r = nullptr;

    node(int _s, int _e)
    {
        s = _s, e = _e, m = (s + e) >> 1;
    }

    bool inside(int i)
    {
        return s <= i && i <= e;
    }

    void update(int i, ll j)
    {
        if (s == e)
            val = j;
        else
        {
            if (i <= m)
            {
                if (l == nullptr)
                    l = new node(i, i);
                else if (!l->inside(i))
                {
                    node *temp = l;
                    ii child = lca(l->s, l->e, i);
                    l = new node(child.first, child.second);
                    if (temp->e <= l->m)
                        l->l = temp;
                    else
                        l->r = temp;
                }
                l->update(i, j);
            }
            else
            {
                if (r == nullptr)
                    r = new node(i, i);
                else if (!r->inside(i))
                {
                    node *temp = r;
                    ii child = lca(r->s, r->e, i);
                    r = new node(child.first, child.second);
                    if (temp->e <= r->m)
                        r->l = temp;
                    else
                        r->r = temp;
                }
                r->update(i, j);
            }
            val = func((l == nullptr) ? 0 : l->val, (r == nullptr) ? 0 : r->val);
        }
    }

    ll query(int i, int j)
    {
        if (i <= s && e <= j)
            return val;
        else if (j <= m)
            return (l == nullptr) ? 0 : l->query(i, j);
        else if (m < i)
            return (r == nullptr) ? 0 : r->query(i, j);
        else
            return func((l == nullptr) ? 0 : l->query(i, m), (r == nullptr) ? 0 : r->query(m + 1, j));
    }

    node *clone()
    {
        node *res = new node(s, e);
        res->val = val;
        res->l = (l == nullptr) ? nullptr : l->clone();
        res->r = (r == nullptr) ? nullptr : r->clone();
        return res;
    }
};

struct node2d
{
    int s, e, m;
    node *val = new node(0, (1 << 30) - 1);
    node2d *l = nullptr, *r = nullptr;

    node2d(int _s, int _e)
    {
        s = _s, e = _e, m = (s + e) >> 1;
    }

    bool inside(int i)
    {
        return s <= i && i <= e;
    }

    void update(int i, int j, ll k)
    {
        if (s == e)
            val->update(j, k);
        else
        {
            if (i <= m)
            {
                if (l == nullptr)
                    l = new node2d(i, i);
                else if (!l->inside(i))
                {
                    node2d *temp = l;
                    ii child = lca(l->s, l->e, i);
                    l = new node2d(child.first, child.second);
                    if (temp->e <= l->m)
                        l->l = temp;
                    else
                        l->r = temp;
                    l->val = temp->val->clone();
                }
                l->update(i, j, k);
            }
            else
            {
                if (r == nullptr)
                    r = new node2d(i, i);
                else if (!r->inside(i))
                {
                    node2d *temp = r;
                    ii child = lca(r->s, r->e, i);
                    r = new node2d(child.first, child.second);
                    if (temp->e <= r->m)
                        r->l = temp;
                    else
                        r->r = temp;
                    r->val = temp->val->clone();
                }
                r->update(i, j, k);
            }
            val->update(j, func((l == nullptr) ? 0 : l->val->query(j, j), (r == nullptr) ? 0 : r->val->query(j, j)));
        }
    }

    ll query(int i, int j, int i2, int j2)
    {
        if (i <= s && e <= j)
            return val->query(i2, j2);
        else if (j <= m)
            return (l == nullptr) ? 0 : l->query(i, j, i2, j2);
        else if (m < i)
            return (r == nullptr) ? 0 : r->query(i, j, i2, j2);
        else
            return func((l == nullptr) ? 0 : l->query(i, m, i2, j2), (r == nullptr) ? 0 : r->query(m + 1, j, i2, j2));
    }
} *root = new node2d(0, (1 << 30) - 1);

void init(int R, int C) {}

void update(int P, int Q, ll K) { root->update(P, Q, K); }

ll calculate(int P, int Q, int U, int V) { return root->query(P, U, Q, V); }

结语

到这里，有关树套树的理解也算是加深了不少，也可以在此基础上进行修改，拿到别的树套树问题上去用了。其他的二维数点问题以后可以再慢慢汇总。毕竟这些问题转换到二维数点上还是很复杂的，光有板子是不行的（没准还不得不动用其他离线做法）。

那就先推荐几个和本题很像的题目吧。

BZOJ4066. 简单题

二维数点的另一个强制在线模板题，但是无法用树套树通过（空间不够），此时需要采用kd-树，牺牲时间来赚取空间的优势。而且kd-树在更高维度的查询会占更多优势，还是建议学习一下的。

平均气温

来自清华大学数据结构MOOC的编程作业，也是一道半强制在线交互的二维数点模板题，因为是先输入所有点的坐标再统一查询，所以可以在得到所有的点坐标之后一次性建树。注意本题kd树写不好的话，只能得80分（因为查询的上限次数为50万次，无法在时间上限10秒内全部完成），正解还是使用2D范围树或者树套树。本人的上述代码在针对本题，修改需要维护的内容之后，最强的点也可以在5.1秒以内跑完。