怎么提高开车技术_全日行车计划

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
#define db double
#define ll long long
#define inf 0x7fffffff
using namespace std;
struct node{
    int d;ll v;
}p[N];
struct note{
    int mx,mi;
}t[N*5];
bool cmp(node x,node y) {
    return x.v<y.v||x.v==y.v&&x.d<y.d;
}
db sum,ans;
int n,m,tot,x,y,k;
int h[N],a[N],b[N],w[N],g[N][18];
ll f[N][18][2],ana,anb,v[N];
void change(int v,int l,int r,int x) {
    if (l==r) {t[v].mx=t[v].mi=l;return;}
    int m=(l+r)/2;
    if (x<=m) change(v*2,l,m,x);
    else change(v*2+1,m+1,r,x);
    t[v].mx=max(t[v*2].mx,t[v*2+1].mx);
    t[v].mi=min(t[v*2].mi,t[v*2+1].mi);
}
int getmx(int v,int l,int r,int x,int y) {
    if (x>y) return 0;
    if (l==x&&r==y) return t[v].mx;
    int m=(l+r)/2;
    if (y<=m) return getmx(v*2,l,m,x,y);
    else if (x>m) return getmx(v*2+1,m+1,r,x,y);
    else return max(getmx(v*2,l,m,x,m),getmx(v*2+1,m+1,r,m+1,y));
}int getmi(int v,int l,int r,int x,int y) {
    if (x>y) return n+1;
    if (l==x&&r==y) return t[v].mi;
    int m=(l+r)/2;
    if (y<=m) return getmi(v*2,l,m,x,y);
    else if (x>m) return getmi(v*2+1,m+1,r,x,y);
    else return min(getmi(v*2,l,m,x,m),getmi(v*2+1,m+1,r,m+1,y));
}
void solve(int x,int y) {
    ana=anb=0;
    fd(j,17,0) 
        if (f[x][j][0]+f[x][j][1]<=y) {
            y-=f[x][j][0]+f[x][j][1];
            ana+=f[x][j][0];anb+=f[x][j][1];
            x=g[x][j];
        } 
    if (f[x][0][0]<=y) ana+=f[x][0][0];
}
int main() {
    scanf("%d",&n);
    fo(i,1,n) scanf("%lld",&v[i]),p[i].v=v[i],p[i].d=i;
    sort(p+1,p+n+1,cmp);v[0]=inf;
    fo(i,1,n) h[p[i].d]=++tot,w[tot]=p[i].d;
    fo(i,1,n*5) t[i].mi=n+1;
    fd(i,n,1) {
        p[1].d=getmi(1,1,n,h[i]+1,n);p[2].d=getmx(1,1,n,1,h[i]-1);
        p[3].d=getmi(1,1,n,p[1].d+1,n);p[4].d=getmx(1,1,n,1,p[2].d-1);
        fo(j,1,4) p[j].v=abs(v[i]-v[w[p[j].d]]);    
        sort(p+1,p+5,cmp);
        if (p[1].d!=0&&p[1].d!=n+1) b[i]=w[p[1].d];
        if (p[2].d!=0&&p[2].d!=n+1) a[i]=w[p[2].d];
        change(1,1,n,h[i]);         
    }
    fo(i,1,n) {
        g[i][0]=b[a[i]];
        f[i][0][0]=abs(v[i]-v[a[i]]);
        f[i][0][1]=abs(v[a[i]]-v[b[a[i]]]);
    }
    fo(j,1,17)
        fo(i,1,n) {
            g[i][j]=g[g[i][j-1]][j-1];
            f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0];
            f[i][j][1]=f[i][j-1][1]+f[g[i][j-1]][j-1][1];
        }
    scanf("%d",&x);ans=inf;
    fo(i,1,n) {
        solve(i,x);
        if (!anb) sum=inf;else sum=ana*1.0/anb;
        if (sum<ans||sum==ans&&v[i]>v[k]) ans=sum,k=i;
    }
    printf("%d\n",k);
    for(scanf("%d",&m);m;m--) {
        scanf("%d%d",&x,&y);
        solve(x,y);
        printf("%lld %lld\n",ana,anb);  
    }
}