Codeforces 700D. Huffman Coding on Segment(哈夫曼树+莫队+set)

Author Avatar
Sakits 6月 01, 2018

题解

  这题感觉写优先队列很烦,于是我写了个set…一开始T飞了,后来发现自己没改块大小,改成10n\sqrt{10n}就过了233

  之前写过几道哈夫曼树的题,但是都忘得差不多了,今天看见这个题想了好久都不会,智商--,只好顺便复习一下QAQ

  哈夫曼编码就是把每种字符都映射成一个二进制数,使得每个字符映射的数都不是其他字符映射的数的前缀,并且使得最后编码出来的字符串总长度最短。

  先构造出哈夫曼树,具体构造方法就是每次选出两个权值最小的数(哈夫曼编码中这个权值为某个字符的出现次数),然后新建一个节点连向这两个节点,权值为两个字符出现次数和,这样一直取到只剩下一个节点。

  哈夫曼树上的每个叶子代表每个字符,而某个字符的哈夫曼编码就是根到它的路径上,连向左儿子的边为00,右儿子的边为11连成的二进制数。显然每个字符的长度和就是它的总出现次数乘到根的距离,因为字符是叶子,所以肯定不会有某个字符的哈夫曼编码是其他字符的前缀。感性理解一下这样之所以是对的是因为出现次数少的字符长度尽量长,所以总长度会尽量短。

  要构造出哈夫曼编码我们需要知道每种数字的出现次数,但是正常一次构造的时间复杂度是O(O(字符集大小))的,显然无法承受。但是我们可以发现一个性质:并不会有很多种出现次数,因为序列总长只有nn。所以我们可以统计出某个出现次数有多少种数,这个用莫队就可以做到了。那么对于出现次数n\leq \sqrt{n}的数,直接暴力计算即可,对于>n>\sqrt{n}的,不会超过n\sqrt{n}个,用堆计算即可,我偷懒用了set。

  总时间复杂度O(nnlogn)O(n\sqrt{n}logn)

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm>
#include<set>
#include<cassert>
#define ll long long 
#define ddq multiset<int>::iterator
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int l, r, pos;}q[maxn];
int n, m, blo;
multiset<int>s, s1;
int cnt[maxn], a[maxn], bl[maxn], pos[maxn], tmppos[maxn], ans[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

bool operator < (poi a, poi b)
{return bl[a.l]<bl[b.l] || (bl[a.l]==bl[b.l] && ((bl[a.l]&1)?a.r<b.r:a.r>b.r));}

inline void update(int x, int delta)
{
	pos[cnt[a[x]]]--;
	if(1ll*cnt[a[x]]*cnt[a[x]]>1000000) s.erase(s.find(cnt[a[x]]));
	cnt[a[x]]+=delta;
	pos[cnt[a[x]]]++;
	if(1ll*cnt[a[x]]*cnt[a[x]]>1000000) s.insert(cnt[a[x]]);
}

inline ll query()
{
	int last=0; ll ans=0; s1=s;
	for(int i=1;i*i<=1000000;i++) tmppos[i]=pos[i];
	for(int i=1;i*i<=1000000;i++)
	if(pos[i])
	{
		if(last) 
		{
			if(1ll*(i+last)*(i+last)>1000000) s1.insert(i+last);
			pos[i+last]++; pos[i]--; pos[last]--; ans+=i+last;
		}
		if(1ll*(i+i)*(i+i)>1000000)
		for(int j=1;j<=(pos[i]>>1);j++) s1.insert(i+i);
		pos[i+i]+=pos[i]>>1; ans+=1ll*i*(pos[i]-(pos[i]&1));
		pos[i]&=1; last=pos[i]?i:0;
	}
	for(int i=1;i*i<=1000000;i++) pos[i]=tmppos[i];
	if(last) s1.insert(last); 
	while(s1.size()>1)
	{
		ddq it2=s1.begin(), it1=it2++;
		int tmp=*it1+*it2; ans+=tmp;
		s1.erase(s1.begin()); s1.erase(s1.begin());
		s1.insert(tmp);
	}
	return ans;
}

int main()
{
	read(n); blo=sqrt(n);
	for(int i=1;i<=n;i++) read(a[i]), bl[i]=(i-1)/blo+1;
	read(m);
	for(int i=1;i<=m;i++) read(q[i].l), read(q[i].r), q[i].pos=i;
	sort(q+1, q+1+m);
	for(int i=1, l=1, r=0;i<=m;i++)
	{
		while(l<q[i].l) update(l++, -1);
		while(l>q[i].l) update(--l, 1);
		while(r<q[i].r) update(++r, 1);
		while(r>q[i].r) update(r--, -1);
		ans[q[i].pos]=query();
	}
	for(int i=1;i<=m;i++) printf("%d\n", ans[i]); 
}