首页 > 代码库 > 车展(vijos P1459)
车展(vijos P1459)
描述
遥控车是在是太漂亮了,韵韵的好朋友都想来参观,所以游乐园决定举办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以内。
/* 可持续性线段树求中位数 */#include<cstdio>#include<iostream>#include<algorithm>#include<cstdlib>#define N 1010#define ll long longusing namespace std;ll a[N],co[N],root[N],n,m,cnt;struct node{ ll lc,rc,sum;};node t[N*100];ll read(){ char c=getchar();ll num=0,flag=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)flag=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*flag;}ll build(ll v,ll x,ll y){ ll k=++cnt;t[k].sum=v; t[k].lc=x;t[k].rc=y; return k;}void insert(ll &root,ll pre,ll l,ll r,ll pos){ root=build(t[pre].sum+1,t[pre].lc,t[pre].rc); if(l==r)return; ll mid=(l+r)/2; if(pos<=mid)insert(t[root].lc,t[pre].lc,l,mid,pos); else insert(t[root].rc,t[pre].rc,mid+1,r,pos);}ll query(ll x,ll y,ll l,ll r,ll k){ if(l==r)return l; ll mid=(l+r)/2; ll sum=t[t[y].lc].sum-t[t[x].lc].sum; if(k<=sum)return query(t[x].lc,t[y].lc,l,mid,k); else return query(t[x].rc,t[y].rc,mid+1,r,k-sum);}int main(){ n=read();m=read(); for(ll i=1;i<=n;i++) { a[i]=read(); co[i]=a[i]; } sort(co+1,co+1+n); ll num=unique(co+1,co+n+1)-co-1; for(ll i=1;i<=n;i++) { ll pos=lower_bound(co+1,co+num+1,a[i])-co; insert(root[i],root[i-1],1,num,pos); } ll ans=0; for(ll i=1;i<=m;i++) { ll l=read(),r=read(),k=(l+r)/2-l+1; ll pos=query(root[l-1],root[r],1,num,k); ll tot=0; for(ll j=l;j<=r;j++) tot+=abs(co[pos]-a[j]); ans+=tot; } cout<<ans; return 0;}
车展(vijos P1459)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。