CF 675E Trains and Statistic

草稿和一些题解而已

因为指针太恶心了

所以query决定还是要试试自己yy一下

#include<cstdio>

#include<cstring>

#include<iostream>

#define ll long long

using namespace std;

int maxx[4000101],poss[4000101],n;

struct node{

	int a,posl;

};

void pushup(int rt){

    if (maxx[rt<<1]>maxx[rt<<1|1])maxx[rt]=maxx[rt<<1],poss[rt]=poss[rt<<1];

    else maxx[rt]=maxx[rt<<1|1],poss[rt]=poss[rt<<1|1];

}

void build(int l, int r, int rt) {

    if (l == r){

        maxx[rt]=0;

        poss[rt]=l;return ;

    }

    int m = (l + r) >> 1;

    build(l,m,rt<<1);

    build(m+1,r,(rt<<1)|1);

    pushup(rt);

}

void update(int p,int c, int l,int r,int rt) {

    if (l == r){

        maxx[rt]=c;return ;

    }

    int m=(l+r)>>1;

    if(p<=m)update(p,c,l,m,rt<<1);

    else update(p,c,m+1,r,(rt<<1)|1);

    pushup(rt);

}

node query(int L, int R, int l, int r, int rt){

    if (L <= l&&r<= R){

        node x;

        x.a=maxx[rt];x.posl=poss[rt];

        return x;

    }

    int m =(l+r)>>1;

    node ans;ans.a=0;

    if(L<=m){

    node kk=query(L,R,l, m,rt<<1);if(kk.a>ans.a)ans=kk;

	}

    if(R>m){

    	node kk=query(L,R,m+1,r,(rt<<1)|1);if(kk.a>ans.a)ans=kk;

	}

    return ans;

}

ll a[101000],dp[101000];

int main(){

    scanf("%d",&n);

    memset(dp,0,sizeof(dp));

    ll ans=0;

    build(1,n,1);

    for(int i=1;i<=n-1;i++)scanf("%lld",&a[i]);

    update(n,n,1,n,1);

    for(int i=n-1; i>=1;i--){

        node temp=query(i+1,a[i],1,n,1);

        dp[i]=dp[temp.posl]+(n-i)-(a[i]-temp.posl);

        ans+=dp[i];

        update(i,a[i],1,n,1);

    }

    printf("%lld",ans);

    return 0;

}

yy完毕，写了个傻逼结构体

巴特西

CF 675E Trains and Statistic

最新文章

热门文章