首页 > 代码库 > Vijos1459 车展 (treap)
Vijos1459 车展 (treap)
描述
遥控车是在是太漂亮了,韵韵的好朋友都想来参观,所以游乐园决定举办m次车展。车库里共有n辆车,从左到右依次编号为1,2,…,n,每辆车都有一个展台。刚开始每个展台都有一个唯一的高度h[i]。主管已经列好一张单子:
L1 R1
L2 R2
…
Lm Rm
单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri的车。
为了更加美观,展览时需要调整展台的高度,使参展所有展台的高度相等。展台的高度增加或减少1都需花费1秒时间。由于管理员只有一个人,所以只好对每个展台依次操作。每次展览结束后,展台高度自动恢复到初始高度。
请告诉管理员为了举办所有展览,他最少需要花多少时间将展台调整好。
格式
输入格式
第一行为两个正整数n、m。
第二行共n个非负整数,表示第i辆车展台的高度h[i]。
接下来m行每行2个整数Li、Ri(Li≤Ri)。
输出格式
一个正整数,调整展台总用时的最小值。
样例1
样例输入1[复制]
6 44 1 2 13 0 91 52 63 42 2
样例输出1[复制]
48
限制
各个测试点1s
提示
对于50%的数据 n≤500,m≤1000;
对于80%的数据 n≤1000,m≤100000;
对于100%的数据n≤1000,m≤200000;
答案在2^64以内。
来源
birdor
分析可知将区间高度都调整成中位数时答案最优。
用treap查询中位数。
枚举区间起点,然后从该点一直往右扫描,每次将该位置的数加入到treap中,并查询第size/2大的数,即是这段区间的中位数。
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<ctime> 8 #include<vector> 9 using namespace std;10 const int mxn=1010;11 int read(){12 int x=0,f=1;char ch=getchar();13 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}14 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}15 return x*f;16 }17 struct node{18 int l,r;19 int size,v,w;20 int rnd;21 }t[mxn];22 int cnt,root;23 void update(int rt){24 t[rt].size=t[t[rt].l].size+t[t[rt].r].size+t[rt].v;25 }26 void lturn(int &k){27 int now=t[k].r;28 t[k].r=t[now].l;29 t[now].l=k;30 update(k);update(now);k=now;31 return;32 }33 void rturn(int &k){34 int now=t[k].l;35 t[k].l=t[now].r;36 t[now].r=k;37 update(k);update(now);k=now;38 return;39 }40 void insert(int &k,int x){41 if(!k){42 t[++cnt].w=x;43 t[cnt].size=1;t[cnt].v=1;44 t[cnt].rnd=rand();45 t[cnt].r=t[cnt].l=0;46 k=cnt;47 return;48 }49 t[k].size++;50 if(x==t[k].w)t[k].v++;51 else if(x<t[k].w){52 insert(t[k].l,x);53 if(t[t[k].l].rnd<t[k].rnd)rturn(k);54 }55 else{56 insert(t[k].r,x);57 if(t[t[k].r].rnd<t[k].rnd)lturn(k);58 }59 return;60 }61 int query(int k,int num){62 if(!k)return 0;63 64 // printf("k:%d num:%d\n",k,num);65 // printf("l:%d r:%d v:%d size:%d\n",t[k].l,t[k].r,t[k].v,t[k].size);66 if(num<=t[t[k].l].size)return query(t[k].l,num);67 if(num>t[t[k].l].size+t[k].v)return query(t[k].r,num-t[t[k].l].size-t[k].v);68 return t[k].w;69 }70 int h[mxn];71 int mid[mxn][mxn];72 int n,m;73 int main(){74 srand(time(0));75 n=read();m=read();76 int i,j;77 for(i=1;i<=n;i++) h[i]=read();78 for(i=1;i<=n;i++){79 cnt=root=0;80 for(j=i;j<=n;j++){81 // printf("root:%d ",root);82 insert(root,h[j]);83 // printf(" %d \n",root);84 mid[i][j]=query(root,(j-i+2)/2);85 // printf("root:%d mid %d %d:%d\n",root,i,j,mid[i][j]);86 }87 }88 int st,ed;89 long long res=0,ans=0;90 while(m--){91 res=0;92 st=read();ed=read();93 for(i=st;i<=ed;i++)res+=abs(h[i]-mid[st][ed]);94 // printf("%d %d %d %d\n",st,ed,mid[st][ed],res);95 ans+=res;96 }97 printf("%lld\n",ans);98 return 0;99 }
Vijos1459 车展 (treap)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。