[ 莫队 哈夫曼树 ] Codeforces700D Huffman Coding on Segment

莫队。每次询问不断将值小于 n−−√ n 的合并，剩下的用构建哈夫曼树的方法来做就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=;
struct Node{
  int l,r,id;
}c[N];
int k,n,m,S,L=,R;
int a[N],b[N];
int cnt[N],s[N],sum[N];
bool v[N];
ll Ans[N];
vector<int>g;
inline bool Cmp(Node x,Node y){
  return b[x.l]<b[y.l]||(b[x.l]==b[y.l]&&x.r<y.r);
}
inline void Update(int x,int y){
  sum[cnt[x]]--;
  cnt[x]+=y;
  sum[cnt[x]]++;
}
inline ll Calc(){
  ll Ans=;
  priority_queue<int,vector<int>,greater<int> >Q;
  for(int i=;i<g.size();i++)
    if(cnt[g[i]]>S)Q.push(cnt[g[i]]);
  int lst=;
  for(int i=;i<=S;i++)s[i]=sum[i];
  for(int i=;i<=S;i++)
    if(s[i]){
      if(lst){
                Ans+=i+lst;
                if(i+lst<=S)s[i+lst]++;else Q.push(i+lst);
                s[i]--;lst=;
      }
      if(s[i]&)lst=i;
      Ans+=l*(s[i]>>)*(i<<);
      if((i<<)<=S)s[i<<]+=s[i]>>;else
                for(int j=;j<=(s[i]>>);j++)Q.push(i<<);
    }
    if(lst)Q.push(lst);
  while(Q.size()>){
    int x=Q.top();Q.pop();
    x+=Q.top();Q.pop();
    Ans+=x;Q.push(x);
  }
  return Ans;
}
int main(){
  scanf("%d",&n);
  for(int i=;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++;
  scanf("%d",&m);
  for(int i=;i<=m;i++)scanf("%d%d",&c[i].l,&c[i].r),c[i].id=i;
  S=sqrt(n);
  for(int i=;i<=n;i++)
    if(cnt[a[i]]>S&&!v[a[i]])
      g.push_back(a[i]),v[a[i]]=;
  memset(cnt,,sizeof(cnt));
  for(int i=;i<=n;i++)b[i]=(i-)/S+;
  sort(c+,c+m+,Cmp);
  for(int i=;i<=m;i++){
    while(R<c[i].r)Update(a[++R],);
    while(R>c[i].r)Update(a[R--],-);
    while(L>c[i].l)Update(a[--L],);
    while(L<c[i].l)Update(a[L++],-);
    Ans[c[i].id]=Calc();
  }
  for(int i=;i<=m;i++)printf("%I64d\n",Ans[i]);
  return ;
}