P9594 Sol
线段树优化 dp。
我们一般见到的 dp 优化题如果是更注重优化的话，那数据范围根本想不出来这是一道 dp 题，这个时候就要敢想、敢推，才能摸到正解的边缘。
很多 dp 题都是基于贪心的，例如先按贪心排序，再在这个顺序上转移，亦或是某个转移的值不需要枚举很大的范围，其中都有可能用到了贪心思想。
本题就是前者。
其实遇到那种答案跟顺序没什么关系的题通常都要先排序。
按左端点排完序了之后我们发现可以轻松设出状态：设
解释就是我们只关心右端点和颜色。
发现左右端点的具体值没什么用，只关心大小关系，于是离散化。
转移也比较好搞：
由于我们钦定了转移顺序是左端点由小到大，这三个转移得以成立。
加上优化就比较简单了，线段树区间
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;
}
（在博客页面看