小团的复制粘贴 #

发布于2021-04-16

上次编辑2021-04-16

问题描述#

小团是一个莫得感情的 CtrlCV 大师，他有一个下标从 1 开始的序列 A 和一个初始全部为 -1 序列 B ，两个序列的长度都是 n 。他会进行若干次操作，每一次操作，他都会选择 A 序列中一段连续区间，将其粘贴到 B 序列中的某一个连续的位置，在这个过程中他也会查询 B 序列中某一个位置上的值。
我们用如下的方式表示他的粘贴操作和查询操作：
粘贴操作：1 k x y，表示把 A 序列中从下标 x 位置开始的连续 k 个元素粘贴到 B 序列中从下标 y 开始的连续 k 个位置上。原始序列中的元素被覆盖。（数据保证不会出现粘贴后 k 个元素超出 B 序列原有长度的情况）
查询操作：2 x，表示询问B序列下标 x 处的值是多少。

格式：
输入：
- 输入第一行包含一个正整数 n ，表示序列 A 和序列 B 的长度。
- 输入第二行包含 n 个正整数，表示序列 A 中的 n 个元素，第 i 个数字表示下标为 i 的位置上的元素，每一个元素保证在 10^9 以内。
- 输入第三行是一个操作数 m ，表示进行的操作数量。
- 接下来 m 行，每行第一个数字为 1 或 2 ，具体操作细节详见题面。
输出：
- 对于每一个操作 2 输出一行，每行仅包含一个正整数，表示针对某一个询问的答案。
示例 1：
输入：
     5
     1 2 3 4 5 
     5
     2 1
     2 5
     1 2 3 4
     2 3
     2 5
输出：
     -1
     -1
     -1
     4
示例 2：
输入：
     5
     1 2 3 4 5 
     9
     1 2 3 4
     2 3
     2 5
     1 2 2 3
     2 1
     2 2
     2 3
     2 4
     2 5
输出：
     -1
     4
     -1
     -1
     2
     3
     4
提示：

1 <= n <= 2000

1 <= m <= 2000

解题思路#

实际上的测试数据量在 30,000 ~ 40,000 之间。

记录操作 1 k x y，然后询问时 2 x，从操作记录中从后往前遍历找到第一个在变化区间的的操作，并输出对应的值即可。如果找不到变化的区间，则输出 -1。

Python

import sys
from typing import List

readline = sys.stdin.readline


def readint() -> int:
    return int(readline().strip())


def readstr() -> str:
    return readline().strip()


def readints() -> List[int]:
    return list(map(int, readline().strip().split()))


n = readint()
A = [0] + readints()
m = readint()
op = []
for _ in range(m):
    o = readints()
    if o[0] == 1:
        k, x, y = o[1:]
        op.append((y, y + k - 1, x))
    else:
        x = o[1]
        out = -1
        for l, r, s in reversed(op):
            if l <= x <= r:
                out = A[s + x - l]
                break
        print(out)

C++

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n;
    vector<int> A(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> A[i];
    }
    cin >> m;
    vector<tuple<int, int, int>> op;
    while (m--) {
        int q, k, x, y;
        cin >> q;
        if (q == 1) {
            cin >> k >> x >> y;
            op.emplace_back(y, y + k - 1, x);
        } else {
            cin >> x;
            int out = -1;
            for (int i = (int)op.size() - 1; i >= 0; --i) {
                auto &[l, r, s] = op[i];
                if (l <= x && x <= r) {
                    out = A[s + x - l];
                    break;
                }
            }
            cout << out << '\n';
        }
    }
    return 0;
}

小团的复制粘贴# 发布于2021-04-16 上次编辑2021-04-16

问题描述#

解题思路#

小团的复制粘贴 #

发布于2021-04-16

上次编辑2021-04-16