AC通道:http://www.lydsy.com/JudgeOnline/problem.php?id=2653
题目大意:多组询问,求左右端点在规定范围内移动所能得到的最大中位数。
[分析]
求中位数这类题目比较少见[笔者见识少...],但是它的性质比较优美——从小到大排序排在中间的数字。
如果往常求一个无序数列的中位数,最好的复杂度就是n*logn[快排一遍的复杂度],[因为你要知道每个元素在序列中的大小]
但是我们这里是多组询问,而且元素不会修改,也就是每个元素的相对大小会在一开始预处理就搞定。
现在我们再来想:左右端点只是一个范围,怎么求出满足情况的最优区间呢?
根据时间的效率,肯定不能用枚举。
那么这个区间就一定有性质,什么性质呢?中位数最大。
我们要从中位数最大来找到这个区间。
也就是这个区间里比中位数大的元素和比中位数小的元素一样多。
可想而知:我们希望这个区间内的大的数越多,小的数越少越好,可是大小只是一个相对的概念,必须要和中位数比较才知道什么叫大,什么叫小。
谁是最大的中位数呢?求的就是这个,我们怎么知道...那我们只好二分了。
二分出这个中位数之后,我们要找这个最优区间就好办了:
假设比中位数小的数值记作-1,比中位数大的数值记作1。
最优区间一定满足:区间元素[指的是1,-1这些数]的和最大。
求最大和的这个过程可以用很多数据结构解决了,即求[a,b]的右端最大+(b,c)的和+[c,d]的左端最大。
可是我其实只需要这个值大于0,当前二分的值就是合法的了,我就会去追求一个更大的中位数,对吧。
也就是说,思考的过程是:
二分一个答案->找到最优的区间->区间如果满足->去追寻更好的答案。
其中最优区间是找寻答案的前提,但只有先暂时确定一个较好值才能找到符合这个的最优区间。[逻辑上有点成环]
最后因为对于每个二分出来的中位数值都希望有一个[-1,1]的序列专门分给它,这个靠什么呢?
想起之前的可持久化线段树就好办了:
树的节点意义是下标的位置范围,树的节点同时需要记录下这个节点代表区间的“右端最大”、“左端最大”、“求和”三种属性
最小的元素所有位置都标上1[因为所有元素都比它大嘛...],
然后从小到大的添加元素,先复制上一棵树,每次将树上上一个元素所在的位置标上-1,同时需要在过程中更新出右端最大、左端最大、求和三种属性。
因为上一棵树和这一棵树的唯一区别就是上一棵树在上一个元素的位置上标记为1,而这一棵树标记为-1,这样每次就是更新树上的一条链,变化不会很大,采用的就是可持久化线段树的思想了。
最后献上代码:
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; inline int in(){
int x=;char ch=getchar();
while(ch>'' || ch<'') ch=getchar();
while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return x;
} const int maxn=; int n,m,key,cnt,ans;
int a[maxn];
int id[maxn],rt[maxn]; struct Node{
int l,r,sz;
int lx,rx,sm;
}s[maxn*]; bool cmp(const int &x1,const int &x2){
return a[x1]<a[x2];
} void renew(int x){
s[x].sm=s[s[x].l].sm+s[s[x].r].sm;
s[x].lx=max(s[s[x].l].lx,s[s[x].l].sm+s[s[x].r].lx);
s[x].rx=max(s[s[x].r].rx,s[s[x].r].sm+s[s[x].l].rx);
} void build(int l,int r,int &rt){
if(l==r){
rt=++cnt,s[rt].sm=s[rt].lx=s[rt].rx=;
return ;
}
rt=++cnt;
int mid=(l+r)>>;
build(l,mid,s[rt].l);
build(mid+,r,s[rt].r);
renew(rt);
} void update(int last,int l,int r,int &rt,int val){
rt=++cnt;s[rt]=s[last];
if(l==r){
s[rt].lx=s[rt].rx=s[rt].sm=val;
return ;
}
int mid=(l+r)>>;
if(key<=mid) update(s[last].l,l,mid,s[rt].l,val);
else update(s[last].r,mid+,r,s[rt].r,val);
renew(rt);
} int get_all(int rt,int l,int r,int x,int y){
if(l==x && r==y) return s[rt].sm;
int mid=(l+r)>>;
if(y<=mid)
return get_all(s[rt].l,l,mid,x,y);
else if(x>mid)
return get_all(s[rt].r,mid+,r,x,y);
else
return get_all(s[rt].l,l,mid,x,mid)+get_all(s[rt].r,mid+,r,mid+,y);
} int get_lx(int rt,int l,int r,int x,int y){
if(l==x && r==y) return s[rt].lx;
int mid=(l+r)>>;
if(y<=mid)
return get_lx(s[rt].l,l,mid,x,y);
else if(x>mid)
return get_lx(s[rt].r,mid+,r,x,y);
else
return max(get_lx(s[rt].l,l,mid,x,mid),get_all(s[rt].l,l,mid,x,mid)+get_lx(s[rt].r,mid+,r,mid+,y));
} int get_rx(int rt,int l,int r,int x,int y){
if(l==x && r==y) return s[rt].rx;
int mid=(l+r)>>;
if(y<=mid)
return get_rx(s[rt].l,l,mid,x,y);
else if(x>mid)
return get_rx(s[rt].r,mid+,r,x,y);
else
return max(get_rx(s[rt].r,mid+,r,mid+,y),get_all(s[rt].r,mid+,r,mid+,y)+get_rx(s[rt].l,l,mid,x,mid));
} bool check(int k,int a,int b,int c,int d){
int sum=;
if(c>b+) sum+=get_all(rt[k],,n-,b+,c-);
sum+=get_rx(rt[k],,n-,a,b);
sum+=get_lx(rt[k],,n-,c,d);
return sum>=;
} int main(){
#ifndef ONLINE_JUDGE
freopen("2653.in","r",stdin);
freopen("2653.out","w",stdout);
#endif n=in();
for(int i=;i<n;i++)
a[i]=in(),id[i]=i;
sort(id,id+n,cmp);
build(,n-,rt[]);
for(int i=;i<n;i++)
key=id[i-],update(rt[i-],,n-,rt[i],-); int ord[]; m=in();
while(m--){
ord[]=in(),ord[]=in(),ord[]=in(),ord[]=in();
for(int i=;i<;i++)
ord[i]=(ord[i]+ans)%n;
sort(ord,ord+);
int l=,r=n,mid;
while(l+<r){
mid=(l+r)>>;
if(check(mid,ord[],ord[],ord[],ord[])) l=mid;
else r=mid;
}
ans=a[id[l]];
printf("%d\n",ans);
} return ;
}
BZOJ 2653 middle的更多相关文章
-
[BZOJ 2653] middle(可持久化线段树+二分答案)
[BZOJ 2653] middle(可持久化线段树+二分答案) 题面 一个长度为n的序列a,设其排过序之后为b,其中位数定义为b[n/2],其中a,b从0开始标号,除法取下整. 给你一个长度为n的序 ...
-
bzoj 2653: middle (主席树+二分)
2653: middle Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 2522 Solved: 1434[Submit][Status][Disc ...
-
BZOJ 2653: middle 主席树 二分
https://www.lydsy.com/JudgeOnline/problem.php?id=2653 因为是两个方向向外延伸所以不能对编号取前缀和(这里只有前缀和向后传递的性质,不是实际意义的和 ...
-
BZOJ 2653 middle | 主席树
题目: http://www.lydsy.com/JudgeOnline/problem.php?id=2653 题解: 设答案为ans,把大于等于ans的记为1,小于的记为-1,这样可以知道当前an ...
-
bzoj 2653 middle (可持久化线段树)
middle Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 1981 Solved: 1097[Submit][Status][Discuss] D ...
-
BZOJ 2653: middle [主席树 中位数]
传送门 题意: 一个长度为n的序列a,设其排过序之后为b,其中位数定义为b[n/2],其中a,b从0开始标号,除法取下整.给你一个 长度为n的序列s.回答Q个这样的询问:s的左端点在[a,b]之间,右 ...
-
bzoj 2653 middle 二分答案 主席树判定
判断中位数是否可行需要将当前的解作为分界,大于其的置为1,小于为-1,然后b-c必选,ab,cd可不选,这个用线段树判定就好 但不能每次跑,所以套主席树,按权值排序,构建主席树,更新时将上一个节点改为 ...
-
BZOJ 2653 middle 二分答案+可持久化线段树
题目大意:有一个序列,包含多次询问.询问区间左右端点在规定区间里移动所得到的最大中位数的值. 考虑对于每个询问,如何得到最优区间?枚举显然是超时的,只能考虑二分. 中位数的定义是在一个序列中,比中位数 ...
-
bzoj 2653 middle(主席树)
题面:https://vjudge.net/problem/HYSBZ-2653 博客:https://blog.csdn.net/litble/article/details/78984846 这个 ...
随机推荐
-
[poj2182] Lost Cows (线段树)
线段树 Description N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacula ...
-
svn: Checksum mismatch for &#39;C:\Documents and Settings\Admin\workspace\pics5\src\baolintest\.svn\text-base\test1.java.svn-base&#39;; expected: &#39;034cc715af5
出现这个问题解决如下: 比如问题文件为\workspace\pics5\src\baolintest\test.java文件,则 1.把在工程根\workspace\pics5\src\baolint ...
-
C#----我对坐标系的理解和图形转动
目录: 设置图形的旋转 设置坐标轴的反向 图形的旋转 参考一个文章:http://www.bccn.net/Article/kfyy/vc/jszl/200601/3008.html ; 目标:让Dr ...
-
在SQL2008R2查询分析器出错(在执行批处理时出现错误。错误消息为: 目录名称无效。)
在用SQL2008R2查询分析器时 SELECT * FROM 表名; 出错: 在执行批处理时出现错误.错误消息为: 目录名称无效. 原因: 在打开查询分析器时,用360软件清空了临时文件(只是偶尔1 ...
-
Android学习笔记(四十):Preference的使用
Preference直译为偏好,博友建议翻译为首选项.一些配置数据,一些我们上次点击选择的内容,我们希望在下次应用调起的时候依旧有效,无须用户再一次进行配置或选择.Android提供preferenc ...
-
Python基础知识--列表和集合
列表:有序性,可以存放任意类型的对象,通过索引访问,可以分片操作 >>> L = ['id', 1000, 'scd', 1000, 'scd'] >>> L [' ...
-
神经网络工具箱nntool的使用方法
关于如何使用nntool神经网络工具箱进行“数据训练”的方法: 1. 在命令窗口键入nntool命令打开神经网络工具箱: 2. 点击Import按钮两次,分别把输入向量和目标输出加入到对应的窗口([I ...
-
Ionic3 遇到的一些错误-submodule update -q --init --recursive
解决方法: ionic start myTabs tabs --skip-deps cd .\myTabs cnpm install --save-dev ionic serve > npm i ...
-
iOS App让自己的应用在其它应用中打开列表中显示
像百度网盘等应用,里面的文件打开时,都能够通过以下应用再打开文件.以下红色框框内的我的jpg就是我做的一个样例. 由于样例没有提供Icon,所以显示的是默认icon. 以下就是这样例的主要步骤和代 ...
-
Web API之路由浅谈
Web API的路由,是指明接口地址的方向,是照亮获取数据路上的灯塔,其重要性不言而喻. 本篇文章以vs2015为例,一步步说明路由的创建及使用,其中包括默认路由.自定义路由和特性路由. 一.默认路由 ...