「Daily OI Round 1」Memory

WZH2026-07-182026-07-27

「Daily OI Round 1」Memory

考试考三道题目都是线段树题目，写爽了。

考完试发现是自己场切两个 $\textcolor{purple}{紫题}$ ，写一篇题解纪念。

题目内容：

有 $n$ 条线段 $[l_i,r_i]$ ，每条线段有颜色 $c_i$ 和权值 $w_i$ 。

一个由线段构成的集合 $M$ 合法当且仅当对于任意两条不同的线段 $i,j \in M$ ，有 $c_i=c_j$ 或 $[l_i,r_i]\cap [l_j,r_j]=\varnothing$ 。这个集合的权值为 $\sum\limits_{i\in M}w_i$ 。

求权值最大的集合的权值。

$n\le 10^5$ 。

显然 DP 题目。

为了处理交集为空的限制，先按右端点排序，然后定义 $f_{i,j}$ 为前 $i$ 条线段，集合中必须有线段 $i$ 且 $\max\{k\ |\ c_k\ne c_i\}=j$ 的最大权值。

然后枚举 $k<i$ ，那么有：

若 $c_i=c_k$ ，则对于任意的满足 $r_j<l_i$ 的 $j$ ， $f_{k,j}+w_i \to f_{i,j}$ 。
若 $c_i\ne c_k$ 且 $r_k<l_i$ ，则对于任意的 $j$ ， $f_{k,j}+w_i \to f_{i,k}$ 。

写成代码长这样：

#include <bits/stdc++.h>
using namespace std;
const int N=2010;
int n,f[N][N],g[N];
struct node{int l,r,c,w;}q[N];
bool operator<(node a,node b){return a.r<b.r;}
int main(){
    freopen("segment.in","r",stdin);
    freopen("segment.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].c,&q[i].w);
    sort(q+1,q+1+n);
    f[1][0]=q[1].w;
    g[1]=q[1].w;
    for(int i=2;i<=n;i++){
        for(int j=0;j<i;j++){
            if(q[i].c==q[j].c){
                for(int k=0;k<i;k++)
                    if(q[k].r<q[i].l)
                        f[i][k]=max(f[i][k],q[i].w+f[j][k]),g[i]=max(g[i],f[i][k]);
            }
            else if(q[j].r<q[i].l){
                f[i][j]=max(f[i][j],q[i].w+g[j]);
                g[i]=max(g[i],f[i][j]);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,g[i]);
    printf("%d\n",ans);
    return 0;
}

然后考虑优化上述 DP 。

由于转移依靠颜色分类，所以我们先对每一个颜色开一个线段树，其中线段树 $i$ 的第 $j$ 个位置表示目前最后一个颜色为 $i$ 的线段 $k$ 所对应的 $f_{k,j}$ 。特别的，对于线段树 $i$ 的满足 $c_j=i$ 的位置 $j$ 是未定义的，不过这些未定义的点不影响转移。

那么，首先，对于第一个 $c_i=c_k$ 的转移，直接二分出一个最大的 $j$ 满足 $r_j<l_i$ ，然后对线段树 $c_i$ 执行区间加 $w_i$ 就行。

然后，对于第二个 $c_i \ne c_k$ 的转移，我们可以令 $g_i=\max\{f_{i,j}\}$ ，然后对 $g$ 建立一颗线段树，然后在第一个转移下传加法标记时，同步跟 $g$ 线段树上对应节点去 $\max$ 就行，具体可以看看代码。

然后就解决了这题。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1000010,M=10000010;
int n,MX[N],am[N],ss;
struct node{int l,r,c,w;}q[N];
bool operator<(node a,node b){return a.r<b.r;}
void insert(int p,int l,int r,int x,int y){
    if(l==r)return (void)(MX[p]=y);
    int mid=(l+r)>>1;
    if(mid>=x)insert(p<<1,l,mid,x,y);
    else insert(p<<1|1,mid+1,r,x,y);
    MX[p]=max(MX[p<<1],MX[p<<1|1]);
}
namespace SEG{
    int rt[N],ls[M],rs[M],idx,mx[M],tag[M];
    void pls(int p,int q,int x){mx[p]=max(mx[p]+x,MX[q]+x);tag[p]+=x;}
    void down(int p,int q){
        if(!tag[p])return ;
        if(!ls[p])ls[p]=++idx;
        if(!rs[p])rs[p]=++idx;
        pls(ls[p],q<<1,tag[p]);
        pls(rs[p],q<<1|1,tag[p]);
        tag[p]=0;
    }
    void add(int &p,int q,int l,int r,int ql,int qr,int x){
        if(!p)p=++idx;
        if(ql<=l&r<=qr)return pls(p,q,x);
        int mid=(l+r)>>1;
        down(p,q);
        if(mid>=ql)add(ls[p],q<<1,l,mid,ql,qr,x);
        if(mid<qr)add(rs[p],q<<1|1,mid+1,r,ql,qr,x);
        mx[p]=max(mx[ls[p]],mx[rs[p]]);
    }
    int query(int p,int q,int l,int r,int ql,int qr){
        if(!p)return 0;
        if(ql<=l&&r<=qr)return mx[p];
        int mid=(l+r)>>1,res=0;
        down(p,q);
        if(mid>=ql)res=max(res,query(ls[p],q<<1,l,mid,ql,qr));
        if(mid<qr)res=max(res,query(rs[p],q<<1|1,mid+1,r,ql,qr));
        return res;
    }
}using namespace SEG;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].c,&q[i].w);
    for(int i=1;i<=n;i++)am[++ss]=q[i].c;
    sort(am+1,am+1+ss);
    ss=unique(am+1,am+1+ss)-am-1;
    for(int i=1;i<=n;i++)q[i].c=lower_bound(am+1,am+1+ss,q[i].c)-am;
    sort(q+1,q+1+n);
    for(int i=1;i<=n;i++){
        int l=0,r=i-1;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(q[mid].r<q[i].l)l=mid;
            else r=mid-1;
        }
        add(rt[q[i].c],1,0,n,0,l,q[i].w);
        insert(1,0,n,i,mx[rt[q[i].c]]);
    }
    printf("%d\n",MX[1]);
    return 0;
}

这个做法似乎题解区没有，而且常数极小。我没卡常就拿到了最优解。