长乐 Day 8

今天学线段树，LCA，倍增
要走了

e

#include<bits/stdc++.h>
#define ll long long

using namespace std;
const int L=1e5+10;
struct city_date
{
    int h;
    int id;
    int pre,suc;
}al[L];
bool cmp(city_date x,city_date y)
{
    return x.h<y.h;
}
int dec(int a,int b,int i)
{
    if(!a)
        return al[b].id;
    if(!b)
        return al[a].id;
    if(al[i].h-al[a].h<=al[b].h-al[i].h)
        return al[a].id;
    else
        return al[b].id;
}
void del(int p)
{
    if(al[p].suc)
        al[al[p].suc].pre=al[p].pre;
    if(al[p].pre)
        al[al[p].pre].suc=al[p].suc;
}
int n,m;
int t_math;
int pos[L],va[L],vb[L];
int f[30][L][2];
ll ux[30][L][2],uy[30][L][2];
int ans_q;
ll ans_first,ans_second;
void cal(int s,ll x)
{
    ans_first=ans_second=0;
    int k=0;
    for(int i=t_math;i>=0;i--)
    {
        if(f[i][s][k]&&ux[i][s][k]+uy[i][s][k]<=x)
        {
            x-=ux[i][s][k]+uy[i][s][k];
            ans_first+=ux[i][s][k],ans_second+=uy[i][s][k];
            if(!i)k^=1;
            s=f[i][s][k];
        }
    }
}
int main(void)
{                                              
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&al[i].h);
        al[i].id=i;
    }
    sort(al+1,al+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        pos[al[i].id]=i;
        al[i].pre=i-1;
        al[i].suc=i+1;
    }
    al[1].pre=al[n].suc=0;
    for(int i=1;i<n;i++)
    {
        int p=pos[i],xp=al[p].pre,yp=al[p].suc;                                  
        if(xp&&(al[p].h-al[xp].h<=al[yp].h-al[p].h||!yp))      
            vb[i]=al[xp].id,va[i]=dec(al[xp].pre,yp,p);
        else
            vb[i]=al[yp].id,va[i]=dec(xp,al[yp].suc,p); 
        del(p);
    }                                                  
    for(int i=1;i<=n;i++)
    {
        if(va[i])
        {
            f[0][i][0]=va[i];
            ux[0][i][0]=abs(al[pos[i]].h-al[pos[va[i]]].h);
            uy[0][i][0]=0;  
        }
        if(vb[i])
        {
            f[0][i][1]=vb[i];
            ux[0][i][1]=0;
            uy[0][i][1]=abs(al[pos[i]].h-al[pos[vb[i]]].h);
        }   
    }
    t_math=(int)(log(n*1.0)/log(2)+1);
    for(int i=1;i<=t_math;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=0;k<=1;k++)
            {
                int l;
                if(i==1)
                    l=k^1;
                else
                    l=k;
                if(f[i-1][j][k])
                    f[i][j][k]=f[i-1][f[i-1][j][k]][l];
                if(f[i][j][k])
                {
                    ux[i][j][k]=ux[i-1][j][k]+ux[i-1][f[i-1][j][k]][l];
                    uy[i][j][k]=uy[i-1][j][k]+uy[i-1][f[i-1][j][k]][l];
                }
            }
        }
    }                            
    ll sm_a=1,sm_b=0,x;
    scanf("%lld",&x);
    for(int i=1;i<=n;i++)
    {
        cal(i,x);
        if(!ans_second)
            ans_first=1;
        if(ans_first*sm_b<ans_second*sm_a||(ans_first*sm_b==ans_second*sm_a&&al[pos[i]].h>al[pos[ans_q]].h))
            sm_a=ans_first,sm_b=ans_second,ans_q=i;
    }
    printf("%d\n",ans_q);
    scanf("%d",&m);
    while(m--)
    {
        int s;
        ll x;
        scanf("%d%lld",&s,&x);
        cal(s,x);
        printf("%lld %lld\n",ans_first,ans_second);
    }
    return 0;
}

再见