题解 P2442 【分数统计】

s_r_f · 2020-04-26 18:08:35 · 题解

感觉这个题卡空间没什么用（雾

查询的是区间average,max,min,众数,但是数只有100种取值.

一种想法是考虑对100种取值做前缀和,然后每组询问O(q*100)来做,但需要O(n*100)的空间.

那么我们就每S个数分一块,然后维护块之间的前缀和,边角暴力即可.

时间复杂度O(\frac{n}{S}*100 +q*max(100+2S))

空间复杂度O(\frac{n}{S}*100).

令S = 40,此时空间可看做线性,时间仍然为O(q*100).

代码:

#include <bits/stdc++.h>
#define LL long long
using namespace std;
template <typename T> void read(T &x){
    static char ch; x = 0,ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
const int N = 200005,S = 40;
int n,m,a[N],b[N],cur[N],cl[N],cr[N],prea[N],preb[N],cnt[101][N/S+5],now[101];
int main(){
    register int i,j; int op,l,r,curl,curr,ans,mx,mn; ios::sync_with_stdio(0);
    read(n),read(m);
    for (i = 1; i <= n; ++i) read(a[i]);
    for (i = 1; i <= n; ++i) cur[i] = (i-1)/S+1,read(b[i]),prea[i] = prea[i-1] + a[i] * b[i],preb[i] = preb[i-1] + b[i];
    for (i = 1; i <= cur[n]; ++i){
        cl[i] = S*(i-1)+1,cr[i] = min(n,S*i);
        for (j = 1; j <= 100; ++j) cnt[j][i] = cnt[j][i-1];
        for (j = cl[i]; j <= cr[i]; ++j) cnt[a[j]][i] += b[j]; 
    }
    while (m--){
        read(op),read(l),read(r);
        if (op==1){ cout << fixed << setprecision(2) << ((double)(prea[r]-prea[l-1])) / (preb[r]-preb[l-1]) << '\n'; continue; }
        memset(now,0,sizeof(now));
        curl = cur[l],curr = cur[r];
        if (curl + 1 >= curr) for (i = l; i <= r; ++i) now[a[i]] += b[i];
        else{
            for (i = l; i <= cr[curl]; ++i) now[a[i]] += b[i];
            for (i = cl[curr]; i <= r; ++i) now[a[i]] += b[i];
            for (i = 1; i <= 100; ++i) now[i] += cnt[i][curr-1] - cnt[i][curl];
        }
        if (op==2) for (ans = 1,i = 2; i <= 100; ++i) if (now[i] > now[ans]) ans = i;
        if (op==3){
            for (i = 1; i <= 100; ++i) if (now[i]){ mn = i; break; }
            for (i = 100; i ; --i) if (now[i]){ mx = i; break; }
            ans = mx-mn;
        }
        cout << ans << '\n';
    }
    return 0;
}