做游戏网站有钱赚吗,百度官方入口,个人如何注册商标,中咨城建设计有限公司官方网站cf1555 E. Boring Segments
题意#xff1a;
给你n个线段#xff0c;最大点是m#xff0c;每一个线段有一个权值w#xff0c;你能选择线段来覆盖1-m这个区间的#xff0c;选择的代价为最大权值和最小权值的差。问你最小的的代价是多少。
题解#xff1a;
尺取线段树 …cf1555 E. Boring Segments
题意
给你n个线段最大点是m每一个线段有一个权值w你能选择线段来覆盖1-m这个区间的选择的代价为最大权值和最小权值的差。问你最小的的代价是多少。
题解
尺取线段树 我们尺取的选择线段然后用线段树来判断此时区间是否被完全覆盖如何判断呢我们可以认为一开始整个线段树都是0每加入一个线段这个区间的值1当tr[1].sum!0时即所有点都被覆盖。 注意本题中的覆盖是覆盖所有边比如线段[1,5]和线段[6,10]并没有将[1,10]这个范围覆盖应该是[1,5]和[5,10]才算覆盖所以我们可以将m个点转换成m-1个边覆盖这m-1个边每个线段的右端点也要-1
代码
// Problem: E. Boring Segments
// Contest: Codeforces - Educational Codeforces Round 112 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1555/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// Data:2021-08-18 13:52:58
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef LOCALstartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef LOCALendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 1e6 9;
struct node
{int l, r, w;
} a[maxn];
bool cmp(node a, node b)
{return a.w b.w;
}
struct tree
{int l, r;int minn;int lazy;
} tr[maxn 2];
void solve(int rt, int val)
{tr[rt].lazy val;tr[rt].minn val;
}
void pushdown(int rt)
{solve(rt 1, tr[rt].lazy);solve(rt 1 | 1, tr[rt].lazy);tr[rt].lazy 0;
}
void pushup(int rt)
{tr[rt].minn min(tr[rt 1].minn, tr[rt 1 | 1].minn);
}
void update(int rt, int l, int r, int val)
{if (tr[rt].l r || tr[rt].r l)return;if (tr[rt].l l tr[rt].r r) {solve(rt, val);return;}if (tr[rt].lazy)pushdown(rt);update(rt 1, l, r, val);update(rt 1 | 1, l, r, val);pushup(rt);
}
void build(int rt, int l, int r)
{//coutrtrtendl;tr[rt].l l;tr[rt].r r;tr[rt].lazy 0;if (l r) {tr[rt].minn 0;return;}int mid (l r) 1;build(rt 1, l, mid);build(rt 1 | 1, mid 1, r);pushup(rt);
}
int main()
{//rd_test();int n, m;read(n, m);for (int i 1; i n; i) {int l, r, w;read(l, r, w);a[i] {l, --r, w};}m--;sort(a 1, a 1 n, cmp);build(1, 1, m);int minn INF_int;for (int i 1, j 0; i n; i) {while (j n tr[1].minn 0) {j;update(1, a[j].l, a[j].r, 1);}if (j i tr[1].minn)minn min(minn, a[j].w - a[i].w);update(1, a[i].l, a[i].r, -1);}printf(%d\n, minn);//Time_test();
}
