AT题解——AT4544 Intervals

· · 题解

据说是套路题。套路在于在右端点处计算贡献，这样不重不漏。

设 dp_{i,j} 为前 i 个位置中，上一个 1 放置在 j 处的最大答案。 首先有：

dp_{i,i}=\max_{j=1}^{i-1}\{dp_{i-1,j}\}

同时存在 i 是第一个为 1 的位置，所以要和 0 取 \max，排除负贡献的情况。

接下来考虑普通的转移，枚举到右端点 i 时，对于所有的 k,r_k=i，若 l_k\ge j，就会产生贡献。于是转移方程：

dp_{i,j}=dp_{i-1,j}+\sum_{l_k\ge j,r_k=i} a_k

当然对于 dp_{i,i}，转移应当是从其本身得来的。

复杂度是 O(n^2) 的。

发现后面的部分每条规则只被计算一次，算上区间加应当和枚举状态同级，考虑如何把枚举状态以及区间修改优化。

可以使用线段树，这样便可以对于每一个 k，批量修改所有产生贡献的 dp_{i,j}。

int n,m;
struct node{
    int l,r;
    ll w;
    node()=default;
    node(int l_,int r_,ll w_):l(l_),r(r_),w(w_){}
}a[maxn];
vector<node> gr[maxn];
struct SegmentTree{
    #define mid ((l+r)>>1)
    #define lson rt<<1,l,mid
    #define rson rt<<1|1,mid+1,r
    ll mx[maxn<<2],tag[maxn<<2];
    void build(int rt,int l,int r){
        mx[rt]=0,tag[rt]=0;
        if(l==r) return;
        build(lson),build(rson);
    } 
    void push_down(int rt){
        if(tag[rt]){
            tag[rt<<1]+=tag[rt],tag[rt<<1|1]+=tag[rt];
            mx[rt<<1]+=tag[rt],mx[rt<<1|1]+=tag[rt];
            tag[rt]=0;
        }
    }
    void update(int rt,int l,int r,int pl,int pr,ll k){
        if(pl<=l&&r<=pr){
            mx[rt]+=k,tag[rt]+=k;
            return;
        }
        push_down(rt);
        if(pl<=mid) update(lson,pl,pr,k);
        if(pr>mid) update(rson,pl,pr,k);
        mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
    }
    #undef mid
    #undef lson
    #undef rson
}S;
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i){
        int l=read(),r=read(),w=read();
        a[i]=node(l,r,w);
        gr[r].push_back(a[i]);
    }
    S.build(1,1,n);
    for(int r=1;r<=n;++r){
        S.update(1,1,n,r,r,max(S.mx[1],0ll));
        for(int j=0;j<gr[r].size();++j){
            int l=gr[r][j].l;
            ll w=gr[r][j].w;
            S.update(1,1,n,l,r,w);
        }
    }
    printf("%lld\n",max(S.mx[1],0ll));
    return 0;
}