Copying Data

Identity_Equation · 2023-11-09 10:43:47 · 个人记录

又是一道支持区间修改单点查询线段树模板题。

思路：

• 把 a 数组与 b 数组放在同一个数组中， 其中 b 放从 1 到 n 的位置， a 放从 n + 1 到 2 * n 的位置。
• 每个节点上建立两个参数：al 块的答案的开头， nl 块的起始位置。
• 区间修改两个参数 al = x + n ; nl = y。
• 单点查询，输出位置。

先解释一下 al 与 nl 的意义（以样例为例）：

upd1 : 一个数字的位置只与他所属块的开头与答案的开头有关。

upd2 : 在线段树中处理的是位置， 而不是数值， 因为位置是连续的。

5 10
1 2 0 -1 3
3 1 5 -2 0
2 5
1 3 3 3
2 5
2 4
2 1
1 2 1 4
2 1
2 4
1 4 2 1
2 2

初始的状态(全都是一个块) ：{al, bl}:{1, 1} {1, 1} {1, 1} {1, 1} {1, 1}。

第一次修改(1 3 3 3) : {al, bl} : {1, 1} {1, 1} {8, 3} {8, 3} {8, 3}。

第二次修改( 1 2 1 4) : {al, bl} : {7, 1} {7, 1} {7, 1} {7, 1} {8, 3}。

第三次修改( 1 4 2 1 ) : {al, bl} : {7, 1} {9, 2} {7, 1} {7, 1} {8, 3}。

对于每一次查询 x 我们都可以返回 x - nl + al 这个值。

Code :

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e5 + 5;
struct node {
    int l, r;
    int al, nl;
    int tagal, tagnl;
} tree[N << 2];

void build (int p, int l, int r) {
    tree[p].l = l, tree[p].r = r;
    tree[p].al = 1;
    tree[p].nl = 1;
    if (l == r) return;
    int mid = l + r >> 1;
    build (p << 1, l, mid);
    build (p << 1 | 1, mid + 1, r);
    return;
} 

void push_down (int p) {
    if (tree[p].tagal) {
        tree[p << 1].al = tree[p].tagal;
        tree[p << 1 | 1].al = tree[p].tagal;
        tree[p << 1].tagal = tree[p].tagal;
        tree[p << 1 | 1].tagal = tree[p].tagal;
        tree[p].tagal = 0;
        tree[p << 1].nl = tree[p].tagnl;
        tree[p << 1 | 1].nl = tree[p].tagnl;
        tree[p << 1].tagnl = tree[p].tagnl;
        tree[p << 1 | 1].tagnl = tree[p].tagnl;
        tree[p].tagnl = 0;
    }
    return;
}

void update (int p, int l, int r, int al, int nl) {
    if (tree[p].l >= l && tree[p].r <= r) {
        tree[p].al = al;
        tree[p].nl = nl;
        tree[p].tagal = al;
        tree[p].tagnl = nl;
        return;
    }
    int mid = tree[p].l + tree[p].r >> 1;
    push_down(p);
    if (mid >= l) update (p << 1, l, r, al, nl);
    if (mid < r) update (p << 1 | 1, l, r, al, nl);
    return;
} 

int query (int p, int x) {
    if (tree[p].l == tree[p].r) {
        int res = tree[p].al + tree[p].l - tree[p].nl;
        return res;
    }
    push_down (p);
    int mid = tree[p].l + tree[p].r >> 1;
    if (mid >= x) return query (p << 1, x);
    else return query (p << 1 | 1, x);
}
int a[N << 2];
signed main () {
    int n, m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++) cin >> a[i + n];
    for (int i = 1 ; i <= n ; i ++) cin >> a[i];
    build (1, 1, n);
    while (m --) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y, k;
            cin >> x >> y >> k;
            update (1, y, y + k - 1, x + n, y);
        } else {
            int x;
            cin >> x;
            cout << a[query(1, x)] << '\n';
        }
    }
    return 0;
}

最后向大家推荐一个查线段树代码的方法：

void gs(int p){
    if(tree[p].l == tree[p].r){
        printf("{%lld, %lld} ", tree[p].al, tree[p].nl);
        return;
    }
    push_down(p);
    gs(p << 1);
    gs(p << 1 | 1);
    return;
}

遍历整棵线段树。