首页 > 代码库 > sequence(bzoj 1367)
sequence(bzoj 1367)
Description
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
/* 思维很扭曲(反正我想不出来)的一道题。 先想想不下降的: 考虑一个正序的序列,z[i]=t[i] 考虑一个逆序的序列,z[i]=x(x是逆列的中位数) 既然是这样那么我们就可以把整个序列化分成逆序的若干段,对于每段求中位数(正序的可看成num个逆序的)。 维护中位数用左偏树,具体方法是始终保持堆中数的个数不大于原数个数的一半。 至于改成上升的,把原序列t[i]-=i。 PS:题解中的root[i]和堆中下标的关系把我看蒙了,所以这里说一下。 代码中是建立了n个堆,然而不断合并,最终变成了tot个。 root[i]表示第i个堆(合并后的)的堆顶是哪个元素。 */ #include<cstdio> #include<iostream> #include<cstdlib> #define N 1000010 using namespace std; int t[N],root[N],l[N],r[N],num[N],cnt[N],n,tot; struct node{ int l,r,dis,w; };node heap[N]; int merge(int a,int b){ if(a==0||b==0)return a+b; if(heap[a].w<heap[b].w)swap(a,b); heap[a].r=merge(heap[a].r,b); if(heap[heap[a].r].dis>heap[heap[a].l].dis) swap(heap[a].r,heap[a].l); heap[a].dis=heap[heap[a].r].dis+1; return a; } int pop(int a){ return merge(heap[a].l,heap[a].r); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&t[i]),t[i]-=i; for(int i=1;i<=n;i++){ ++tot; l[tot]=r[tot]=i; num[tot]=cnt[tot]=1; root[tot]=i; heap[i].dis=heap[i].l=heap[i].r=0; heap[i].w=t[i]; while(tot>1&&heap[root[tot]].w<heap[root[tot-1]].w){ --tot; root[tot]=merge(root[tot],root[tot+1]); num[tot]+=num[tot+1],cnt[tot]+=cnt[tot+1],r[tot]=r[tot+1]; for(;cnt[tot]*2>num[tot]+1;--cnt[tot]) root[tot]=pop(root[tot]); } } long long ans=0; for(int i=1;i<=tot;i++) for(int j=l[i],w=heap[root[i]].w;j<=r[i];j++) ans+=abs(t[j]-w); cout<<ans; return 0; }
sequence(bzoj 1367)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。