[POI2005]AUT-The Bus 树状数组维护最大前缀和

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=100000+3;

int x[N], y[N], Y[N], A[N], nums[N];

int C[N];

int cmp(int i,int j){

    if(x[i]==x[j])return y[i]<y[j];

    return x[i]<x[j];

}

int lowbit(int t){return t&(-t);}

void update(int t,int delta)

{

    while(t<N) C[t]=max(C[t],delta),  t+=lowbit(t);

}

int query(int t){

    int tmp=-1;

    while(t>0)tmp=max(tmp,C[t]), t-=lowbit(t);

    return tmp;

}

int main()

{

    //freopen("in.txt","r",stdin);

    int n,m,k,ans=0;

    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=k;++i)scanf("%d%d%d",&y[i],&x[i],&nums[i]), Y[i]=y[i];

    for(int i=1;i<=k;++i)A[i]=i;

    sort(A+1,A+1+k,cmp);

         sort(Y+1,Y+1+k);

    for(int i=1;i<=k;++i)

    {

        int cur=A[i];

        y[cur]=lower_bound(Y+1,Y+1+k, y[cur])-Y;

        int h=query(y[cur])+nums[cur];

        ans=max(ans,h);

        update(y[cur], h);

    }

    printf("%d",ans);

    return 0;

}

巴特西

[POI2005]AUT-The Bus 树状数组维护最大前缀和

最新文章

热门文章