权值分块就是快……Rank5……
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 #define N 38001 6 #define INF 2147483647 7 #define min(a,b) (((a)<(b))?(a):(b)) 8 struct Point{int v,p;}t[N]; 9 bool operator < (const Point &a,const Point &b){return a.v<b.v;} 10 int n,ma[N],a[N],en,sum,sz,l[201],r[201],sumv[201],num[N],b[N],ans; 11 inline void R(int &x){ 12 char c=0;int f=1; 13 for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1; 14 for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0'); 15 x*=f; 16 } 17 void makeblock() 18 { 19 sz=sqrt(en); if(!sz) sz=1; 20 for(sum=1;sum*sz<en;sum++) 21 { 22 l[sum]=r[sum-1]+1; 23 r[sum]=sz*sum; 24 for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 25 } 26 l[sum]=r[sum-1]+1; 27 r[sum]=en; 28 for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 29 } 30 inline void Insert(const int &x){b[x]++; sumv[num[x]]++;} 31 inline int Next(const int &x) 32 { 33 if(b[x]>1) return x; 34 for(int i=x+1;i<=r[num[x]];i++) if(b[i]) return i; 35 for(int i=num[x]+1;i<=sum;i++) if(sumv[i]) 36 for(int j=l[i];;j++) 37 if(b[j]) return j; 38 return INF; 39 } 40 inline int Pre(const int &x) 41 { 42 if(b[x]>1) return x; 43 for(int i=x-1;i>=l[num[x]];i--) if(b[i]) return i; 44 for(int i=num[x]-1;i>=1;i--) if(sumv[i]) 45 for(int j=r[i];;j--) 46 if(b[j]) return j; 47 return INF; 48 } 49 int main() 50 { 51 R(n); for(int i=1;i<n;i++) 52 { 53 R(t[i].v); 54 t[i].p=i; 55 } 56 if(scanf("%d",&t[n].v)==EOF) t[n].v=0; t[n].p=n; 57 sort(t+1,t+n+1); 58 ma[a[t[1].p]=++en]=t[1].v; 59 for(int i=2;i<=n;i++) 60 { 61 if(t[i].v!=t[i-1].v) en++; 62 ma[a[t[i].p]=en]=t[i].v; 63 } makeblock(); 64 Insert(a[1]); ans+=ma[a[1]]; 65 for(int i=2;i<=n;i++) 66 { 67 Insert(a[i]); 68 int Up=Next(a[i]),Down=Pre(a[i]); 69 if(Up==INF) ans+=(ma[a[i]]-ma[Down]); 70 else if(Down==INF) ans+=(ma[Up]-ma[a[i]]); 71 else ans+=min(ma[Up]-ma[a[i]],ma[a[i]]-ma[Down]); 72 } printf("%d ",ans); 73 return 0; 74 }