自动搬运

查看原文

来自洛谷，原作者为

	一只绝帆 就让我在风儿中独舞，唱着只有云儿能听懂的哀歌。

搬运于2025-08-24 22:49:56，当前版本为作者最后更新于2023-09-04 22:41:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

线段树优化 dp。

我们一般见到的 dp 优化题如果是更注重优化的话，那数据范围根本想不出来这是一道 dp 题，这个时候就要敢想、敢推，才能摸到正解的边缘。

很多 dp 题都是基于贪心的，例如先按贪心排序，再在这个顺序上转移，亦或是某个转移的值不需要枚举很大的范围，其中都有可能用到了贪心思想。

本题就是前者。

其实遇到那种答案跟顺序没什么关系的题通常都要先排序。

按左端点排完序了之后我们发现可以轻松设出状态：设 $f_{i,c}$ 为考虑所有颜色为 $c$ 的元素、最右端点在 $i$ 的最大权值。

解释就是我们只关心右端点和颜色。

发现左右端点的具体值没什么用，只关心大小关系，于是离散化。

转移也比较好搞：

$$f_{r_i,c}\xleftarrow{\max} w_i+\max_{j=1}^{l_i-1}\max_kf_{j,k}\\f_{r_i,c}\xleftarrow{\max}w_i+\max_{j=1}^{r_i}f_{j,c}\\\forall j>r_i,f_{j,c}\xleftarrow+w_i $$

由于我们钦定了转移顺序是左端点由小到大，这三个转移得以成立。

加上优化就比较简单了，线段树区间 $+$ 区间 $\max$ 即可。

Code：

#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##end(b);i<=i##end;i++)
#define gc getchar
#define l(x) ls[x]
#define r(x) rs[x]
#define mid (L+R>>1)
using namespace std;
int read() {
	int s=0;char c=gc(),w=0;
	while(c<'0'||c>'9') w|=c=='-',c=gc();
	while(c>='0'&&c<='9') s=s*10+(c^48),c=gc();
	return w?-s:s;
} const int N=1e5+5,C=2e7+5,X=1e9+5;unordered_map<int,int> mp;
int n,hnt,snt,mx[C],l(C),r(C),tg[C],RT,rt[N],ans,V[N<<1],vnt,pre;vector<int> v[N<<1];
struct S {int l,r,c,w;bool operator<(const S &b) {return l==b.l?r<b.r:l<b.l;}} a[N];
int hsh(int x) {if(!mp.count(x)) mp[x]=++hnt;return mp[x];}
void up(int d) {mx[d]=max(mx[l(d)],mx[r(d)]);}
void pr(int &d,int t) {if(!d) d=++snt;mx[d]+=t;tg[d]+=t;}
void down(int &d) {if(tg[d]) pr(l(d),tg[d]),pr(r(d),tg[d]),tg[d]=0;} 
void add(int l,int r,int b,int L,int R,int &d) {
	if(R<l||r<L) return;if(!d) d=++snt;if(l<=L&&R<=r) return pr(d,b);
	down(d);add(l,r,b,L,mid,l(d));add(l,r,b,mid+1,R,r(d));up(d);
}
void ins(int x,int b,int L,int R,int &d) {
	if(!d) d=++snt;if(L==R) return mx[d]=max(mx[d],b),void();
	down(d);x<=mid?ins(x,b,L,mid,l(d)):ins(x,b,mid+1,R,r(d));up(d);
}
int q(int l,int r,int L,int R,int &d) {
	if(r<L||R<l) return 0;if(l<=L&&R<=r) return mx[d];
	return down(d),max(q(l,r,L,mid,l(d)),q(l,r,mid+1,R,r(d)));
}
int main() {
	F(i,1,n=read()) a[i]={V[++vnt]=read(),V[++vnt]=read(),hsh(read()),read()};
	sort(a+1,a+n+1);sort(V+1,V+vnt+1);vnt=unique(V+1,V+vnt+1)-V-1;
	int p=1;F(i,1,n) {
		a[i].l=lower_bound(V+1,V+vnt+1,a[i].l)-V;a[i].r=lower_bound(V+1,V+vnt+1,a[i].r)-V;
		v[a[i].r].push_back(a[i].c);
		while(p<a[i].l) {for(int c:v[p]) pre=max(pre,q(1,a[i].l-1,1,vnt,rt[c]));p++;}
		int Q=max(pre,q(1,a[i].r,1,vnt,rt[a[i].c]))+a[i].w;
		ins(a[i].r,Q,1,vnt,rt[a[i].c]);ans=max(ans,Q);
		add(a[i].r+1,X,a[i].w,1,vnt,rt[a[i].c]);ans=max(ans,mx[rt[a[i].c]]);
	} cout<<ans<<endl;
	return 0; 
}

（在博客页面看 $\LaTeX$ 并没有问题，但是管理审的时候表示 $\LaTeX$ 炸了/kk。）