题解：P11398 众数

· · 题解

可以说真的是一道不错的题。

我的做法是“分块”。

由于 n^2 以上做法太简单，就不写了，直接从 O(n\sqrt n) 开始。

O((n+m+\sum k)\sqrt n) 做法

会的可以直接跳过。

这其实就是静态区间众数。主要思路是将原序列分成 k 块，我们维护每个数在前 i 个块中出现的次数，进而维护前 i 个块的众数。

构建时，考虑到前 i+1 个块的众数必然为前 i 个块的众数，或者第 i 个块中出现过的数，共 O(\sqrt n) 个不同的值。

修改时，只需要修改后面的块。

注意，修改和构建时维护的所有信息只需要每个块的。

查询时类似，这里只需要查前 i 个块带上不超过 O(\sqrt n) 个零散的元素。

这里的 \sum k\le 5\times 10^7，显然就是查询次数，但是 k\sqrt n 显然会超时，需要把它优化掉。

O(\sum k+(n+m)\sqrt n) 做法

在查询的时候，由于右端点是一段区间，显然一个块中的答案可以在块长的时间内求出来。

但是这样仍然会超时。

O(\sum k+(n+m)\log n) 做法

增加块长时修改操作会变快，但是查询中浪费的就会变多。但是又因为查询是最右边一段连续的区间。因此可以将块长设置得不一样，具体地，如果从右往左块长依次为 1,2,4,8,\cdots，则总共只有 \log n 个块。又不妨假设所有询问答案都是 k_0，则总共需要查询不超过 \frac{\sum k}{k_0} 次，且每次浪费的询问也不会超过 2^{\log k_0}=k_0 个，总共查询复杂度即为 O(\sum k)。

代码

#include<cstdio>
#include<utility>
#include<algorithm>
#include<math.h>
#define int long long
int t,n,m,b[400005];
int a[400005];
long long d[400005][19];
long long app[400005];
std::pair<long long,int>zhong[400000],ans[400005];
int kuail[19],kuair[19],kuainum=19;
void run(){
    long long q;
    scanf("%lld",&q);
    for(int i=kuainum-1;~i;i--){
        ans[kuair[i-1]]=zhong[i-1];
        for(int j=kuail[i];j<=kuair[i];j++)app[b[j]]=d[b[j]][i-1];
        for(int j=kuail[i];j<=kuair[i];j++){
            ans[j]=ans[j-1];
            app[b[j]]+=a[j];
            if(app[b[j]]>ans[j].first||(app[b[j]]==ans[j].first&&b[j]>ans[j].second))ans[j]={app[b[j]],b[j]};
        }
        for(int j=kuail[i];j<=kuair[i];j++)app[b[j]]=0;
        for(int j=kuair[i];j>=kuail[i];j--){
            q^=(1ll*a[j]*ans[j].second);
            if(!q){
            printf("%lld\n",n-j+1);
            return;
            }
        }
    }
}
signed main(){
    scanf("%lld%lld%lld",&t,&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]);
    kuainum=log2(n);
    for(int i=kuainum-1;~i;i--){
        if(kuainum==i+1)kuair[i]=n;
        else kuair[i]=kuail[i+1]-1;
        if(!i)kuail[i]=1;
        else kuail[i]=kuair[i]-(1<<(kuainum-i-1));
    }
    for(int i=0;i<kuainum;i++){
        for(int j=1;j<=n;j++)d[j][i]=d[j][i-1];
        for(int j=kuail[i];j<=kuair[i];j++)d[b[j]][i]+=a[j];
        zhong[i]=zhong[i-1];
        for(int j=kuail[i];j<=kuair[i]&&j<=n;j++)if(d[b[j]][i]>zhong[i].first||(d[b[j]][i]==zhong[i].first&&b[j]>zhong[i].second))zhong[i]={d[b[j]][i],b[j]};
    }
    while(m--){
        int op,x,y;
        scanf("%lld",&op);
        if(op==2)run();
        else{
            scanf("%lld%lld",&x,&y);
            a[x]+=y;
            for(int i=0;i<kuainum;i++){
                if(kuair[i]>=x)d[b[x]][i]+=y;
                if(d[b[x]][i]>zhong[i].first||(d[b[x]][i]==zhong[i].first&&b[x]>zhong[i].second))zhong[i]={d[b[x]][i],b[x]};
            }
        }
    }
}