题目链接
题目大意
给你一个1-m的区间 n个线段
这个线段 l,r,w 代表从l到r 权值为w
问你如何选择线段可以让线段覆盖这个区间 并且选择的线段的权值最大和最小的差最小
即最大权值和最小权值最接近
题目思路
由于是要找到线段权值差最小 有单调性 很轻易考虑到将 所给的n条线段 从小到大排序
进行尺取的做法
对于排序中从小到大的线段 用线段树的方式维护 最小值 进行区间操作
区间修改操作对应尺取 每次r移动 该r线段+1 每次l移动 该l线段-1
这最小值是否为0 代表着当前有没有到达不到的节点
注意线段树上所有m要减一 因为求的是两点是否相连的边 而不是真判点
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
int n,m,pos[maxn],num,cnt,f[maxn];
const int inf = 1e9;
typedef pair<int ,int >p;
int pd[maxn],pre[maxn];
int b[maxn*2];
struct node{int l,r,w;
}e[maxn];
struct tree{int v,laz;
}ans[maxn*4];
int ls(int x)
{return x<<1;
}
int rs(int x)
{return x<<1|1;
}
void pushup(int x)
{ans[x].v=min(ans[ls(x)].v,ans[rs(x)].v);
}
void build(int l,int r,int x)
{ans[x].laz=0;ans[x].v=0;if(l==r)return ;int mid=(l+r)/2;build(l,mid,ls(x));build(mid+1,r,rs(x));pushup(x);
}
void pushdown(int x,int l,int r)
{if(ans[x].laz==0)return ;int mid=(l+r)/2;ans[ls(x)].v+=ans[x].laz;ans[rs(x)].v+=ans[x].laz;//ans[ls(x)].laz=min(ans[x].laz,ans[ls(x)].laz);//ans[rs(x)].laz=min(ans[x].laz,ans[rs(x)].laz);ans[ls(x)].laz+=ans[x].laz;ans[rs(x)].laz+=ans[x].laz;ans[x].laz=0;
}
void updata(int l,int r,int nl,int nr,int x,int k)
{if(nl>=l&&nr<=r){ans[x].laz+=k;ans[x].v+=k;return ;}pushdown(x,nl,nr);int mid=(nl+nr)/2;if(l<=mid)updata(l,r,nl,mid,ls(x),k);if(r>mid)updata(l,r,mid+1,nr,rs(x),k);pushup(x);
}
int query(int l,int r,int nl,int nr,int x)
{if(nl>=l&&nr<=r){return ans[x].v;}pushdown(x,nl,nr);int mid=(nl+nr)/2;int tmp=inf;if(l<=mid){tmp=min(tmp,query(l,r,nl,mid,ls(x)));}if(r>mid) {tmp=min(tmp,query(l,r,mid+1,nr,rs(x)));}return tmp;
}
bool cmp(node x,node y)
{return x.w<y.w;
}
int main()
{cin>>n>>m;//int cnt=0;for(int i=1;i<=n;i++){cin>>e[i].l>>e[i].r>>e[i].w;} sort(e+1,e+n+1,cmp);build(1,m-1,1);int l=1,r=1;int ans=inf;for(r=1;r<=n;r++){updata(e[r].l,e[r].r-1,1,m-1,1,1);//r线段int now=query(1,m-1,1,m-1,1);//cout<<now<<endl;if(now){ans=min(ans,e[r].w-e[l].w);while(now&&l<=r){//cout<<ans<<endl;updata(e[l].l,e[l].r-1,1,m-1,1,-1);//l线段now=query(1,m-1,1,m-1,1);l++;if(now)ans=min(ans,e[r].w-e[l].w);}}//cout<<ans<<endl;} cout<<ans<<endl;return 0;
}