TIOJ 1836：[IOI 2013] 遊戲 Game

TIOJ 1836：[IOI 2013] 遊戲 Game

題目大意：有一個大小 $n \times m$ 個格子的平面，每格有一個數字，初始皆為 $0$。有 $q$ 筆操作，每筆操作可更改其中一格數字或詢問一個區間裡所有數字的最大公因數。$1≤n, m≤10^9, 1≤q≤3\times 10^5$。

解法：可以考慮二維的動態開點線段樹，但如果每次都直接多 $O(log(n)\times log(m))$ 個節點記憶體會爆掉，可以直接將大區間指向小節點，如果之後範圍衝突到了再對小節點新增一個父節點。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 3e5 + 5;

int n, m, q, Root;

// 1d - segtree

struct _node {
    int l, r;
    long long gcd;
    int ls, rs;
    _node() {}
    _node (int l, int r) : l (l), r (r), gcd (0), ls (0), rs (0) {}
} node[30 * SIZE];

int cnt;

int newnode (int l, int r) {
    node[++cnt] = _node (l, r);
    return cnt;
}

int clone (int pos) {
    int nd = newnode (node[pos].l, node[pos].r);
    node[nd].gcd = node[pos].gcd;
    if (node[pos].ls) node[nd].ls = clone (node[pos].ls);
    if (node[pos].rs) node[nd].rs = clone (node[pos].rs);
    return nd;
}

void check (int &pos, int l, int r, int p) {
    if (!pos) {
        pos = newnode (p, p);
        return;
    }
    if (node[pos].l <= p && p <= node[pos].r) return;
    int nd = newnode (l, r), mid = (l + r) / 2;
    if (node[pos].r <= mid) node[nd].ls = pos;
    else node[nd].rs = pos;
    node[nd].gcd = node[pos].gcd;
    pos = nd;
}

void update (int pos, int p, long long k) {
    int l = node[pos].l, r = node[pos].r;
    if (l == r) {
        node[pos].gcd = k;
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid) {
        check (node[pos].ls, l, mid, p);
        update (node[pos].ls, p, k);
    } else {
        check (node[pos].rs, mid + 1, r, p);
        update (node[pos].rs, p, k);
    }
    node[pos].gcd = __gcd (node[pos].ls ? node[node[pos].ls].gcd : 0, node[pos].rs ? node[node[pos].rs].gcd : 0);
}

long long query (int pos, int l, int r) {
    if (!pos) return 0;
    int L = node[pos].l, R = node[pos].r;
    if (l <= L && R <= r) return node[pos].gcd;
    int mid = (L + R) / 2;
    if (r <= mid) return query (node[pos].ls, l, r);
    if (l > mid) return query (node[pos].rs, l, r);
    return __gcd (query (node[pos].ls, l, mid), query (node[pos].rs, mid + 1, r));
}

// 2d - segtree

struct _Node {
    int u, d, root, ls, rs;
    _Node() {}
    _Node (int u, int d) : u (u), d (d), root (newnode (1, m)), ls (0), rs (0) {}
} Node[SIZE];

int Cnt;

int newNode (int u, int d) {
    Node[++Cnt] = _Node (u, d);
    return Cnt;
}

void Check (int &pos, int u, int d, int p) {
    if (!pos) {
        pos = newNode (p, p);
        return;
    }
    if (Node[pos].u <= p && p <= Node[pos].d) return;
    int Nd = newNode (u, d), mid = (u + d) / 2;
    if (Node[pos].d <= mid) Node[Nd].ls = pos;
    else Node[Nd].rs = pos;
    Node[Nd].root = clone (Node[pos].root);
    pos = Nd;
}

void Update (int pos, int x, int y, long long k) {
    int u = Node[pos].u, d = Node[pos].d;
    if (u == d) {
        update (Node[pos].root, y, k);
        return;
    }
    int mid = (u + d) / 2;
    if (x <= mid) {
        Check (Node[pos].ls, u, mid, x);
        Update (Node[pos].ls, x, y, k);
    } else {
        Check (Node[pos].rs, mid + 1, d, x);
        Update (Node[pos].rs, x, y, k);
    }
    update (Node[pos].root, y, __gcd (Node[pos].ls ? query (Node[Node[pos].ls].root, y, y) : 0, Node[pos].rs ? query (Node[Node[pos].rs].root, y, y) : 0));
}

long long Query (int pos, int u, int d, int l, int r) {
    if (!pos) return 0;
    int U = Node[pos].u, D = Node[pos].d;
    if (u <= U && D <= d) return query (Node[pos].root, l, r);
    int mid = (U + D) / 2;
    if (d <= mid) return Query (Node[pos].ls, u, d, l, r);
    if (u > mid) return Query (Node[pos].rs, u, d, l, r);
    return __gcd (Query (Node[pos].ls, u, mid, l, r), Query (Node[pos].rs, mid + 1, d, l, r));
}

void solve() {
    cin >> n >> m >> q;
    Root = newNode (1, n);
    while (q--) {
        int ty;
        cin >> ty;
        if (ty == 1) {
            int x, y;
            long long k;
            cin >> x >> y >> k;
            Update (Root, ++x, ++y, k);
        } else {
            int u, d, l, r;
            cin >> u >> l >> d >> r;
            cout << Query (Root, ++u, ++d, ++l, ++r) << '\n';
        }
    }
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！