Codeforces

Luogu

分析

考虑莫队，维护区间内每个数的出现次数，然后询问时建一棵 Huffman 树即可。然而暴力建树是 $\mathcal{O}(n)$ 的，显然过不了。

考虑根号分治，并维护出现次数为 $i$ 的数的个数，这样子对于出现次数 $\leq B$ 的数，可以直接 $\mathcal{O}(B)$ 扫一遍合并；对于出现次数 $>B$ 的数，显然只有 $\frac{n}{B}$ 个，可以用堆暴力合并。取 $B=\sqrt{n}$ 时复杂度为 $\mathcal{O}(n\sqrt{n}\log n)$。

实现有一些细节。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,B=317;

int n,m,a[N],ans[N];
vector<int> v;
struct query { int l,r,id; } q[N];
bool operator <(query a,query b) {
    if (a.l/B!=b.l/B) return a.l<b.l;
    else return (a.l/B)&1?a.r<b.r:a.r>b.r;
}

int o[N],cnt[N],tmp[N];
void add(int x) { --cnt[o[x]],++o[x],++cnt[o[x]]; }
void del(int x) { --cnt[o[x]],--o[x],++cnt[o[x]]; }

priority_queue<int,vector<int>,greater<int> > Q;
int Huffman() {
    for (int i:v) if (o[i]>B) Q.push(o[i]);
    for (int i=1;i<=B;++i) tmp[i]=cnt[i];
    int ans=0,j=0;
    for (int i=1;i<=B;++i) {
        if (!tmp[i]) continue;
        if (j) {
            --tmp[i],ans+=i+j;
            if (i+j>B) Q.push(i+j);
            else ++tmp[i+j];
            j=0;
        }
        if (tmp[i]&1) j=i,--tmp[i];
        ans+=tmp[i]*i;
        if ((i<<1)>B)
            for (int j=1;j<=tmp[i]>>1;++j) Q.push(i<<1);
        else tmp[i<<1]+=tmp[i]>>1;
    }
    if (j) Q.push(j);
    while (!Q.empty()) {
        int x=Q.top(); Q.pop();
        if (Q.empty()) break;
        int y=Q.top(); Q.pop();
        ans+=x+y,Q.push(x+y);
    }
    return ans;
}

int main() {
    n=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=n;++i) ++o[a[i]];
    for (int i=1;i<=100000;++i) if (o[i]>B) v.emplace_back(i);
    memset(o,0,sizeof(o));
    m=read();
    for (int i=1;i<=m;++i) q[i]=(query){read(),read(),i};
    sort(q+1,q+m+1);
    for (int i=1,l=1,r=0;i<=m;++i) {
        while (l>q[i].l) --l,add(a[l]);
        while (r<q[i].r) ++r,add(a[r]);
        while (l<q[i].l) del(a[l]),++l;
        while (r>q[i].r) del(a[r]),--r;
        ans[q[i].id]=Huffman();
    }
    for (int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}