原题链接

题解

只要求最大值和最小值的差尽量小，也就意味着，权值位于最大值和最小值之间的线段可以任意取

也就是说，我们将线段按权值排序，我们只需要取其中一段区间，然后查看是否覆盖了完整的区间，如果是，判断能否更新最小值

这样看起来是两次for循环找区间，对于查看是否完整覆盖区间的部分，看起来是对区间内每个点+1，然后查看全域最小值

这样看起来是 \(O(n^4)\) 的做法

优化：
对于区间修改，区间查找，我们可以用线段树维护，时间复杂度来到 \(O(n^3 logn)\)

再度优化：我们可以遍历 \(i\) ，查看以 \(i\) 为右端点时，且能覆盖全域的最大左端点 \(l\)，由于这样的左端点是递增的，所以我们可以用双指针维护，时间复杂度来到 \(O(nlogn)\)

双指针上楼：我们发现，在遍历 \(i\) 查找以 \(i\) 为左/右端点时，满足条件的 （ 最大/小） 左/右 端点，可以用双指针维护，只要这样的 左/右端点 满足单调性

code

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll inf=1e18;
ll tree[4000006]={0};
struct node
{
    ll l,r,v;
}seg[300005];
bool cmp(node a,node b)
{
    return a.v<b.v;
}

ll lazytag[4000006]={0};

void pushdown(ll node,ll l,ll r)
{
    tree[node]+=lazytag[node];
    if(l!=r)
    {
        lazytag[node*2]+=lazytag[node];
        lazytag[node*2+1]+=lazytag[node];
    }

    lazytag[node]=0;
}

void update(ll node,ll l,ll r,ll x,ll y,ll val)
{
    if(lazytag[node]) pushdown(node,l,r);

    if(l>y||r<x) return ;

    if(l>=x&&r<=y)
    {
        lazytag[node]=val;
        pushdown(node,l,r);
        return;
    }

    ll mid=(l+r)/2;
    update(node*2,l,mid,x,y,val);update(node*2+1,mid+1,r,x,y,val);

    tree[node]=min(tree[node*2],tree[node*2+1]);
}

void solve()
{
    ll n,m;
    cin>>n>>m;

    for(ll i=1;i<=n;i++)
    {
        cin>>seg[i].l>>seg[i].r>>seg[i].v;
    }

    sort(seg+1,seg+1+n,cmp);

    ll itl=1;

    ll ans=inf;
    for(ll itr=1;itr<=n;itr++)
    {
        update(1,1,m-1,seg[itr].l,seg[itr].r-1,1);
        while(itl<=itr&&tree[1]>0)
        {
            update(1,1,m-1,seg[itl].l,seg[itl].r-1,-1);
            itl++;
        }

       // printf("itl:%d  itr:%d\n",itl,itr);
        if(itl!=1) ans=min(ans,seg[itr].v-seg[itl-1].v);
    }
    cout<<ans;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll TT=1;
    //cin>>TT;
    while(TT--) solve();
    return 0;
}