【莫队算法】【权值分块】bzoj3920 Yuuna的礼物

【算法一】

暴力。

可以通过第0、1号测试点。

预计得分：20分。

【算法二】

经典问题：区间众数，数据范围也不是很大，因此我们可以：

①分块，离散化，预处理出：

<1>前i块中x出现的次数(差分)；

<2>第i块到第j块中的众数是谁，出现了多少次。

询问的时候，对于整块的部分直接获得答案；对于零散的部分，暴力统计每个数出现 的次数，加上差分的结果，尝试更新ans。

时间复杂度O(m*sqrt(n))，

空间复杂度O(n*sqrt(n))。

②考虑离线，莫队算法，转移的时候使用数据结构维护，具体实现不赘述。

时间复杂度O(m*sqrt(n)*log(n))，

空间复杂度O(n)。

结合算法一，预计得分：40分。

【算法三】

考虑离线，莫队算法，存储一个数组，记录权值的出现次数，然后我们把这些次数插 入到一个权值分块(即一种对权值分块的数据结构，特点是支持O(1)的插入删除和O(sqrt(n))的查询全局k大、全局排名、前驱、后继之类，因此可以良好地与莫队算法结合起来解决无修改的区间询问)里，如果仅仅需要知道众数出现的次数而已，我们就可以O(1)地实现转移，并且O(sqrt(n))地实现询问了。但是我们还需要知道k2小值，所以在权值分块的每个结点维护一棵平衡树，插入的时间复杂度就变高了。

时间复杂度O(m*sqrt(n)*log(n)(插入、删除)+m*sqrt(n)(查询))

空间复杂度O(n)。

可以通过0、1、2(?)、3(?)、4、5号测试点。

预计得分：40分~60分，结合算法二一定可以得到60分，可能需要常数优化。

【算法四】

我们发现算法三的主要问题在于插入到平衡树里是O(logn)的，因此如果我们把平衡树换成权值分块，就可以实现O(1)插入了，而且不会影响查询的复杂度。

但是，每个节点的子权值分块的大小是严格值域的，也就是说，出现次数可能为i的数都有可能在那个子权值分块里。这样我们的空间是无法承受的。因此，我们需要进行“分段离散化”(把对于一个出现次数i，要将出现次数>=i的权值全部离散掉。对每个i都得这样做)(复杂度在其后有证明)。

我们最终需要的数据结构是这样的：

一个数组Pinlv[]，记录每种权值出现的次数；

一个权值分块block[]，维护这些出现次数；

然后在以上那个权值分块的每个节点再开一个子权值分块，记录出现次数为其的权值是哪几种。

有点绕是不是……举个例子：

n=11

2 1 3 2 1 4 1 2 2 1 4

假设当前数据结构正在维护a1...an这个区间。

数组Pinlv	[1]	[2]	[3]	[4]
	4	4	1	2
权值分块block	[1]	[2]	[3]	[4]
	1	1	0	2
子权值分块	3	4		1
				2

※一些复杂度的证明：

出现次数i	1	2	3	4	5	...	m
出现次数为i的权值的个数之和(含重复)	S1	S2	S3	S4	S5	...	Sm
S1+S2+S3+...+Sm=n(1<=m<=n)

Ai表示出现次数为i的权值种类数：

A1=S1

A2=S2/2

A3=S3/3

...

Am=Sm/m

设P是A的后缀和：

P1=A1+A2+A3+A4+...+Am

P2=A2+A3+A4...+Am

P3=A3+A4...+Am

...

Pm=Am

①子权值分块的总空间f：

f=P1+P2+...+Pm

=m*Am+(m-1)*Am-1+...+2*A2+1*A1

=m*Sm/m+(m-1)*Sm-1/m-1+...+1*S1/1

=S1+S2+S3+S4+...+Sm

=n

②不分段离散化的子权值分块的总空间f’：

f’=(A1+A2+...+Am)*n

复杂度难以保证。

③分段离散化的总时间复杂度g(这里涉及的log都是<=logn的，因此我们用logn代替)：

先对原始数组去重，其大小就变成了A1+A2+...+Am

g<=P1*logn+P2*logn+...+Pm*logn

=(m*Am+(m-1)*Am-1+...+2*A2+1*A1)*logn

=(m*Sm/m+(m-1)*Sm-1/m-1+...+1*S1/1)*logn

=(S1+S2+S3+S4+...+Sm)*logn

=n*logn

④记录每种权值离散化后的值的数组的总空间h：

h=P1+P2+...+Pm

=m*Am+(m-1)*Am-1+...+2*A2+1*A1

=m*Sm/m+(m-1)*Sm-1/m-1+...+1*S1/1

=S1+S2+S3+S4+...+Sm

=n

因此，最终，只要合理地使用vector，我们的算法的空间复杂度便是O(n)，

时间复杂度是O(m*sqrt(n))。

预计得分：100分。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 40001
typedef vector<int>::iterator VER;
int T[MAXN],plt;
int n,m,a[MAXN],pl[MAXN],upd,num_mo[MAXN],anss[MAXN],num_pl[MAXN],l_pl[MAXN],s_pl[MAXN];
vector<int>LiSan[MAXN],evpl[MAXN],evnum[MAXN],evl[MAXN],evs[MAXN],evb[MAXN];
bool vis[MAXN];
struct Ask{int l,r,k1,k2,p;}Q[MAXN];
bool operator < (const Ask &a,const Ask &b)
{return num_mo[a.l]!=num_mo[b.l] ? num_mo[a.l]<num_mo[b.l] : a.r<b.r;}
void Mo_Make_Block()
{
    int tot=1,sz=sqrt(n);
	if(!sz) sz=1;
    for(;tot*sz<n;++tot)
      {
        int r=tot*sz;
        for(int i=(tot-1)*sz+1;i<=r;++i)
		  num_mo[i]=tot;
      }
    for(int i=(tot-1)*sz+1;i<=n;++i)
	  num_mo[i]=tot;
}
void pl_Make_Block()
{
	plt=1;
	int sz=sqrt(upd);
	if(!sz) sz=1;
    for(;plt*sz<upd;++plt)
      {
      	l_pl[plt]=(plt-1)*sz+1;
      	int r=plt*sz;
        for(int i=l_pl[plt];i<=r;++i)
		  num_pl[i]=plt;
      }
    l_pl[plt]=(plt-1)*sz+1;
    for(int i=l_pl[plt];i<=upd;++i)
	  num_pl[i]=plt;
}
void Insert(const int &x)
{
	if(T[x])
	  {
	  	--pl[T[x]];
		if(!pl[T[x]])--s_pl[num_pl[T[x]]];
		--evb[T[x]][LiSan[x][T[x]]];
		--evs[T[x]][evnum[T[x]][LiSan[x][T[x]]]];
	  }
	++T[x];
	if(!pl[T[x]])++s_pl[num_pl[T[x]]];
	++pl[T[x]];
	++evb[T[x]][LiSan[x][T[x]]];
	++evs[T[x]][evnum[T[x]][LiSan[x][T[x]]]];
}
void Delete(const int &x)
{
	--pl[T[x]];
	if(!pl[T[x]])--s_pl[num_pl[T[x]]];
	--evb[T[x]][LiSan[x][T[x]]];
	--evs[T[x]][evnum[T[x]][LiSan[x][T[x]]]];
	--T[x];
	if(T[x])
	  {
	  	if(!pl[T[x]])++s_pl[num_pl[T[x]]];
	  	++pl[T[x]];
		++evb[T[x]][LiSan[x][T[x]]];
		++evs[T[x]][evnum[T[x]][LiSan[x][T[x]]]];
	  }
}
int Query(const int &K1,const int &K2)
{
	int cnt1=0,cnt2=0;
	for(int i=1;;++i)
	  {
	  	cnt1+=s_pl[i];
	  	if(cnt1>=K1)
	  	  {
	  	  	cnt1-=s_pl[i];
	  	  	for(int j=l_pl[i];;++j)
	  	  	  {
	  	  	  	cnt1+=(bool)pl[j];
	  	  	  	if(cnt1>=K1)
	  	  	  	  {
	  	  	  	  	for(int k=1;;++k)
	          		  {
	          		  	cnt2+=evs[j][k];
	          		  	if(cnt2>=K2)
	          	  		  {
	          	  		  	cnt2-=evs[j][k];
	          	  		  	for(int l=evl[j][k];;++l)
	          	  	  		  {
	          	  	  		  	cnt2+=evb[j][l];
	          	  	  		  	if(cnt2>=K2)
	                      		  return evpl[j][l];
	          	  	  		  }
	          	  		  }
	          		  }
	  	  	  	  }
	  	  	  }
	  	  }
	  }
}
int main()
{
	scanf("%d",&n);
	Mo_Make_Block();
	for(int i=1;i<=n;++i)
	  {
	  	scanf("%d",&a[i]);
	  	++pl[a[i]];
	  }
	upd=*max_element(pl+1,pl+n+1);
	pl_Make_Block();
	for(int i=1;i<=n;++i)
	  if(!vis[a[i]])
	    {
	      vis[a[i]]=1;
	      LiSan[a[i]].assign(pl[a[i]]+1,0);
	      for(int j=1;j<=pl[a[i]];++j)
	        evpl[j].push_back(a[i]);
	    }
	for(int i=1;i<=upd;++i)
	  {
	  	//分段离散化
	  	sort(evpl[i].begin(),evpl[i].end());
	  	int k=1;
	  	for(VER j=evpl[i].begin();j!=evpl[i].end();++j,++k)
	  	  LiSan[*j][i]=k;
	  	//分段权值分块
	  	int Lim=evpl[i].size();
	  	evb[i].assign(Lim+1,0);
	  	int tot=1,sz=sqrt(Lim);
	  	evl[i].push_back(0);
	  	evnum[i].push_back(0);
	  	if(!sz) sz=1;
    	for(;tot*sz<Lim;++tot)
      	  {
      	  	evl[i].push_back((tot-1)*sz+1);
        	int r=tot*sz;
        	for(int j=evl[i][tot];j<=r;++j)
		  	  evnum[i].push_back(tot);
      	  }
      	evl[i].push_back((tot-1)*sz+1);
    	for(int j=evl[i][tot];j<=Lim;++j)
	  	  evnum[i].push_back(tot);
	  	evs[i].assign(tot+1,0);
	  	evpl[i].insert(evpl[i].begin(),0);
	  }
	scanf("%d",&m);
	for(int i=1;i<=m;++i)
	  {
	  	scanf("%d%d%d%d",&Q[i].l,&Q[i].r,&Q[i].k1,&Q[i].k2);
	  	Q[i].p=i;
	  }
	sort(Q+1,Q+m+1);
	memset(pl,0,(n+1)*sizeof(int));
    for(int i=Q[1].l;i<=Q[1].r;++i)
	  Insert(a[i]);
    anss[Q[1].p]=Query(Q[1].k1,Q[1].k2);
    for(int i=2;i<=m;++i)
      {
        if(Q[i].l<Q[i-1].l)
		  for(int j=Q[i-1].l-1;j>=Q[i].l;--j)
		    Insert(a[j]);
        if(Q[i].r>Q[i-1].r)
		  for(int j=Q[i-1].r+1;j<=Q[i].r;++j)
		    Insert(a[j]);
        if(Q[i].l>Q[i-1].l)
		  for(int j=Q[i-1].l;j<Q[i].l;++j)
		    Delete(a[j]);
        if(Q[i].r<Q[i-1].r)
		  for(int j=Q[i-1].r;j>Q[i].r;--j)
		    Delete(a[j]);
    	anss[Q[i].p]=Query(Q[i].k1,Q[i].k2);
      }
    for(int i=1;i<=m;++i)
      printf("%d\n",anss[i]);
	return 0;
}