思路

我们可以使用 最大堆（或最小堆），来实时维护当前学习过程中最久未遗忘的汉字的记忆值。这样做的好处是：

1. 每次学习汉字之前，我们可以通过堆来快速地找出哪些汉字已经遗忘（即记忆值为 0）。
2. 使用优先队列可以避免在每次学习之前遍历所有汉字来衰减记忆值，提升效率。

算法步骤

1. 汉字记忆衰减：在每次学习一个新汉字之前，检查堆顶元素（最大记忆值）是否为零，如果是零，则表示这个汉字已经遗忘，应该从堆中删除。然后将所有未遗忘的汉字的记忆衰减。
2. 记忆更新：每次学习汉字时，更新该汉字的学习次数，并计算其记忆值增加量。
3. 堆的管理：使用一个最大堆来存储当前所有未遗忘的汉字的记忆值，堆中的元素随着学习过程中汉字记忆值的变化而更新。

时间复杂度

• 每次学习操作的时间复杂度是 $O(\log k)$，其中 $k$ 是当前不遗忘汉字的数量，因为堆的操作（插入、删除、更新）是对数时间复杂度。
• 总体时间复杂度为 $O(n \log k)$，其中 $n$ 是学习计划的长度，而 $k$ 是汉字种类的数量，最多为 $n$（即每个汉字最多出现一次）。

Python 实现

import heapq

def solve():
    t = int(input())  # 测试数据组数
    for _ in range(t):
        n = int(input())  # 学习计划长度
        a = list(map(int, input().split()))  # 学习计划

        mem = {}  # 存储记忆值
        cnt = {}  # 存储学习次数
        pq = []   # 小根堆
        active = max_active = 0  # 当前活跃和最大活跃汉字数量
        time = 0  # 当前时间步

        for char in a:
            time += 1  # 学习步数

            # 清理已遗忘的汉字
            while pq and pq[0][0] == time:
                d, ch = heapq.heappop(pq)
                if mem.get(ch) == d:
                    del mem[ch]
                    active -= 1

            # 更新当前汉字的记忆值
            k = cnt.get(char, 0) + 1
            nxt = k * k
            if char in mem:
                mem[char] += nxt
            else:
                active += 1
                mem[char] = time + nxt

            cnt[char] = k
            heapq.heappush(pq, (mem[char], char))

            # 更新最大活跃汉字数量
            max_active = max(max_active, active)

        print(max_active)

if __name__ == "__main__":
    solve()

Java 实现

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());  // 测试数据组数
        StringBuilder sb = new StringBuilder();

        // 遍历每组数据
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());  // 学习计划长度
            String[] a = br.readLine().split(" ");   // 学习计划
            
            Map<Integer, Integer> mem = new HashMap<>();  // 存储记忆值
            Map<Integer, Integer> cnt = new HashMap<>();  // 存储学习次数
            PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a1 -> a1[0]));  // 小根堆
            
            int active = 0, maxActive = 0, time = 0;

            // 遍历学习计划
            for (String s : a) {
                int c = Integer.parseInt(s);
                time++;  // 增加学习步数

                // 清理已遗忘的汉字
                while (!pq.isEmpty() && pq.peek()[0] == time) {
                    int[] top = pq.poll();
                    int memVal = top[0], charIndex = top[1];
                    if (mem.getOrDefault(charIndex, -1) == memVal) {
                        mem.remove(charIndex);
                        active--;
                    }
                }

                // 更新当前学习汉字的记忆值
                int k = cnt.getOrDefault(c, 0) + 1;
                int nxt = k * k;
                int newMem;
                if (mem.containsKey(c)) {
                    newMem = mem.get(c) + nxt;
                } else {
                    newMem = time + nxt;
                    active++;
                }

                mem.put(c, newMem);
                cnt.put(c, k);

                // 插入堆中
                pq.offer(new int[]{newMem, c});

                // 更新最大活跃汉字数量
                maxActive = Math.max(maxActive, active);
            }

            sb.append(maxActive).append("\n");
        }

        System.out.print(sb.toString());
    }
}

C++ 实现

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

int main() {
    int t;
    cin >> t;  // 测试数据组数

    while (t--) {
        int n;
        cin >> n;  // 学习计划长度
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];  // 学习计划
        }

        unordered_map<int, int> mem;  // 存储记忆值
        unordered_map<int, int> cnt;  // 存储学习次数
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  // 小根堆
        
        int active = 0, maxActive = 0, time = 0;

        // 遍历学习计划中的每个汉字
        for (int i = 0; i < n; ++i) {
            int c = a[i];
            time++;  // 增加学习步数

            // 清理已遗忘的汉字
            while (!pq.empty() && pq.top().first == time) {
                auto top = pq.top();
                pq.pop();
                int memVal = top.first, charIndex = top.second;
                if (mem[charIndex] == memVal) {
                    mem.erase(charIndex);
                    active--;
                }
            }

            // 更新当前汉字的记忆值
            int k = cnt[c] + 1;
            int nxt = k * k;
            int newMem;
            if (mem.find(c) != mem.end()) {
                newMem = mem[c] + nxt;
            } else {
                newMem = time + nxt;
                active++;
            }

            mem[c] = newMem;
            cnt[c] = k;

            // 插入堆中
            pq.push({newMem, c});

            // 更新最大活跃汉字数量
            maxActive = max(maxActive, active);
        }

        cout << maxActive << endl;
    }

    return 0;
}

题目内容

wida 小朋友快到上学的年纪了，为了帮助他进行识字学习，Tk 设计了一套学习计划。

我们用整数 $a_i$ 表示汉字类别，相同的数字表示同一个汉字。

学习计划为一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$}，Tk 将按照数组顺序依次教给 wida 小朋友。由于 wida 会边学边回看先前学过的汉字记忆，过程具体如下：

• 当某个汉字 $a_i$ 是第 $x$ 次学习这个汉字，且之前未学过或已遗忘，该次学习令其获得 $x^2$ 点学习记忆；

• 当某个汉字 $a_i$ 是第 $x$ 次学习这个汉字，且之前尚未遗忘，该次学习在原有学习记忆上再增加 $x^2$ 点；

在学习每个汉字之前，所有未遗忘汉字的学习记忆均会衰减 $1$ 点；当某个汉字的学习记忆降为 $0$ 时，即视为遗忘(具体可以移步到样例解释)。

请计算 wida 小朋友在整个学习过程中，任意一时刻最多同时掌握(即未遗忘的)不同汉字的数量。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ 代表数据组数；

除此之外，保证单个测试文件中所有 $n$ 之和不超过 $2×10^5$ 。

每组测试数据描述如下：

• 第一行输入一个整数 $n(1 ≦n ≦ 2×10^5)$ ，表示学习计划的长度；

• 第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1 ≦ a_i ≦ n)$ ，表示学习计划中第 $i$ 次学习的汉字编号。

输出描述

对于每一组测试数据，新起一行，输出一个整数，代表 wida 小朋友在所有时刻最多掌握的不同汉字数量。

样例1

输入

2
3
1 2 3
6
1 1 2 2 3 4

输出

1
3

说明

在第一个样例中，$n=3$ 且序列为 {$1,2,3$}，每个汉字仅出现一次，学习后会在下一次学习前遗忘，因此最多同时掌握 $1$ 个汉字。

在第二个样例中，题目将具体解释此样例，对于每一次学习之前以及学习之后数字为 $1$ ~ $4$ 的每个学习记忆。

• 第一个汉字学习前：{$0,0,0,0$} ，第一个汉字学习后学习后：{$1,0,0,0$}

• 第二个汉字学习前：{$0,0,0,0$} ，第二个汉字学习后学习后：{$4,0,0,0$}

• 第三个汉字学习前：{$3,0,0,0$} ，第三个汉字学习后学习后：{$3,1,0,0$}

• 第四个汉字学习前：{$2,0,0,0$} ，第四个汉字学习后学习后：{$2,4,0,0$}

• 第五个汉字学习前：{$1,3,0,0$} ，第五个汉字学习后学习后：{$1,3,1,0$}

• 第六个汉字学习前：{$0,2,0,0$} ，第六个汉字学习后学习后：{$0,2,0,1$}

即学完第五个汉字后 wida 小朋友同时掌握的汉字最多，$3$ 个。