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;
}