md调了一个晚上最后发现竟然是空间开小了……明明算出来够的……
讲真其实我以前不太瞧得起分块,觉得这种基于暴力的数据结构一点美感都没有。然而今天做了这道分块的题才发现分块的暴力之美(如果我空间没有开小就更美了)
我们先将整个数组分块,设块的大小为$T$
我们先预处理出所有以块边界为端点的区间的答案,即$ans[L][R]$代表着第$L$块到第$R$块的序列所代表的答案。这个可以$O(n*n/T)$预处理
然后我们先将所有的数给离散化,然后对每一个值都开一个vector,记录这个值在数组中出现的每一个位置。比如数组的下标为1,3,5的位置都是3,那么3的vector记录的就是{1,3,5}
这个有什么用呢?我们设查询的区间为$[l,r]$,然后在这个vector里先二分查找第一个大于等于$l$的数的位置,再二分查找第一个大于$r$的数的位置,那么两个位置一减就是这个数在这个区间中的出现次数。比如查询区间$[2,4]$,我们先找到第一个大于等于2的数3,在vector中下标为2,再找第一个大于4的数为5,下标为3,那么3-2=1就是3这个数字在这个区间中的出现次数
那么,我们设$[L,R]$为查询区间之间的整块,因为我们第一步已经预处理出了所有块与块之间的答案,那么这一段之间的众数也就可以知道。那么,只有区间$[l,L-1]$和$[R+1,r]$之间的数字有可能更新答案。那么我们就去枚举这两个区间中的所有数字,然后用上面说的方法去查询它在整个查询区间内的出现次数,然后更新答案即可
复杂度为$O(n*n/T+n*T*logn)$,设块的大小为$n/sqrt{nlogn}$ ,那么时间复杂度就是$O(nsqrt{nlogn})$
其实还有一种更快的方法是先预处理出块与块之间的答案和各个数的出现次数,然后查询只要在散块里暴力增加并更新答案,之后暴力复原即可(然而我懒并不想打)
然后基本注意点都写在注解里了
//minamoto
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(int x){
if(C><<)Ot();if(x<)sr[++C]=,x=-x;
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=,M=;
int ans[M][M],a[N],b[N],cnt[N],rt[N],vis[N];
vector<int> pos[N];
int n,m,q,lastans=,s,l,r;
inline int query_cnt(int x){
//查询数的出现次数,注意l和r要开全局变量
return upper_bound(pos[x].begin(),pos[x].end(),r)-lower_bound(pos[x].begin(),pos[x].end(),l);
}
void init(){
//暴力枚举块与块之间的答案
for(int i=;i<=rt[n];++i){
memset(cnt,,sizeof(cnt));
int bg=s*(i-)+,res=a[bg];
for(int j=bg;j<=n;++j){
++cnt[a[j]];
if(cnt[a[j]]>cnt[res]||(cnt[a[j]]==cnt[res]&&a[j]<res)) res=a[j];
ans[i][rt[j]]=res;
}
}
}
int query(int l,int r){
//查询,小块暴力,大块直接找答案
if(rt[r]-rt[l]<=){
int id=,res=;
for(int i=l;i<=r;++i)
if(!vis[a[i]]){
int t=query_cnt(a[i]);
if(t>res||(t==res&&a[i]<id)) res=t,id=a[i];
vis[a[i]]=;
}
for(int i=l;i<=r;++i) vis[a[i]]=;
return b[id];
}
int L=rt[l]+,R=rt[r]-;
int LL=(L-)*s+,RR=R*s;
int id=ans[L][R],res=query_cnt(id);vis[id]=;
for(int i=l;i<LL;++i)
if(!vis[a[i]]){
int t=query_cnt(a[i]);
if(t>res||(t==res&&a[i]<id)) res=t,id=a[i];
vis[a[i]]=;
}
for(int i=RR+;i<=r;++i)
if(!vis[a[i]]){
int t=query_cnt(a[i]);
if(t>res||(t==res&&a[i]<id)) res=t,id=a[i];
vis[a[i]]=;
}
for(int i=l;i<LL;++i) vis[a[i]]=;
for(int i=RR+;i<=r;++i) vis[a[i]]=;
vis[ans[L][R]]=;
return b[id];
}
int main(){
n=read(),q=read(),s=sqrt(n/(double)(log2(n))+);
//我怕s会变成0所以sqrt里加了个1(可能并不需要)
for(int i=;i<=n;++i) a[i]=b[i]=read(),rt[i]=(i-)/s+;//分块
sort(b+,b++n),m=unique(b+,b++n)-b-;
for(int i=;i<=n;++i) a[i]=lower_bound(b+,b++m,a[i])-b,pos[a[i]].push_back(i);
//以上是离散
init();
while(q--){
l=read(),r=read();
l=(l+lastans-)%n+,r=(r+lastans-)%n+;
if(l>r) swap(l,r);
print(lastans=query(l,r));
}
Ot();
return ;
}
bzoj2724: [Violet 6]蒲公英(分块)的更多相关文章
-
BZOJ2724 [Violet 6]蒲公英 分块
原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ2724.html 题目传送门 - BZOJ2724 题意 求区间最小众数,强制在线. $n$ 个数,$m ...
-
bzoj2724: [Violet 6]蒲公英 分块 区间众数 论algorithm与vector的正确打开方式
这个,要处理各个数的话得先离散,我用的桶. 我们先把每个块里的和每个块区间的众数找出来,那么在查询的时候,可能成为[l,r]区间的众数的数只有中间区间的众数和两边的数. 证明:若不是这里的数连区间的众 ...
-
[BZOJ2724][Violet 6]蒲公英
[BZOJ2724][Violet 6]蒲公英 试题描述 输入 修正一下 l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1 输出 输入示 ...
-
【BZOJ2724】[Violet 6]蒲公英 分块+二分
[BZOJ2724][Violet 6]蒲公英 Description Input 修正一下 l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n ...
-
BZOJ 2724: [Violet 6]蒲公英( 分块 )
虽然AC了但是时间惨不忍睹...不科学....怎么会那么慢呢... 无修改的区间众数..分块, 预处理出Mode[i][j]表示第i块到第j块的众数, sum[i][j]表示前i块j出现次数(前缀和, ...
-
【分块】bzoj2724 [Violet 6]蒲公英
分块,离散化,预处理出: ①前i块中x出现的次数(差分): ②第i块到第j块中的众数是谁,出现了多少次. 询问的时候,对于整块的部分直接获得答案:对于零散的部分,暴力统计每个数出现的次数,加上差分的结 ...
-
【bzoj2724】[Violet 6]蒲公英 分块+STL-vector
题目描述 输入 修正一下 l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1 输出 样例输入 6 3 1 2 3 2 1 2 1 5 3 ...
-
bzoj2724: [Violet 6]蒲公英(离散化+分块)
我好弱啊..这题调了2天QwQ 题目大意:给定一个长度为n(n<=40000)的序列,m(m<=50000)次询问l~r之间出现次数最多的数.(区间众数) 这题如果用主席树就可以不用处理一 ...
-
BZOJ 2724: [Violet 6]蒲公英 [分块 区间众数]
传送门 题面太美不忍不放 分块分块 这种题的一个特点是只有查询,通常需要预处理:加入修改的话需要暴力重构预处理 预处理$f[i][j]$为第i块到第j块的众数,显然$f[i][j]=max{f[i][ ...
随机推荐
-
J2EE中关于tomcat的maxIdle、maxActive、maxActive相关配置
一.基本概念 1 maxActive 连接池的最大数据库连接数.设为0表示无限制,一般把maxActive设置成可能的并发量就行了 2 maxIdle 最大的空闲连接数 3 maxWait 最大建立连 ...
-
性能测试类,让你写法代码养成经常测试的好习惯 -ASP.NET C#
介绍: 可以很方便的在代码里循环执行 需要测试的函数 自动统计出执行时间,支持多线程. 使用方法: PerformanceTest p = new PerformanceTest(); p.SetC ...
-
postgresql之ctid的浅谈
ctid: 表示数据记录的物理行当信息,指的是 一条记录位于哪个数据块的哪个位移上面. 跟oracle中伪列 rowid 的意义一样的:只是形式不一样. 例如这有个一表test:查看每行记 ...
-
scaleform 注意事项
在使用 自带的UI .fla 里面的组建时 需要把自己建立的fla进行如下设置. 文件-发布设置-flash-脚本actionscript3.0设置——舞台:自动声明舞台实例
-
qemu 调试(二)
我见过最全的剖析QEMU原理的文章 qemu代码分析 qemu中ELF文件的加载 几个关键点,可以设计断点,观察. $ cat command.gdbset breakpoint pending on ...
-
docker 中国站 www.dockerpool.com 报价图片下载
为了方便一些基本的下载docker 镜像,我建立了一个docker该站 http://www.dockerpool.com 对于Docker用户提供一站式Docker镜像服务: 稳定可靠的官方镜像下载 ...
-
Rabbitmq重启服务器用户丢失解决办法
参考:https://blog.csdn.net/yiluoAK_47/article/details/78173563?utm_source=blogxgwz2 Rabbitmq创建的用户在服务器重 ...
-
Django手册
Django教程 Python一直是我最喜欢的语言,在Django和Tornado之间我选择了前者,没有特别的原因,网上人云亦云的,肯定不会有一方离另一方差很远,我就直接去看了看Github上两个项目 ...
-
Codeforces 838A - Binary Blocks(二维前缀和+容斥)
838A - Binary Blocks 思路:求一下前缀和,然后就能很快算出每一小正方块中1的个数了,0的个数等于k*k减去1的个数,两个的最小值就是要加进答案的值. 代码: #include< ...
-
scss-@for 指令
此指令用于循环输出,具有两种循环方式,下面分别做一下介绍. (1).@for $var from <start> through <end>: 此种方式的遍历索引区间是[sta ...