题目理解

我们有三种操作：

1. 插入（$k=1$）：姓名为 $S$ 的学生选课
2. 删除（$k=2$）：姓名为 $S$ 的学生退课
3. 查询（$k=3$）：给定前缀 $S$ 和参数 $a,b,c$，计算阈值 $v = (a \times |lastAns| + b) \bmod c$，问最早在哪个事件后，以 $S$ 为前缀的学生数 超过 $v$

关键点：

• 学生姓名可重复
• 查询的是历史事件，不是当前状态
• 阈值 $v$ 依赖于上一次查询结果

核心思路

1. 数据结构选择

我们需要维护所有前缀的计数历史，并在任意时刻能回答“最早超过 $k$ 个人的时间”。

这可以用 Trie 树 实现：

• 每个 Trie 节点对应一个前缀
• 节点记录：
  • cnt：当前该前缀的学生数
  • ans：一个列表，ans[i] 表示第 i+1 个学生加入时的事件编号

2. 操作处理

插入

沿 Trie 插入字符串 $S$，对路径上每个节点：

• cnt[p]++
• 如果 ans[p].size() < cnt[p]，说明这是该前缀的第 cnt[p] 个学生，把当前事件编号加入 ans[p]

删除

沿 Trie 走到对应节点，cnt[p]--（但 ans[p] 不删，保留历史）

查询

1. 计算阈值 $v = (a \times |lastAns| + b) \bmod c$
2. 走到前缀 $S$ 对应的节点
3. 如果 ans[p].size() <= v，说明历史上从未超过 $v$ 个人，输出 $-1$
4. 否则输出 ans[p][v]（因为我们要的是超过 $v$ 的最早时间，即第 $v+1$ 个学生加入的时间）

算法正确性分析

为什么 ans[p] 列表能工作？

• ans[p][i] 记录的是该前缀第 i+1 个学生加入的事件编号
• 当查询“超过 $v$ 个人”时，就是找第 $v+1$ 个学生加入的时间
• 由于插入时按顺序记录，ans[p][v] 就是答案

删除为什么不影响历史记录？

因为题目问的是历史上最早超过阈值的时间，即使后来有人退课，历史最大值仍然保留在 ans[p] 中。

复杂度分析

• 时间复杂度：每个插入/删除/查询操作 $O(|S|)$，其中 $|S| \le 60$
• 空间复杂度：Trie 节点数 $O(n \cdot |S|)$，每个节点 ans 列表总大小 $O(n \cdot |S|)$
• 对于 $n \le 10^5$ 可以接受

代码详解

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

constexpr int N = 6E6;  // Trie 最大节点数
constexpr int M = 10;   // 字符集大小 (a-j)

int tr[N][M];     // Trie 树
int cnt[N];       // 当前节点对应前缀的学生数
vector<int> ans[N]; // ans[p][i] 记录第 i+1 个学生加入的事件编号

int sz = 1;       // Trie 节点计数，1 为根节点

void insert(const string &s, int tim) {
    int p = 1;  // 从根节点开始
    
    for (auto c : s) {
        // 移动到对应子节点
        if (!tr[p][c - 'a']) {
            tr[p][c - 'a'] = ++sz;
        }
        p = tr[p][c - 'a'];
        
        // 更新计数
        cnt[p]++;
        
        // 如果是第 cnt[p] 个学生，记录事件编号
        if ((int)ans[p].size() < cnt[p]) {
            ans[p].push_back(tim);
        }
    }
}

void del(const string &s) {
    int p = 1;
    for (auto c : s) {
        p = tr[p][c - 'a'];
        cnt[p]--;  // 只减少计数，不删除历史记录
    }
}

int res = 0;  // 上一次查询结果

void query(const string &s, int c) {
    int p = 1;
    for (auto c : s) {
        p = tr[p][c - 'a'];
    }
    
    // 如果历史上从未超过 c 个人
    if (ans[p].size() <= c) {
        res = -1;
    } else {
        // ans[p][c] 是第 c+1 个学生加入的时间
        res = ans[p][c];
    }
}

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

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int o;
        cin >> o;

        if (o == 1) {
            string s;
            cin >> s;
            insert(s, i);
        } else if (o == 2) {
            string s;
            cin >> s;
            del(s);
        } else {
            string s;
            int a, b, c;
            cin >> s >> a >> b >> c;
            // 计算阈值 v = (a*|lastAns| + b) mod c
            int p = (1ll * a * abs(res) + b) % c;
            
            query(s, p);
            
            cout << res << "\n";
        }
    }

    return 0;
}

样例验证

以题目样例为例：

8
1 jead      // 插入 "jead"
1 dec       // 插入 "dec"  
3 de 0 0 10 // 查询前缀 "de"，v=(0*0+0)%10=0
            // ans[de] = [2] (第1个学生在事件2加入)
            // ans[de].size()=1 > 0，输出 ans[de][0]=2

1 dec       // 再插入 "dec"
3 de 0 1 10 // v=(0*2+1)%10=1
            // ans[de] = [2,4] (第2个学生在事件4加入)
            // ans[de].size()=2 > 1，输出 ans[de][1]=4

2 dec       // 删除一个 "dec"
3 de 0 1 10 // v=(0*4+1)%10=1
            // 当前cnt[de]=1，但历史上有2个人
            // ans[de].size()=2 > 1，输出 ans[de][1]=4

3 de 0 2 10 // v=(0*4+2)%10=2
            // ans[de].size()=2 <= 2，输出 -1

总结

这道题的关键在于理解：

1. 查询的是历史信息，不是当前状态
2. 用 Trie 维护所有前缀
3. 在每个节点记录每个第 k 个学生加入的时间
4. 查询时直接通过阈值 $v$ 索引到对应历史记录

这种记录完整历史的方法可以高效回答各种关于历史状态的查询，是处理这类问题的有效技巧。