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

时间:2022-05-02 22:32:42

【算法一】

暴力。

可以通过第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;
}

【莫队算法】【权值分块】bzoj3920 Yuuna的礼物的更多相关文章

  1. BZOJ2038&colon; &lbrack;2009国家集训队&rsqb;小Z的袜子&lpar;hose&rpar; -- 莫队算法 ,,分块

    2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec  Memory Limit: 259 MBSubmit: 3577  Solved: 1652[Subm ...

  2. 莫队算法 sqrt&lpar;n&rpar;分块思想

    在此说一下本渣对莫队算法思想的一些浅薄理解 莫队算法的思想就是对真个区间的分块,然后按照每块来分别进行计算,这样最终的复杂度可以达到n*sqrt(n) 小Z的袜子是一道非常经典的题目.:题目链接htt ...

  3. Luogu 1494 - 小Z的袜子 - &lbrack;莫队算法模板题&rsqb;&lbrack;分块&rsqb;

    题目链接:https://www.luogu.org/problemnew/show/P1494 题目描述 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿.终于有一天 ...

  4. 莫队或权值线段树 或主席树 p4137

    题目描述 有一个长度为n的数组{a1,a2,…,an}.m次询问,每次询问一个区间内最小没有出现过的自然数. 输入格式 第一行n,m. 第二行为n个数. 从第三行开始,每行一个询问l,r. 输出格式 ...

  5. 【BZOJ】4358&colon; permu 莫队算法

    [题意]给定长度为n的排列,m次询问区间[L,R]的最长连续值域.n<=50000. [算法]莫队算法 [题解]考虑莫队维护增加一个数的信息:设up[x]表示数值x往上延伸的最大长度,down[ ...

  6. 【莫队算法】【权值分块】poj2104 K-th Number &sol; poj2761 Feed the dogs

    先用莫队算法保证在询问之间转移的复杂度,每次转移都需要进行O(sqrt(m))次插入和删除,权值分块的插入/删除是O(1)的. 然后询问的时候用权值分块查询区间k小值,每次是O(sqrt(n))的. ...

  7. 【莫队算法】【权值分块】bzoj2223 &lbrack;Coci 2009&rsqb;PATULJCI

    不带修改主席树裸题<=>莫队+权值分块裸题. 复杂度O(m*sqrt(n)). P.S.题目描述坑爹,第二个数是权值的范围. #include<cstdio> #include ...

  8. 【DFS序】【莫队算法】【权值分块】bzoj2809 &lbrack;Apio2012&rsqb;dispatching

    题意:在树中找到一个点i,并且找到这个点子树中的一些点组成一个集合,使得集合中的所有点的c之和不超过M,且Li*集合中元素个数和最大 首先,我们将树处理出dfs序,将子树询问转化成区间询问. 然后我们 ...

  9. 【莫队算法】【权值分块】bzoj3585 mex

    orz PoPoQQQ. 本来蒟蒻以为这种离散化以后就对应不起来的题不能权值分块搞的说. ……结果,实际上>n的权值不会对答案作出贡献. #include<cstdio> #incl ...

随机推荐

  1. 在项目中同时使用Objective-C和Swift

    苹果发布的Swift语言可以和之前的Objective-C语言同时存在于一个项目中. 可能有人会认为是同一个类文件中既可以有Objective-C也可以有Swift,这是不对的.同一个类文件或同一个代 ...

  2. 如何使CEF支持Flash

    方法一:复制Chrome浏览器下的pepperFlash,通过cef命令行参数设置路径. public Form1() { InitializeComponent(); InitializeChrom ...

  3. QT学习笔记3

    对话框 新建了一个对话框,在新建项目选择类型时是Dialog即可. 添加的代码如下,注意QCheckBox 并没有添加头文件定义,只是加了类的前向声明.因为我们仅仅使用的是指针,并不涉及到这些类的函数 ...

  4. Linux内核设计第八周 ——进程的切换和系统的一般执行过程

    Linux内核设计第八周 ——进程的切换和系统的一般执行过程 第一部分 知识点总结 第二部分 实验部分 1.配置实验环境,确保menu内核可以正常启动 2.进入gdb调试,在shedule和conte ...

  5. 【剑指offer】求逆序对的个数

    2013-09-07 10:50:31 面试题36:在数组中的两个数字如果前面一个数字大于后面的数字,则这两个数字构成一个逆序对.输入一个数组,求出这个数组中逆序对的总数. 小结: 最直观的的方法是: ...

  6. 接私活,得有套好框架,&period;net快速开发神器

    同一家公司的同事,拿同样的工资,以前他在用肾机,我还在用诺记.吃饭的时候他是买单王,我在想这家伙应该没存什么钱吧.结果前段时间他买了个沃尔沃S60L,可我一套省城小三房的首付都还没凑齐. 他说他经常在 ...

  7. cf479D Long Jumps

    D. Long Jumps time limit per test 1 second memory limit per test 256 megabytes input standard input ...

  8. 从花式swap引出的pointer aliasing问题

    上次,一个同学问我,你知不知道可以不用引入中间变量就可以实现swap? 我说,我知道,可以用加减法或者异或实现,像是这样 void mySwap(int &x,int &y) { x= ...

  9. apply和call的区别

    每一个javascript中的Function对象都有一个apply()方法和call()方法,他们的基本用法为: /*apply()方法*/ function.apply(thisObj[, arg ...

  10. shell 构建脚本基础

    bash -v test.sh 启用 verbose 调试模式 bash -n test.sh  启用语法检查调试模式 bash -x test.sh  遍历脚本执行过程 一.基础参数 1.shell ...