题解：P2442 分数统计

· · 题解

看了一圈，普遍使用了一些入门新手不一定会掌握的数据结构，而我的写法用到的唯一的数据结构是数组，唯二的技巧是离线询问以及前缀和差分，希望能帮到也许不那么擅长数据结构的你。

题目需要我们求：

对于区间均值，我们求出区间分数之和，以及区间人数，然后两者相除就能得到答案。区间分数之和以及区间人数都可以用前缀和维护，差分快速求得。

对于区间众数，如果分数的取值范围不那么小，一般要考虑回滚莫队或者分块预处理。但由于分数取值范围很小，我们可以枚举所有分数，同样利用前缀和的差分来快速求出这个分数在区间中的人数，取人数最大者即可，人数相同则取分数最小的。

对于区间极差，处理方式和区间众数区别不大，枚举所有分数，用前缀和维护，差分查询区间内分数对应的人数，对于人数不为零的分数，求出区间内第一次出现的，以及最后出现的，就是区间中最小和最大的分数。

接下来注意到空间限制得很小，导致我们不能提前预处理出所有分数的前缀和数组。但我们可以存下所有第二类和第三类询问，然后枚举所有分数，求出分数对应的人数前缀数组再进行求解。这题唯一的难点就在这里，需要有一点离线思维。说白了就是如果在线，就是枚举每个询问，再枚举每个分数；现在离线询问，就是先枚举每个分数，再枚举每个询问，也就是每个询问的求解过程都被拆开了。

时间复杂度 O(mn)，空间复杂度 O(n)，其中 m 是分数的取值范围。

看看代码以及里面的注释吧：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
    ll s=0,t=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')t*=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        s=(s<<1)+(s<<3)+c-'0';
        c=getchar();
    }
    return s*t;
}
ll n,m;
ll pre[200005];
ll a[200005],b[200005];
ll c[200005],d[200005];
ll answer[200005];
ll type[200005];
struct kkk
{
    ll no,tp,l,r,x,y;//问题编号、问题种类、问题范围（左和右）、用于记录的两个变量
    kkk(){}
    kkk(ll a,ll b,ll c,ll d)
    {
        no=a;
        tp=b;
        l=c;
        r=d;
        x=0;
        y=0;
    }
};
vector<kkk>Q;
int main()
{
    n=read();
    m=read();
    for(ll i=1;i<=n;i++)a[i]=read();
    for(ll i=1;i<=n;i++)b[i]=read();
    for(ll i=1;i<=n;i++)
    {
        d[i]=d[i-1]+b[i];//记录前缀人数
        c[i]=c[i-1]+a[i]*b[i]*100;//记录前缀总分的一百倍，方便后续输出
    }
    for(ll i=1;i<=m;i++)
    {
        ll op,l,r;
        op=read();
        type[i]=op;
        l=read();
        r=read();
        if(op==1)
        {
            answer[i]=(1.0*(c[r]-c[l-1])/(d[r]-d[l-1]))+0.5;
        }
        if(op==2)
        {
            Q.push_back(kkk(i,2,l,r));//存下询问
        }
        if(op==3)
        {
            Q.push_back(kkk(i,3,l,r));//存下询问
        }
    }
    for(ll j=1;j<=100;j++)//单独处理每种分数
    {
        memset(pre,0,sizeof(pre));
        for(ll i=1;i<=n;i++)
        {
            pre[i]=pre[i-1]+(a[i]==j?b[i]:0);//计算人数的前缀
        }
        for(auto &now:Q)
        {
            if(now.tp==2)
            {
                if(pre[now.r]-pre[now.l-1]>now.y)//找出众数，用 x 记录众数，y 记录众数对应人数
                //注意要用大于号，而不是大于或等于号，因为出现次数相同时取较小者
                {
                    now.x=j;//发现人数更大的分数了，替换之
                    now.y=pre[now.r]-pre[now.l-1];
                }
            }
            else
            {
                if(pre[now.r]-pre[now.l-1]>0)
                {
                    //找出出现过的数中最小和最大的
                    if(now.x==0)now.x=j;//只记录第一次出现的分数，也就是最小的分数
                    now.y=j;//每个新出现的分数都会替代，也就是找出最大的分数
                }
            }
        }
    }
    for(auto now:Q)
    {
        if(now.tp==2)answer[now.no]=now.x;
        else answer[now.no]=now.y-now.x;//计算极差
    }
    for(ll i=1;i<=m;i++)
    {
        if(type[i]==1)
        {
            printf("%.2lf\n",1.0*answer[i]/100);
        }
        else printf("%lld\n",answer[i]);
    }
}