4486 -- 【NOIP2015-4】数据

Mr_H出了一道信息学竞赛题，就是给n个数排序。输入格式是这样的：试题有若干组数据。每组数据的第一个是一个整数n，表示总共有n个数待排序；接下来n个整数，分别表示这n个待排序的数。
　　例如：3 4 2 –1 4 1 2 3 4，就表示有两组数据。第一组有3个数 (4,2,-1)，第二组有4个数(1,2,3,4)。可是现在 Mr_H做的输入数据出了一些问题。例如：2 1 9 3 2 按理说第一组数 据有2个数(1,9)，第二组数据有3个数，可是“3”后面并没有出现三个数，只出现了一个数“2” 而已！
　　现在Mr_H需要对数据进行修改，改动中“一步”的含义是对文件中的某一个数+1或-1，写个程序，计算最少需要多少步才能将数据改得合法。

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define _I inline
#define _R register
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define INF 0x3f3f3f3f3f3f3f3f
#define memset(x,y) memset(x,y,sizeof(x))
#define memcpy(x,y) memcpy(x,y,sizeof(x))
using namespace std;
char buf[1<<18],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
const ll N=100005;
ll n,a[N],f[N];
ll ls[N<<2],rs[N<<2],v1[N<<2],v2[N<<2];
_I ll read(){
    ll x=0;bool f=0;char ch=getchar();
    while(ch<'0'||ch>'9')f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    f&&(x=-x);
    return x;
}
_I void pushup(ll x){
    v1[x]=min(v1[x<<1],v1[x<<1|1]);
    v2[x]=min(v2[x<<1],v2[x<<1|1]);
}
void build(ll x,ll l,ll r){
    ls[x]=l;rs[x]=r;
    int mid=(l+r)>>1;
    if(l==r){v1[x]=v2[x]=INF;return;}
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
void revise(ll x,ll d,ll min1,ll min2){
    if(ls[x]>d||rs[x]<d)return;
    if(ls[x]==rs[x]){
        v1[x]=min1;v2[x]=min2;
        return;
    }
    revise(x<<1,d,min1,min2);
    revise(x<<1|1,d,min1,min2);
    pushup(x);
}
ll ask1(ll x,ll l,ll r){
    if(ls[x]>r||rs[x]<l)return INF;
    if(l<=ls[x]&&rs[x]<=r)return v1[x];
    return min(ask1(x<<1,l,r),ask1(x<<1|1,l,r));
}
ll ask2(ll x,ll l,ll r){
    if(ls[x]>r||rs[x]<l)return INF;
    if(l<=ls[x]&&rs[x]<=r)return v2[x];
    return min(ask2(x<<1,l,r),ask2(x<<1|1,l,r));
}
int main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    n=read();
    for(_R ll i=1;i<=n;++i)a[i]=read();
    memset(f,0x3f);
    build(1,1,n+1);
    revise(1,n+1,(-n-1),(n+1));
    f[n+1]=0;
    for(_R ll i=n;i>=1;--i){
        f[i]=min(ask1(1,1,min(a[i]+i,n+1))+a[i]+i+1,ask2(1,a[i]+i+1,n+1)-(a[i]+i+1));
        revise(1,i,f[i]-i,f[i]+i); 
    }
    printf("%lld",f[1]);
    return 0;
}