Intervals 题解

· · 题解

Intervals

题目大意

给定 m 条形如 (l_i,r_i,a_i) 的规则，你需要求出一个长为 n 的分数最大的 01 串的分数，其中一个 01 串 A 的分数被定义为

\sum_{i=1}^ma_i[\sum_{j=l_i}^{r_i}A_j\ge 1]

思路分析

考虑 DP。

设 f_{i,j} 表示考虑 01 串的前 i 个数，最后一个 1 放在 j 时的最大分数，首先有一个特殊的转移：

f_{i,i}=\max_{j<i}(f_{i-1,j})

也就是枚举前 i-1 个数中上一个 1 放在哪个位置，对所有可能的情况取 \max。

考虑一般情况：

从 i-1 转移到 i，新的贡献只从所有右端点为 i 的区间产生，考虑到产生贡献的条件是至少包含一个 1，而最后的 1 位于 j，故只有这个区间包含 j 的时候才会产生贡献，故有状态转移方程：

f_{i,j}=f_{i-1,j}+\sum_{k=1}^m[l_k\le j][r_k=i]a_k

直接转移的时间复杂度是 O(n^3) 的，不过可以通过将区间排序加双指针做到均摊 O(n^2)，但依然无法通过，考虑优化。

首先发现转移只与上一维有关，可以直接优化掉 i，使空间复杂度降为 O(n)。

考虑哪些区间对 f 产生贡献，不难发现，只要区间包含 f 的端点，它就对 f 有贡献，那么我们就可以把 f 丢到线段树上，对于每一个区间进行一次线段树上的区间加操作，维护区间的最大值即可。

注意 01 串全为 0 时其分数为 0，故不可能产生负分数，所有的分数需要和 0 取 \max。

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;
const int N=200200;
#define int long long
#define mid ((l+r)>>1)

int n,m,in1,in2,in3;

struct Node{
    int l,r,a;
}a[N];
vector<Node> v[N];

struct ST{
    int maxn[N<<2],tag[N<<2];
    void change_t(int p,int k){
        maxn[p]+=k;tag[p]+=k;
    }
    void push_down(int p){
        if(!tag[p]) return ;
        change_t(p<<1,tag[p]);
        change_t(p<<1|1,tag[p]);
        tag[p]=0;
    }
    void change(int p,int l,int r,int x,int y,int k){
        if(x<=l&&r<=y){change_t(p,k);return ;}
        push_down(p);
        if(x<=mid) change(p<<1,l,mid,x,y,k);
        if(y>mid) change(p<<1|1,mid+1,r,x,y,k);
        maxn[p]=max(maxn[p<<1],maxn[p<<1|1]);
    }
}tree;

signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&in1,&in2,&in3);
        a[i]=Node{in1,in2,in3};
        v[in2].push_back(a[i]);
    }
    for(int i=1;i<=n;i++){
        tree.change(1,1,n,i,i,max(tree.maxn[1],0ll));
        for(auto it:v[i])
            tree.change(1,1,n,it.l,i,it.a);
    }
    cout<<max(tree.maxn[1],0ll)<<'\n';
    return 0;
}