CF1250C Trip to Saint Petersburg

思路

线段树入门题。

不妨固定一个右端点 \(r\)，把所有右端点小于 \(r\) 的区间都在 \(1\) 至此区间的左端点处 update 一个 \(p\)，然后每次都给区间 \(1\) 至 \(i\) update 一个 \(-k\)，最后查询区间 \(\max\) 即可。

代码

//A tree without skin will surely die.

//A man without face is invincible.

#include<bits/stdc++.h>

using namespace std;

#define int long long

int const N=2e5+10;

struct answ{int first,second,id;};

struct node{int x,y;};

vector<answ>a[N];

vector<int>anss;

struct Segment_Tree{

    #define ls (x<<1)

    #define rs (x<<1|1)

    #define mid ((l+r)>>1)

    int c[N<<2],lazy[N<<2],pl[N<<2];

    inline void build(int x,int l,int r){

        if (l==r){pl[x]=l;return;}

        build(ls,l,mid);build(rs,mid+1,r);

        pl[x]=pl[ls];

    }

    inline void pushdown(int x){

        c[ls]+=lazy[x];c[rs]+=lazy[x];

        lazy[ls]+=lazy[x];lazy[rs]+=lazy[x];

        lazy[x]=0;

    }

    inline void pushup(int x){

        if (c[ls]>c[rs]) c[x]=c[ls],pl[x]=pl[ls];

        else c[x]=c[rs],pl[x]=pl[rs];

    }

    inline void update(int x,int l,int r,int ll,int rr,int v){

        if (l==r){pl[x]=l;}

        if (ll<=l && r<=rr){c[x]+=v,lazy[x]+=v;return;}

        pushdown(x);

        if (ll<=mid) update(ls,l,mid,ll,rr,v);

        if (mid<rr) update(rs,mid+1,r,ll,rr,v);

        pushup(x);

    }

    inline node query(int x,int l,int r,int ll,int rr){

        if (l==r) pl[x]=l;

        if (ll<=l && r<=rr) return {c[x],pl[x]};

        pushdown(x);node res;res.x=res.y=0;

        if (ll<=mid) res=query(ls,l,mid,ll,rr);

        if (mid<rr){

            node qq=query(rs,mid+1,r,ll,rr);

            if (qq.x>res.x) res=qq;

        }

        pushup(x);

        return res;

    }

}T;

signed main(){

    int n,k;cin>>n>>k;int maxr=0;

    for (int i=1;i<=n;++i){

        int l,r,p;cin>>l>>r>>p;

        a[r].push_back({l,p,i});maxr=max(maxr,r);

    }

    T.build(1,1,maxr);

    int ans=0,ansl=0,ansr=0;

    for (int i=1;i<=maxr;++i){

        T.update(1,1,maxr,1,i,-k);

        for (auto j:a[i]) T.update(1,1,maxr,1,j.first,j.second);

        node reply=T.query(1,1,maxr,1,i);

        if (reply.x>ans) ans=reply.x,ansl=reply.y,ansr=i;

    }

    //输出

    return 0;

}

巴特西

CF1250C Trip to Saint Petersburg

思路

代码

最新文章

热门文章