CodeForces - 292E

一种操作:从数组 a 的第 $x$ 位开始,复制到数组 b 的第 $y$ 位开始,长度为 $k$ 的子串
询问一个位置的值

线段树保存b数组是否被覆盖,并记录覆盖操作的 $x-y$ ,每次询问输出 $a[i+x-y]$ 或 $b[i]$

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4.2e6;
int a[maxn], b[maxn], n, m;
int tx[maxn];
int tc[maxn];
int lazy[maxn];

void pushdown(int rt)
{
    if (lazy[rt])
    {
        tx[rt << 1 | 1] = tx[rt << 1] = tx[rt];
        tc[rt << 1 | 1] = tc[rt << 1] = tc[rt];
        lazy[rt << 1 | 1] = lazy[rt << 1] = lazy[rt];
        lazy[rt] = 0;
    }
}
void update(int rt, int l, int r, int L, int R, int va)
{
    if (L <= l && r <= R)
    {
        tx[rt] = va, lazy[rt] = 1;
        tc[rt] = 1;
        return;
    }
    pushdown(rt);
    int mid = l + r >> 1;
    if (L <= mid)
        update(rt << 1, l, mid, L, R, va);
    if (mid < R)
        update(rt << 1 | 1, mid + 1, r, L, R, va);
}
int query(int rt, int l, int r, int pos)
{
    if (l == r)
    {
        if (tc[rt] == 0)
            return b[l];
        return a[l + tx[rt]];
    }
    pushdown(rt);
    int mid = l + r >> 1;
    if (pos <= mid)
        query(rt << 1, l, mid, pos);
    else
        query(rt << 1 | 1, mid + 1, r, pos);
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    for (int i = 1; i <= n; i++)
        scanf("%d", b + i);
    while (m--)
    {
        int cmd;
        scanf("%d", &cmd);
        if (cmd == 1)
        {
            int x, y, k;
            scanf("%d %d %d", &x, &y, &k);
            update(1, 1, n, y, y + k - 1, x - y);
        }
        else
        {
            int x;
            scanf("%d", &x);
            printf("%d\n", query(1, 1, n, x));
        }
    }
}