【题解】「MSTOI-R1」超速检测II

· · 题解

这里是验题人的超级复杂 tj。这个题我的评价是

不带修的问题：

于是我们可以有一个很显然的 dp，f_i 表示当前考虑到点 i，最大的 \sum S 是多少。转移是 f_{i}=\max (f_{i-1},f_{l}+v)，其中 l,v 是以 i 为 r 的一个速度限制。复杂度 O(d(m+n))。

对结论的证明：\ 按照右端点大小顺序考虑每个限制。每次新考虑一个限制，然后我们只需要满足当前考虑过的限制是合法的即可。\ 不妨令 T 为与当前加入的这个限制 [l,r] 有交的限制集合。\ 如果转移取的是 f_l+v，那说明 v 可以满足 T 中的限制，而 f_l 满足了前面的限制。\ 如果转移取的是 f_{i-1}，那说明当前限制被 T 中的满足了。

考虑原问题：

对于一个询问，发现我们不能选 [l,r]。所以如果询问的 V 比原来的大，那么就好搞。否则我们需要特殊处理。考虑我们再做一个反着 dp 的数组 g_i，那么分讨：

先离线，然后对点扫描线。以 i 结尾的可能有询问或原本的限制。把询问按照左端点大小排序，把以 i 结尾的询问加入线段树。对于原本的限制 [l,i,V]，我们把左端点在 [l+1,i] 内的询问用 f_l+g_i+V 进行更新。

然后我们按此操作，将整个序列反过来再做一边，于是对于一个原本的限制 [l,r,V]，我们对于 l\le u\le v\le r，且满足 u\neq l \mathrm{\ or\ } v\neq r 的询问进行了更新。

于是我们完成了这个题目。复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL N=1e5+10;
LL n,m,d,f[N],g[N],st[N][17],lg[N],ans[N],zsw[N];
vector<PII> L[N],R[N];
LL query(LL l,LL r)
{
    LL t=lg[r-l+1];
    return l>r?0:max(st[l][t],st[r-(1<<t)+1][t]);
}

namespace SegT
{
    struct node { LL l,r,val,tag; }t[N<<2];
    struct zxz { LL l,r,id; }a[N];
    vector<LL> ad[N];
    #define ls (k<<1)
    #define rs (k<<1|1)
    #define mid (l+r>>1)
    bool cmp(zxz a,zxz b) { return a.l<b.l; }
    void addtag(LL k,LL v)
    {
        t[k].tag=max(t[k].tag,v);
        t[k].val=max(t[k].val,v);
    }
    void pushdown(LL k)
    {
        addtag(ls,t[k].tag);
        addtag(rs,t[k].tag);
        t[k].tag=0;
    }
    void modify(LL k,LL l,LL r,LL L,LL R,LL mx)
    {
        if(l>R||L>r) return;
        if(L<=l&&r<=R) return addtag(k,mx);
        pushdown(k);
        modify(ls,l,mid,L,R,mx);
        modify(rs,mid+1,r,L,R,mx);
    }
    void miku(LL k,LL l,LL r,LL x)
    {
        if(l>x||r<x) return;
        if(l==r) return t[k].val=0,void();
        pushdown(k);
        miku(ls,l,mid,x);
        miku(rs,mid+1,r,x);
    }
    LL query(LL k,LL l,LL r,LL x)
    {
        if(l>x||r<x) return 0;
        if(l==r) return t[k].val;
        pushdown(k);
        return max(query(ls,l,mid,x),query(rs,mid+1,r,x));
    }
    void solve()
    {
        for(int i=1;i<=n;i++) zsw[i]=0,ad[i].clear();
        for(int i=1;i<=d;i++) miku(1,1,d,i);
        sort(a+1,a+d+1,cmp);
        for(LL i=1;i<=d;i++) zsw[a[i].l]=max(zsw[a[i].l],i);
        for(int i=1;i<=n;i++) zsw[i]=max(zsw[i],zsw[i-1]);
        for(int i=1;i<=d;i++) ad[a[i].r].push_back(i);
        for(int i=1;i<=n;i++)
        {
            for(auto j:ad[i]) miku(1,1,d,j);
            for(auto j:L[i]) 
                modify(1,1,d,zsw[j.first]+1,zsw[i],f[j.first]+j.second+g[i]);
        }
        for(int i=1;i<=d;i++)
            ans[a[i].id]=max(ans[a[i].id],query(1,1,d,i));
    }
}
using namespace SegT;
int main()
{
    scanf("%lld%lld%lld",&n,&m,&d);
    for(int i=1;i<=m;i++)
    {
        LL l,r,v;
        scanf("%lld%lld%lld",&l,&r,&v);
        L[r].push_back({l,v});
        R[l].push_back({r,v});
    }
    for(int i=1;i<=n;i++,f[i]=f[i-1])
        for(auto j:L[i]) f[i]=max(f[i],f[j.first]+j.second);
    for(int i=n;i>=1;i--,g[i]=g[i+1])
        for(auto j:R[i]) g[i]=max(g[i],g[j.first]+j.second);
    for(int i=1;i<=n;i++) st[i][0]=f[i]+g[i];
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            st[j][i]=max(st[j][i-1],st[j+(1<<i-1)][i-1]);
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int i=1;i<=d;i++)
    {
        LL l,r,v;
        scanf("%lld%lld%lld",&l,&r,&v);
        a[i]=(zxz){l,r,i};
        ans[i]=max(f[l]+v+g[r],query(l+1,r-1));
    }
    solve();
    reverse(f+1,f+n+1);
    reverse(g+1,g+n+1);
    swap(f,g);
    for(int i=1;i<=n;i++) L[i].clear();
    for(int i=1;i<=n;i++)
        for(auto j:R[i])
            L[n-i+1].push_back({n-j.first+1,j.second});
    for(int i=1;i<=d;i++) a[i]=(zxz){n-a[i].r+1,n-a[i].l+1,a[i].id};
    solve();
    for(int i=1;i<=d;i++) printf("%lld\n",ans[i]);
    return 0;
}