题解

我们要枚举改哪条指令，算出改完以后每个位置被射击多少次，再看哪些靶子够次数得分。

这题可以沿着一个思路做下去，先把所有射击平移，再从左往右把前面的射击恢复到原位置。

改一条指令，后面的射击一起平移

先按原指令走一遍，记下执行第 $i$ 条指令之前的位置 $p_i$。如果这一条是 F，原来的射击位置就是 $p_i$。

假设把某一条 L 改成 R。原来向左走一格，现在向右走一格，执行完这一步后，新位置比原位置大 $2$。接下来执行的指令完全相同，所以这个差距一直保持为 $2$，后面的每次射击都向右平移两格。

其他修改也一样。将 L、R、F 的移动量分别记为 $-1,1,0$，后面需要平移的量就是

$$d=\text{新指令的移动量}-\text{原指令的移动量}.$$

所以只有 $-2,-1,0,1,2$ 这五种平移量。这里也允许新旧指令相同，把不修改的情况一起算进去。

若修改的是第 $i$ 条，那么第 $i$ 条之前的射击都在原位置，第 $i$ 条之后的射击都平移 $d$。当前这一条单独处理，改成 F 就在 $p_i$ 射击，改成移动就不射击。

先固定一个平移量，看数组怎么维护

先只考虑某一个 $d$，开一个计数数组，记录每个坐标有多少次射击。

初始化时，把原来的所有射击都平移 $d$。原来在 $p_j$ 射击，就给 $p_j+d$ 这个位置的计数加一。

接着从左往右枚举修改位置。刚开始，前面没有指令，全部射击都还处在平移后的位置。每经过一条原来的 F，就把它从 $p_i+d$ 删掉，再加回 $p_i$。这样前面的射击会逐渐恢复，后面的射击仍然保持平移。

不过，第 $i$ 条正是这次准备修改的指令，算答案时不能把它当作原来的射击保留下来。因此要把恢复过程拆成两步，把算答案放在中间。

处理到第 $i$ 条时	前面的射击	当前这条原有的射击	后面的射击
本轮开始	已恢复原位	还在 $p_i+d$	仍然平移 $d$
删掉当前射击后		不在数组里
本轮结束		加回 $p_i$

如果原指令是移动，本来就没有这次射击，删除和加回都不用做。

中间这一行就是算答案时需要的状态。 修改位置之前不变，之后整体平移，当前指令留给我们决定。

实际程序把五个 $d$ 对应的计数数组都存下来。一次删除或恢复在五个数组中各做一次，每个数组仍然按上面的规则维护。

当前改成什么，就取对应的那份计数

到第 $i$ 条时，若原指令是 F，先从五份数组的 $p_i+d$ 位置各删掉一次射击。

然后枚举新指令。

例如原来是 R，改成 L 就取 $d=-2$ 的数组，改成 F 就取 $d=-1$ 的数组，不修改就取 $d=0$ 的数组。选哪份数组，完全由这次修改确定。

若新指令是移动，这份数组已经包含改完后的全部射击，直接读取它的总分。

若新指令是 F，还要在 $p_i$ 补一枪。只看这个坐标就够了。如果那里有靶子，并且当前恰好还差一枪，就加上它的分值；已经达到要求，或者还差两枪以上，都不会增加得分。

这枪只用于计算当前候选答案，不必真的加进数组。否则枚举下一种修改时还得把它撤销。

三种选择都算完后，若原指令是 F，再把原来的这枪加回五份数组的 $p_i$ 位置。接着枚举 $i+1$，第 $i$ 条就属于不修改的前缀了。

因此每一轮都是

删掉当前原有的射击
枚举新指令，读取对应平移量的得分，需要时补算当前这一枪
把原有射击恢复到原位置，继续枚举下一个修改位置

最后恢复的是原指令，因为下一轮讨论的是改第 $i+1$ 条，第 $i$ 条就应该照原样执行。当前试过的修改不会保留到下一轮。

总分也跟着计数一起改

每份计数数组旁边存一个总分。一个坐标达到靶子的要求次数，就在总分中计入它的分值一次。

当某个坐标的计数加一或减一时，只有这个靶子的得分可能变化。先减去它原先的得分，修改计数，再加上它现在的得分，就能在 $O(1)$ 时间内更新总分。没有靶子的坐标不影响总分。

前面的射击和后面平移过来的射击，如果落在同一个坐标，就直接累加在同一个数组格子里。比如这个靶子需要三枪，前面打了两枪、后面打了一枪，数组里存的就是三，正常计分即可。两边都已经打够次数时，也只会计入这个靶子的分值一次。

这样就不需要把前后两段的得分分开计算，也没有额外的重叠修正。

上面的维护过程保证，枚举每一种修改时，选中的计数数组恰好包含修改后前后两段的全部射击；若当前改成 F，再补算这一枪，就得到了该方案的准确分数。所有修改位置、所有新指令都枚举到了，取最大值即可。

原来是 F 而选择不修改时，也遵循同一流程，先删掉它，再在 $d=0$ 的数组上补算回来。因此不修改的情况不会漏掉。

预处理花费 $O(n+m)$，每条射击在五份数组里各初始化、删除、恢复一次，每个位置只枚举三种指令，总时间为 $O(n+m)$，空间为 $O(n)$。可以通过全部子任务。

代码把 $d$ 存在编号 $d+2$ 中，因此 score[2] 表示平移量为 $0$ 的那份总分。坐标可能为负，统一加上偏移量；临时平移还可能多出两格，要留好数组边界。总分用 long long。

部分分可以怎样做

$n,m\le2000$

枚举修改位置和新指令，每次从头模拟，统计命中次数并计算得分。一次模拟 $O(n)$，总时间 $O(n^2+m)$，空间 $O(n)$，可以得到子任务 1 的 $20$ 分。

射击次数不超过 $20$

先记录原来每次射击的位置。枚举一次修改后，只遍历这些射击，修改位置之前的坐标不动，之后的坐标加 $d$，当前这次原有射击跳过，新指令是 F 时再补一枪。

所有射击都处理到了，把同坐标的命中次数合并后就能准确算分。设原来有 $k$ 次射击，用时间戳数组或记录本次碰过的坐标来清空计数，一种方案只需 $O(k+1)$ 时间。总时间 $O(n(k+1)+m)$，空间 $O(n)$，可通过子任务 1、2，共 $35$ 分。

所有 F 连续出现

设这段指令是 $[l,r]$，长度为 $q$，原来的射击位置为 $a$。因为中间没有移动，这 $q$ 枪都打在 $a$。

修改位置在这段之前时，整段射击一起平移；在这段之后时，整段射击不动。这两种情况下，若新指令是 F，再补上修改位置的一枪。

修改位置 $i$ 在这段里面时，如果改成移动，前面的 $i-l$ 枪还在 $a$，后面的 $r-i$ 枪移到相邻坐标，当前这一枪消失。不修改则仍是 $q$ 枪打在 $a$。

每种方案最多涉及两个坐标，相同坐标先合并次数，$O(1)$ 就能算出得分。总时间 $O(n+m)$，空间 $O(n)$，能得到子任务 3 的 $15$ 分。

原串不含 L

这时原路线只向右走。枚举第 $i$ 条时，前面的射击都在 $p_i$ 及其左侧，后面的射击平移 $d$ 后，都在 $p_i+d$ 及其右侧。

可以分别维护前面的得分和后面五种平移的得分。两段可能重叠的坐标只在 $[p_i+d,p_i]$ 中；当左端点大于右端点时没有重叠，否则至多三个坐标。

每次先把两段得分相加，再对这些坐标减去两边分别计算的得分，合并命中次数后重新加一次。新指令若是 F，再按合并后的次数补算这一枪。重叠以外的靶子只会被一段打中，不需要修正。

扫描时，原来的射击从后面移到前面，分别维护这些计数和总分即可。每个位置只更新、检查常数个坐标，总时间 $O(n+m)$，空间 $O(n)$，能得到子任务 4 的 $20$ 分。将上述方法按输入条件选用，可以通过前四个子任务，共 $70$ 分。

参考代码

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

int step(char c) {
    if (c == 'L') return -1;
    if (c == 'R') return 1;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    const int offset = n + 4, size = 2 * n + 9;
    vector<int> need(size), pos(n);
    vector<ll> weight(size);
    for (int j = 0; j < m; ++j) {
        int x, b;
        ll w;
        cin >> x >> b >> w;
        need[x + offset] = b;
        weight[x + offset] = w;
    }

    int p = offset;
    for (int i = 0; i < n; ++i) {
        pos[i] = p;
        p += step(s[i]);
    }

    // 编号 k 对应后缀平移 k - 2，计数中已合并前缀和后缀。
    vector<array<int, 5>> cnt(size);
    array<ll, 5> score{};
    auto update = [&](int x, int k, int change) {
        if (weight[x] && cnt[x][k] >= need[x]) score[k] -= weight[x];
        cnt[x][k] += change;
        if (weight[x] && cnt[x][k] >= need[x]) score[k] += weight[x];
    };

    for (int i = 0; i < n; ++i) {
        if (s[i] == 'F') {
            for (int k = 0; k < 5; ++k) update(pos[i] + k - 2, k, 1);
        }
    }
    ll answer = score[2];

    for (int i = 0; i < n; ++i) {
        // 先排除当前指令，剩下的才是严格前缀与严格后缀。
        if (s[i] == 'F') {
            for (int k = 0; k < 5; ++k) update(pos[i] + k - 2, k, -1);
        }

        for (char c : {'L', 'R', 'F'}) {
            int k = step(c) - step(s[i]) + 2;
            ll candidate = score[k];
            int x = pos[i];
            // 新指令为 F 时，在修改前的位置补一次射击。
            if (c == 'F' && weight[x] && cnt[x][k] == need[x] - 1) {
                candidate += weight[x];
            }
            answer = max(answer, candidate);
        }

        // 移动分界线，原指令的射击转入不平移的前缀。
        if (s[i] == 'F') {
            for (int k = 0; k < 5; ++k) update(pos[i], k, 1);
        }
    }
    cout << answer << '\n';
    return 0;
}