自动搬运

查看原文

来自洛谷，原作者为

	DengDuck 澳門現役 OIer，萌萌未花日奈雙推人一枚

搬运于2025-08-24 21:55:47，当前版本为作者最后更新于2024-04-21 21:52:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我校小朋友发现暴力能过。

注意要利用 STL 容器 string，这样插入的效率很快，但是比对那里 $\mathcal O(n)$ 咋过的就很玄学。

原因主要是因为 STL 容器在随机数据下跑得飞快的原因。

建议加强数据。

提供一种 Hack 方法，没有修改插入操作，全是查询，然后字符串所有字符都一样，然后每次查询的位置是 $1$ 和 $\dfrac 1 2 (n+1)$。

Upd：根据我的测试，我的方案并不能卡掉暴力，目测是查询次数在 $10^4$ 次以内，每次 $\mathcal O(n)$ 可以勉强撵过去。

而其他操作虽然是 $\mathcal O(n)$，但是 STL，懂得都懂，卡不了啊......

#include <bits/stdc++.h>
#define fo(i, a, b) for (int i = a; i <= b; i++)
using namespace std;
string s;
int n, m;
int main() {
    cin >> s;
    n = s.size();
    cin >> m;
    fo(i, 1, m) {
        string o, c;
        int x, d;
        cin >> o >> x;
        if (o == "Q") {
            cin >> d;
            x--, d--;
            int lcq = 0;
            for (int i = x, j = d; i < n && j < n; i++, j++)
                if (s[i] == s[j])
                    lcq++;
                else
                    break;
            printf("%d\n", lcq);
        }
        if (o == "R") {
            cin >> c;
            s[x - 1] = c[0];
        }
        if (o == "I") {
            cin >> c;
            s.insert(x, c);
            n = s.size();
        }
    }
    return 0;
}

代码是我校一个小朋友的，不是我的。