题目概述

给出 $n$ 个数和 $m$ 个询问，每次询问给 $[L,R]$ 中的数进行哈夫曼编码得到的长度总和。

解题报告

挺强的题，给 $[L,R]$ 中的数进行哈夫曼编码，数据结构肯定搞不了，所以考虑奇技淫巧：莫队。

用莫队我们可以得出所有数的出现情况，但是还是没有什么好方法建哈夫曼树。

其实建哈夫曼树除了优先队列还可以直接在权值数组上搞，考虑优先队列的复杂度取决于权值个数，而在权值数组上处理的复杂度取决于权值大小，然后我们就发现了什么不得了的事情：可以阈值优化。权值小于等于 $\sqrt n$ 的元素直接在权值数组上做，而权值大于 $\sqrt n$ 的元素丢进优先队列就好了，注意权值数组在合并时会产生 $>\sqrt n$ 的元素，也要丢进优先队列。因为不管怎么样优先队列里的和是小于 $n$ 的所以元素个数小于 $\sqrt n$ 。

示例程序

发现了个神坑……我莫队排序的时候采用了一种上升下降交错的方式（据法老说可以减小常数），但是应该使用三目的(a.X/S&1)?a.Y<b.Y:a.Y>b.Y写成了(a.X/S&1)^(a.Y<b.Y)使得sort因为优先级不明确而爆炸。

调了一下午换来了这个结论我真的是……LKDFJSDUB%^D&$&%S^DNSDNJ

#include<cstdio>
#include<algorithm>
#define X first.first
#define Y first.second
#define ID second
using namespace std;
typedef long long LL;typedef pair<pair<int,int>,int> data;
const int maxn=100000,maxq=100000,maxa=100000,S=317;

int n,m,a[maxn+5],A[maxn+5];data q[maxq+5];LL ans[maxq+5];
int cnt[maxa+5],ha[maxn+5],tem[maxn+5],si,Heap[maxn+5];

inline bool cmp(const data &a,const data &b) {return a.X/S<b.X/S||a.X/S==b.X/S&&((a.X/S&1)?a.Y<b.Y:a.Y>b.Y);}
inline void Insert(int x) {ha[cnt[x]]--;cnt[x]++;ha[cnt[x]]++;}
inline void Delete(int x) {ha[cnt[x]]--;cnt[x]--;ha[cnt[x]]++;}
inline bool Hcmp(const int &a,const int &b) {return a>b;}
#define Push(x) (Heap[++si]=(x),push_heap(Heap+1,Heap+1+si,Hcmp))
#define Pop() (pop_heap(Heap+1,Heap+1+si--,Hcmp))
inline LL Huffman(LL &ans){
    si=0;for (int i=1;i<=A[0];i++) if (cnt[A[i]]>S) Push(cnt[A[i]]);
    for (int i=1;i<=S;i++) tem[i]=ha[i];
    for (int i=1,lst=1;i<=S;i++)
        while (tem[i]){
            while (!tem[lst]) lst++;int sum=i+lst,num=(i==lst?tem[i]>>1:min(tem[i],tem[lst]));
            if (sum>S) for (int t=1;t<=num;t++) Push(sum); else tem[sum]+=num;
            ans+=(LL)num*sum;tem[i]-=num;tem[lst]-=num;if (i==lst) break;
        }
    for (int i=1;i<=S;i++) if (tem[i]) Push(i);
    while (si>1) {int A=Heap[1];Pop();int B=Heap[1];Pop();ans+=A+B;Push(A+B);}
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]),cnt[a[i]]++==S?A[++A[0]]=a[i]:0;
    scanf("%d",&m);for (int i=1;i<=m;i++) scanf("%d%d",&q[i].X,&q[i].Y),q[i].ID=i;
    sort(q+1,q+1+m,cmp);for (int i=1;i<=n;i++) cnt[a[i]]=0;
    for (int i=1,L=1,R=0;i<=m;Huffman(ans[q[i++].ID])){
        while (L>q[i].X) Insert(a[--L]);while (L<q[i].X) Delete(a[L++]);
        while (R<q[i].Y) Insert(a[++R]);while (R>q[i].Y) Delete(a[R--]);
    }for (int i=1;i<=m;i++) printf("%lld\n",ans[i]);return 0;
}