题解：历史研究

一、题目分析

本题给定记录了(N)天事件的日记，每个事件有对应的种类。需要处理(Q)次询问，每次询问一个区间，要求计算该区间内所有事件种类的重要度（事件种类(t)的重要度为(t×)该区间内重要度为(t)的事件数），并输出其中的最大值。

二、解题思路

本题采用分块算法结合莫队算法的思想来解决。先对数据进行离散化处理，然后将询问区间排序，通过双指针在区间上移动计算每个询问的答案。

（一）数据结构与变量定义

typedef long long LL;
const int N = 100010;
int n, m, len;
int w[N], cnt[N];
LL ans[N];
struct Query
{
    int id, l, r;
}q[N];
vector<int> nums;

• LL：定义长整型别名，用于处理较大的数值。
• N：定义日记记录天数和询问数量的最大值。
• n：存储日记记录的实际天数。
• m：存储询问的数量。
• len：存储分块的长度。
• w[N]：数组，用于存储每天事件的种类编号。
• cnt[N]：数组，用于记录每种事件种类在当前区间内出现的次数。
• ans[N]：数组，用于存储每个询问的答案。
• Query结构体：用于存储每个询问的信息，包括询问的编号id，区间左端点l和右端点r。
• nums：向量，用于存储需要离散化处理的事件种类数值。

（二）辅助函数

1. 获取元素所属块的编号函数get：

int get(int x)
{
    return x / len;
}

根据元素的下标x，返回其所属块的编号。

1. 询问排序比较函数cmp：

bool cmp(const Query& a, const Query& b)
{
    int i = get(a.l), j = get(b.l);
    if (i != j) return i < j;
    return a.r < b.r;
}

用于对询问进行排序。先按区间左端点所属块的编号排序，若块编号相同，则按区间右端点排序。

（三）区间元素添加函数add

void add(int x, LL& res)
{
    cnt[x] ++ ;
    res = max(res, (LL)cnt[x] * nums[x]);
}

在当前区间添加一个事件种类为x的事件。增加该事件种类的出现次数，并更新当前区间内重要度的最大值res（通过事件种类数值和出现次数计算重要度）。

（四）主函数main

int main()
{
    scanf("%d%d", &n, &m);
    len = sqrt(n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]), nums.push_back(w[i]);
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    for (int i = 1; i <= n; i ++ )
        w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin();

    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {i, l, r};
    }
    sort(q, q + m, cmp);

    for (int x = 0; x < m;)
    {
        int y = x;
        while (y < m && get(q[y].l) == get(q[x].l)) y ++ ;
        int right = get(q[x].l) * len + len - 1;

        // 暴力求块内的询问
        while (x < y && q[x].r <= right)
        {
            LL res = 0;
            int id = q[x].id, l = q[x].l, r = q[x].r;
            for (int k = l; k <= r; k ++ ) add(w[k], res);
            ans[id] = res;
            for (int k = l; k <= r; k ++ ) cnt[w[k]] -- ;
            x ++ ;
        }

        // 求块外的询问
        LL res = 0;
        int i = right, j = right + 1;
        while (x < y)
        {
            int id = q[x].id, l = q[x].l, r = q[x].r;
            while (i < r) add(w[ ++ i], res);
            LL backup = res;
            while (j > l) add(w[ -- j], res);
            ans[id] = res;
            while (j < right + 1) cnt[w[j ++ ]] -- ;
            res = backup;
            x ++ ;
        }
        memset(cnt, 0, sizeof cnt);
    }

    for (int i = 0; i < m; i ++ ) printf("%lld\n", ans[i]);
    return 0;
}

1. 读取日记记录天数n和询问数量m，计算分块的长度len。读取每天事件的种类编号，将其存入nums向量用于离散化处理。对nums进行排序和去重，然后将w数组中的事件种类编号离散化。
2. 读取每个询问的区间，将询问信息存储到q数组中。
3. 对询问按照cmp函数定义的规则进行排序。
4. 处理询问：
   • 按左端点所属块分组，对于同一块内且右端点也在块内的询问，直接暴力计算答案，计算完后将区间内事件种类的计数恢复。
   • 对于块外的询问，使用双指针i和j，先移动i指针扩展区间计算部分答案，记录下来；再移动j指针进一步扩展区间更新答案，最后恢复j指针移动过程中增加的计数，并恢复答案变量res。处理完一组询问后，清空cnt数组。
5. 输出每个询问的答案。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 初始化操作：读取数据、离散化处理，时间复杂度为(O(n\log n))。
• 排序操作：对询问进行排序，时间复杂度为(O(m\log m))。
• 处理询问操作：分块处理询问，块内暴力计算和块外双指针移动，时间复杂度为(O(m\sqrt{n}))。
• 总的时间复杂度为(O(n\log n + m\log m + m\sqrt{n}))，近似为(O(m\sqrt{n}))（当n和m规模相近时）。

（二）空间复杂度

需要存储事件种类编号w[N]、询问信息q[N]、事件种类计数数组cnt[N]、答案数组ans[N]以及离散化用的nums向量，空间复杂度为(O(N + N + N + N + N)=O(N)) 。