传送门

对区间按照左端点进行排序

那么对于每条线段的右端点

因为左端点是递增的m往右二分出一个区间的线段都是不相交的

但是还需要找到固定长度的

做法

枚举每个线段,把这条线段当作右端的线段,去左端的线段里找最小值

维护两个线段数组和

按照区间左端点小到大排序,按照右端点小到大排序

现在考虑线段和哪些线段不相交

如果一条线段的右端点小于那么就不相交

或者一条线段的左端点大于(这个不考虑,我们只把每条线段作为右边的线段)

由于数组右端点升序,所以可以双指针更新当前的数组

表示不与当前线段相交且长度为的最小花费

那么每次轮到数组的第条线段作为右边的线段去左边找最大值时

所有左边满足条件的线段一定都去更新过了数组

所以是正确的

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5+10;
int cost[maxn],n,x;
struct XIAN
{
    int l,r,cost;
}a[maxn],b[maxn];
bool com1(XIAN a,XIAN b){ return a.l<b.l; }
bool com2(XIAN a,XIAN b){ return a.r<b.r; }
signed main()
{
    cin >> n >> x;
    for(int i=1;i<=n;i++)
        cin >> a[i].l >> a[i].r >> a[i].cost, b[i] = a[i];
    sort(a+1,a+1+n,com1);
    sort(b+1,b+1+n,com2);
    memset( cost,0x3f,sizeof cost );
    int inf = cost[0], ans = cost[0];
    for(int i=1,j=1;i<=n;i++)
    {
        while( j<=n && b[j].r<a[i].l )
        {
            cost[b[j].r-b[j].l+1] = min( cost[b[j].r-b[j].l+1],b[j].cost );
            j++;    
        }
        int len = x-( a[i].r-a[i].l+1 );
        if( len>0 )    ans = min( ans,cost[len]+a[i].cost );    
    }
    if( ans==inf )    ans = -1;
    cout << ans;
}