比较迷糊，比较乱搞。
我们考虑从上往下进行 \(dp\)，\(dp_i\) 表示从顶上水槽 \(i\) 最多的流量。然后我们发现，每个高度，能用来进行转移的区间一定没有被完全覆盖。也就是，只有在遮挡关系中被覆盖的区间可能被用来转移。
同时，每个区间还是有要求的，比如 \([1,3]\) 的 \([2,3]\) 部分后来被覆盖了，但是 \([1,2]\) 依旧可以转移，因为 \([2,3]\) 不会成为中间障碍，而 \([1,3]\) 就不可以。
所以我们发现，每个颜色段区间还存在转移区间，初始是 \([-\infty,+\infty]\)，每次被断开或部分遮挡的时候，就更改转移区间为被遮挡部分和剩余部分的交界。而只有不超过转移区间的新区间，才能使用这个区间进行转移。
我们考虑 ODT 维护区间，每次找到所有和当前水槽区间存在交集的区间，提取出来，看转移区间是否符合进行转移。然后进行区间推平，将当前的 \([l,r]\) 全部推平为自己，两边出现断开，更新转移区间。
这题出现的时候还没有 ODT 所以不用担心 ODT 会被卡
我们发现这题的操作是比较均匀的，每次一次查询一次推平。那么它的复杂度就是有保证的。我们发现，每次最多加入新的三个区间（新区间，左端点，右端点）。所以被加入的区间总和就是 \(O(n)\) 的。而每次访问之后一定会被推平，所以每个元素只会被访问一次。那么复杂度就有保证是 \(O(n\log n)\) 的。
int n,t,h[100005],l[100005],r[100005],to[100005];
int dp[100005];
struct node{
int id,l,r,L,R;
node(){
id=l=r=L=R=0;
}
node(int _id,int _l,int _r){
id=_id,l=_l,r=_r,L=-1e9,R=1e9;
}
node(int _id,int _l,int _r,int _L,int _R){
id=_id,l=_l,r=_r,L=_L,R=_R;
}
bool operator <(const node b)const{
return l<b.l;
}
};
set<node>se;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>t;
rp(i,n)cin>>h[i]>>l[i]>>r[i];
n++,h[n]=0,l[n]=-1e9,r[n]=1e9;
l[n+1]=-1e9,r[n+1]=1e9;
rp(i,n)to[i]=i;
sort(to+1,to+1+n,[](int x,int y){
return h[x]>h[y];
});dp[n+1]=2e9;
se.insert(node(n+1,-1e9,1e9));
rp(o,n){
int i=to[o],x=l[i],y=r[i];
vt<node>v;
auto k=se.lower_bound({i,x,y});
if(k!=se.begin()){
k--;
if(k->r>x){
v.pb(*k);
se.erase(k);
}
}k=se.lower_bound({i,x,y});
while(k!=se.end()&&k->l<y){
v.pb(*k);se.erase(k);
k=se.lower_bound({i,x,y});
}
for(auto k:v)if(k.L<=x&&y<=k.R){
dp[i]=max(dp[i],min(dp[k.id],min(y,k.r)-max(x,k.l)));
}
for(auto k:v){
if(k.l<x){
se.insert({k.id,k.l,x,k.L,x});
}
if(k.r>y){
se.insert({k.id,y,k.r,y,k.R});
}
}se.insert({i,x,y});
}cout<<dp[n]<<endl;
return 0;
}
//Crayan_r