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 4
4 1 2 13 0 9
1 5
2 6
3 4
2 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 }
时间: 11-02

Vijos1459 车展 (treap)的相关文章

Vijos P1459 车展 treap求任意区间中位数

描述 遥控车是在是太漂亮了,韵韵的好朋友都想来参观,所以游乐园决定举办m次车展.车库里共有n辆车,从左到右依次编号为1,2,…,n,每辆车都有一个展台.刚开始每个展台都有一个唯一的高度h[i].主管已经列好一张单子:L1 R1L2 R2…Lm Rm单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri的车. 为了更加美观,展览时需要调整展台的高度,使参展所有展台的高度相等.展台的高度增加或减少1都需花费1秒时间.由于管理员只有一个人,所以只好对每个展台依次操作.每次展览结束后,展台高度自动

Vijos1459 车展 (数学)

描述 遥控车是在是太漂亮了,韵韵的好朋友都想来参观,所以游乐园决定举办m次车展.车库里共有n辆车,从左到右依次编号为1,2,…,n,每辆车都有一个展台.刚开始每个展台都有一个唯一的高度h[i].主管已经列好一张单子:L1 R1L2 R2…Lm Rm单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri的车. 为了更加美观,展览时需要调整展台的高度,使参展所有展台的高度相等.展台的高度增加或减少1都需花费1秒时间.由于管理员只有一个人,所以只好对每个展台依次操作.每次展览结束后,展台高度自动

Treap

先推荐一篇文章和黄学长的代码http://hzwer.com/1712.html    https://wenku.baidu.com/view/c8c11e1e650e52ea55189887.html 黄学长的代码既不用指针又很短,真心推荐 Treap,顾名思义,Tree+Heap,它既满足二叉搜索树的性质,又满足堆的性质 对于二叉搜索树,如果我们把数有序加入,那么它的时间效率会退化成O(n). 我们引入一个随机数(即下文描述的修正值),使得随机数满足堆的性质(小根堆或大根堆,不一定要是完全

【贪心+Treap】BZOJ1691-[Usaco2007 Dec]挑剔的美食家

[题目大意] 有n头奶牛m种牧草,每种牧草有它的价格和鲜嫩度.每头奶牛要求它的牧草的鲜嫩度要不低于一个值,价格也不低于一个值.每种牧草只会被一头牛选择.问最少要多少钱? [思路] 显然的贪心,把奶牛和牧草都按照鲜嫩度由大到小排序,对于每奶牛把鲜嫩度大于它的都扔进treap,然后找出后继. 不过注意后继的概念是大于它且最小的,然而我们这里是可以等于的,所以应该是找cow[i].fresh-1的后继,注意一下…… 1 #include<iostream> 2 #include<cstdio&

1503: [NOI2004]郁闷的出纳员 Treap

1503: [NOI2004]郁闷的出纳员 Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 6263  Solved: 2190[Submit][Status] Description OIER公司是一家大型专业化软件公司,有着数以万计的员工.作为一名出纳员,我的任务之一便是统计每位员工的工资.这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资.如果他心情好,就可能把每位员工的工资加上一个相同的量.反之,如果心情不好,就可

数组splay ------ luogu P3369 【模板】普通平衡树(Treap/SBT)

二次联通门 : luogu P3369 [模板]普通平衡树(Treap/SBT) #include <cstdio> #define Max 100005 #define Inline __attri\ bute__( ( optimize( "-O2" ) ) ) Inline void read (int &now) { now = 0; register char word = getchar (); bool temp = false; while (wor

平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】

平衡树初阶——AVL平衡二叉查找树 一.什么是二叉树 1. 什么是树. 计算机科学里面的树本质是一个树状图.树首先是一个有向无环图,由根节点指向子结点.但是不严格的说,我们也研究无向树.所谓无向树就是将有向树的所有边看成无向边形成的树状图.树是一种递归的数据结构,所以我们研究树也是按照递归的方式去研究的. 2.什么是二叉树. 我们给出二叉树的递归定义如下: (1)空树是一个二叉树. (2)单个节点是一个二叉树. (3)如果一棵树中,以它的左右子节点为根形成的子树都是二叉树,那么这棵树本身也是二叉

【bzoj3224】Tyvj 1728 普通平衡树 平衡树的三种姿势 :splay,Treap,ScapeGoat_Tree

直接上代码 正所谓 人傻自带大常数 平衡树的几种姿势:  AVL Red&Black_Tree 码量爆炸,不常用:SBT 出于各种原因,不常用. 常用: Treap 旋转 基于旋转操作和随机数堆 但不支持区间操作. 非旋转 基于随机数堆和拆分合并操作 常数较大 Spaly 完全基于旋转 各种操作 ScapeGoat_Tree 基于a权值平衡树和压扁重构 无旋转 但不支持区间操作 PS:非旋转可以实现平衡树的可持久化,从而来套一些东西 splay #include<cstdio> #de

读车神探来了:上海车展大爆移动视频商业化图谋

作为重磅国际车展之一的上海车展已经于上月28日正式闭幕,据不完全统计,展会期间共接待观众近26万人,现场购车及订车16000余辆,销售金额近24.3亿元人民币. 文/张书乐 TMT行业观察者.游戏产业时评人,人民网.人民邮电报专栏作者 但较以往车展不同,人流最为密集的却不是展台,而是全国范围内移动视频用户们的手机屏幕.仅以一下科技(秒拍.一直播.小咖秀母公司)披露的数据为例:在一直播上,其携手闫闯.ai媚儿两个KOL,与奥迪于19日单日直播,累计观看量就达831.6万.点赞783.9万,最高在线