题解：P11398 众数

· · 题解

D. 众数 官方题解

本题涉及的主要知识点：

测试点 1\sim 9

要算出众数，关键就是要统计每个数字出现的次数。1 操作正常修改（直接增加 a_i 即可），当碰到 2 操作时，开一组计数器，用一重 for 循环从前往后枚举 i，将第 i 个数组中的数加入计数器，并同时维护此时的最大众数。

知道前 i 个数组的众数后，再用另一重循环从后往前扫描并统计 n-k+1\sim n 的权值异或和。该方法时间复杂度为 O(nm)。

对于测试点 8,9，既然所有数组都不发生变化，那么第一次把所有前缀众数求好就一劳永逸了，时间复杂度 O(n+\sum k)。

测试点 10\sim 15

当 b_i=1 时，众数显然永远是 1，相当于你需要维护单点修改后缀异或和，在从小到大枚举 k 的时候顺带维护一下就可以。

当 b_i\le 2 时，你需要知道前缀中 1,2 分别有几个。因为在用循环枚举 k 的时候你可以确保当前结点的后缀都是被扫描过的，所以前缀中 1,2 的个数等于全局 1,2 的个数减去后缀中对应的个数。

本节中这句话以下的内容并不是 J 组需要掌握的，也不是做出这题所必需的。

当 b_i 更大时，你可以使用任何一种支持单点减小全局求 \max 的数据结构维护，如线段树、带时间戳的优先队列、multiset 等，代价是往前挪一步的时间复杂度变成 \log n——或者说 \log \max b_i。

因此本题的总时间复杂度为 O((n+m+\sum k)\log \max b_i)。

测试点 13\sim 15 还有另解（根号分治）。在测试点 16\sim 19 做法的基础上，如果 k\le B=300 时无解，我就以 O(n) 的代价从头跑一遍（B 需要略微调整，但我没写过）。显然从头跑一遍的次数不超过 \dfrac{\sum k}{B} 次，所以总时间复杂度为 O(n+mB+\dfrac{n\sum k}{B})，根据基本不等式，最小时间复杂度为 O(n+\sqrt{nm\sum k})。

测试点 16\sim 19

（这是本题最具有提示性的部分分）

注意到 k 减小是很容易的，但增大是很困难的。因为 k\le 300，所以无论如何，前 n-300 个数组肯定永远都是要参与计算区间众数的。为此我们设置一个计数器记录前 n-300 个数组中每个数出现了几次以及此时的区间众数，然后让 k 从 300 逐渐减少到 1。时间复杂度 O(n+m\max k)。

正解

现在 k 范围不确定，我们能不能设置一些递推起点（在测试点 17\sim 20 中是 n-300），使得不管 k 是多少，都有一个离它不太远的递推起点呢？

答案是肯定的。注意到 k 及以上的、最小的 2 的整数次幂不超过 2k，换言之，如果我们以 n-2^i 作为递推起点，就可以保证存在一个递推起点，从它递推到 k 所需的次数不超过 k。

具体要怎么做呢？考虑如下流程：

因为现在有 \log n 个递推起点需要统计每个数出现次数，所以每次 1 操作的时间复杂度会提升为 O(\log n)。这样总时间复杂度就是 O((n+m)\log n+\sum k)。

本节中这句话以下的内容并不是 J 组需要掌握的，也不是做出这题所必需的。

如果你学过分块，你或许会发现（因为我没亲自写过），似乎不用倍增法设置起点也能把这题做出来。

具体地，如果你每 \sqrt n 个数组设置一个递推起点，那么每次 2 操作最多花费 k+\sqrt n 次递推就可以得出结果，然后 1 操作时间复杂度为 O(\sqrt n)，总时间复杂度为 O((n+m)\sqrt n+\sum k)，也能通过。

我自己用根号一段的方法没有 A 掉本题，我不太清楚选手有没有根号干过去的。

#include<bits/stdc++.h>
using namespace std;
int T,n,m;
int a[300005],b[300005];
vector<int> stt;
long long cnt[20][300005],best[20],v[300005];
bool x_gr_y(int x,int y,int j){return cnt[j][x]>cnt[j][y] || (cnt[j][x]==cnt[j][y] && x>y);}
int main(){
    scanf("%d%d%d",&T,&n,&m);
    for(int j=0;(1<<j)<=n;j++)stt.emplace_back(n+1-(1<<j));
    stt.emplace_back(1);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
    for(int j=0;j<stt.size();j++)
        for(int i=1;i<stt[j];i++){
            cnt[j][b[i]]+=a[i];
            if(x_gr_y(b[i],best[j],j))
                best[j]=b[i];
        }
    for(;m;m--){
        int op,x,y;
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d",&x,&y);
            a[x]+=y;
            for(int j=0;j<stt.size();j++)
                if(x<stt[j]){
                    cnt[j][b[x]]+=y;
                    if(x_gr_y(b[x],best[j],j))
                        best[j]=b[x];
                }
        }
        else{
            long long q;
            scanf("%lld",&q);
            int last=n+1,answer=-1;
            for(int j=0;j<stt.size();j++){
                long long bst=best[j];
                for(int i=stt[j];i<last;i++){
                    cnt[j][b[i]]+=a[i];
                    if(x_gr_y(b[i],bst,j))
                        bst=b[i];
                    v[i]=bst*a[i];
                }
                for(int i=last-1;i>=stt[j];i--){
                    q^=v[i];
                    if(q==0 && answer<0)answer=i;
                    cnt[j][b[i]]-=a[i];
                }
                if(answer>=0){
                    printf("%d\n",n+1-answer);
                    break;
                }
                else
                    last=stt[j];
            }
        }
    }
    return 0;
}

Further More

出这道题，主要就是发现考纲里有个“倍增法”，然后回顾了脑海当中所有关于“倍增”的内容。

本题最开始是想丢到基础赛的，所以出题受到知识点的限制，能维护的量非常有限，我枚举了好几天才找到了符合需求的一些操作。

在成功出出来这道题之前，我曾经有过很多个不同尝试，下面列举一些：

总结：线段树，太强大。