自动搬运

查看原文

来自洛谷，原作者为

	fanhy 欧拉 阿里 啵哒 木大

搬运于2025-08-24 21:22:14，当前版本为作者最后更新于2019-02-20 18:14:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

谁说$O(N*K)$算法要靠$RP$的

这题模拟才不到300ms，稳稳的

将一段文本剪切下来粘到另一段文本后面，相当于将这两段文本交换

使用temp数组记录下剪切下的文本，将另一段文本向前（插入行在原文本第一行之后）或向后（插入行在原文本第一行之前）。

将temp数组里的数赋值到该黏贴的位置就可以了。

AC代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;
int n, k;
int doc[MAXN], temp[MAXN];
int cnt;

int main()
{
    for (int i = 1; i < MAXN; i++) doc[i] = i;
    cin >> n >> k;
    for (int oper = 0; oper < k; oper++)
    {
        int s, t, p1, p2, ins, len;
        cin >> s >> t >> ins;
        len = t - s + 1;
        p1 = ins + 1;
        p2 = p1 + len - 1;
        cnt = 0;
        for (int i = s; i <= t; i++) temp[++cnt] = doc[i];
        if (ins < s) for (int i = s - 1; i >= p1; i--) doc[i + len] = doc[i];
        else for (int i = t + 1; i <= p2; i++) doc[i - len] = doc[i];
        for (int i = p2; i >= p1; i--) doc[i] = temp[cnt--];
    }
    for (int i = 1; i <= 10; i++) cout << doc[i] << endl;
    return 0;
}