首页 > 代码库 > bzoj 1367: [Baltic2004]sequence
bzoj 1367: [Baltic2004]sequence
1367: [Baltic2004]sequence
Time Limit: 20 Sec Memory Limit: 64 MBDescription
Input
Output
一个整数R
Sample Input
7
9
4
8
20
14
15
18
9
4
8
20
14
15
18
Sample Output
13
HINT
所求的Z序列为6,7,8,13,14,15,18.
R=13
详细证明请看IOI2005国家集训队论文 黄源河
https://wenku.baidu.com/view/20e9ff18964bcf84b9d57ba1.html
两个极端情况:
1、a[i]<a[i+1]<a[i+2]<a[i+3]…… ans[i]=a[i]
2、a[i]>a[i+1]>a[i+2]>a[i+3]…… ans[i]=ans[i+1]=ans[i+2]=a[i+3]=区间中位数
将每一个点看做一个区间，如果前一个区间的中位数比这个大，则合并
所以我们对于每一段已求好的序列，既要维护它的中位数，又要支持合并
因为我们合并的前提是：中位数(i)>中位数(i+1)，那么对于合并后的i而言，中位数肯定是不升的
根据这个性质我们又可以用可并堆了，堆顶元素表示该序列中的中位数
当堆的元素个数*2>序列长度+1的时候就可以弹出堆顶
如何保证严格上升？
常用套路：a[i]-i
#include<cstdio>#include<algorithm>#define N 1000001using namespace std;int a[N],siz[N],tot[N],root[N],lc[N],rc[N],now,lp[N],rp[N],dis[N];int merge(int x,int y){ if(!x) return y; if(!y) return x; if(a[x]<a[y]) swap(x,y); rc[x]=merge(rc[x],y); siz[x]=siz[lc[x]]+siz[rc[x]]+1; if(dis[lc[x]]<dis[rc[x]]) swap(lc[x],rc[x]); dis[x]=dis[rc[x]]+1; return x;}int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]-=i; for(int i=1;i<=n;i++) { root[++now]=i; lp[now]=rp[now]=i; siz[root[now]]=tot[now]=1; while(now>1&&a[root[now-1]]>a[root[now]]) { now--; rp[now]=rp[now+1]; tot[now]+=tot[now+1]; root[now]=merge(root[now],root[now+1]); while(siz[root[now]]*2>tot[now]+1) root[now]=merge(lc[root[now]],rc[root[now]]); } } long long ans=0; for(int i=1;i<=now;i++) for(int j=lp[i];j<=rp[i];j++) ans+=abs((long long)a[j]-a[root[i]]); printf("%lld",ans);}
bzoj 1367: [Baltic2004]sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。