「vijos1459」车展
描述
遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办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）。
输出格式
一个正整数，调整展台总用时的最小值。
限制
各个测试点1s
提示
对于50％的数据 n≤500，m≤1000；
对于80％的数据 n≤1000，m≤100000；
对于100％的数据n≤1000，m≤200000；
答案在2^64以内。
题解
用treap n^2logn预处理中位数
当做模板练习
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define eps 1e-8 #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt,root; ll tot,anstot,tmp,num; int h[1005],ans[1005][1005]; struct treap{ int rnd,size,w,l,r,val; ll sum; }t[1005]; void update(int k) { t[k].size=t[t[k].l].size+t[t[k].r].size+t[k].w; t[k].sum=t[t[k].l].sum+t[t[k].r].sum+t[k].val*t[k].w; } void rturn(int &k) { int tmp=t[k].l;t[k].l=t[tmp].r;t[tmp].r=k; update(k);update(tmp);k=tmp; } void lturn(int &k) { int tmp=t[k].r;t[k].r=t[tmp].l;t[tmp].l=k; update(k);update(tmp);k=tmp; } void insert(int &k,int x) { if(k==0) { k=++cnt; t[k].size=t[k].w=1; t[k].sum=t[k].val=x;t[k].rnd=rand(); t[k].l=t[k].r=0; return; } t[k].size++;t[k].sum+=x; if(t[k].val==x)t[k].w++; else if(x>t[k].val) { insert(t[k].r,x); if(t[t[k].r].rnd<t[k].rnd)lturn(k); } else { insert(t[k].l,x); if(t[t[k].l].rnd<t[k].rnd)rturn(k); } } int query(int k,int val) { if(val<=t[t[k].l].size) return query(t[k].l,val); else if(val>t[t[k].l].size+t[k].w) { tmp+=t[t[k].l].sum+t[k].w*t[k].val; num+=t[t[k].l].size+t[k].w; return query(t[k].r,val-t[t[k].l].size-t[k].w); } else { tmp+=t[t[k].l].sum; num+=t[t[k].l].size; return t[k].val; } } void pre() { for(int i=1;i<=n;i++) { cnt=root=tot=0; for(int j=i;j<=n;j++) { tot+=h[j]; insert(root,h[j]); tmp=num=0; int ave=query(root,(j-i+2)/2); ans[i][j]+=num*ave-tmp; ans[i][j]+=tot-tmp-(j-i+1-num)*ave; } } } int main() { n=read();m=read(); for(int i=1;i<=n;i++)h[i]=read(); pre(); for(int i=1;i<=m;i++) { int l=read(),r=read(); anstot+=ans[l][r]; } cout<<anstot; return 0; } |
Subscribe
计数器 9787188
OI 课件=>
OI 课件=>