UESTC 1558 Charitable Exchange

本文从WordPress迁移而来, 查看全部WordPress迁移文章

线段树

把一个转化变为一个线段

l->r，看做线段[l,r]，用这个线段去覆盖总区间，这条线段的权值就是那个时间

先对所有操作即线段排序，按左端点升序排序

然后总区间每个单元的最小值Min初始化为INF，而1号单元初始化为0

在覆盖前先询问这个区间的最小值Min，如果最小值是INF，那么这次覆盖是不能进行的，这
说明之前都没有线段覆盖过这部分，这次也不能覆盖

找到最小值后，可以覆盖这个线段，本次产生的花费是c = Min + t，用这个c去更新区间[l,r]的每个单元

这个是原始的思想，这种思想的正确性，不难理解

但是问题是更新操作，得到c后，要更新整个区间的每个单元，这是会超时的，因为深入到每个叶子了

如果细想这个问题，可以知道，其实每次只需要更新每个区间的右端点即可

这个问题的正确性，不累述了，想想很容易明白的

数据比较大，一开始先排序去重离散化

注意无穷大的设置，设置为0x3f3f3f3f会wa!要设置一个更大的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
#define N 100010
#define INF 100000000000000
#define LL long long
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

int n,E;
int Hash[2*N];
map<int,int>M;
struct segment{
	int l,r; LL t;
	bool operator<(const segment &a)const{
		return l < a.l;
	}
}s[N];
struct SegTree{
	int l,r,mid;
	LL Min;
	SegTree(){}
	SegTree(int __l,int __r){
		l = __l; r = __r; mid = (l+r)>>1; Min = INF;
	}
}t[2*N*4];

void build(int rt,int a,int b){
	t[rt] = SegTree(a,b);
	if(a == b) return ;
	int mid = t[rt].mid;
	build(lson(rt),a,mid);
	build(rson(rt),mid+1,b);
}

LL query(int rt,int a,int b){
	if(t[rt].l == a && t[rt].r == b){
		return t[rt].Min;
	}
	int mid = t[rt].mid;
	if(b <= mid) 
		return query(lson(rt),a,b);
	else if(a > mid) 
		return query(rson(rt),a,b);
	else{
		LL res1 = query(lson(rt),a,mid);
		LL res2 = query(rson(rt),mid+1,b);
		return min(res1,res2);
	}
}

void PushUp(int rt){
	t[rt].Min = min(t[lson(rt)].Min,t[rson(rt)].Min);
}

void updata(int rt,int index,LL val){
	if(t[rt].l == t[rt].r){
		t[rt].Min = min(t[rt].Min,val);
		return ;
	}
	int mid = t[rt].mid;
	if(index <= mid) 
		updata(lson(rt),index,val);
	else
		updata(rson(rt),index,val);
	PushUp(rt);
}

int main(){
	int T;
	scanf("%d",&T);
	for(int cas = 1; cas <= T; cas++){
		scanf("%d%d",&n,&E);
		for(int i = 0; i < n; i++){
			scanf("%d%d%lld",&s[i].r,&s[i].l,&s[i].t);
			Hash[i<<1] = s[i].l; Hash[i<<1|1] = s[i].r;
		}
		Hash[n<<1] = 1; Hash[n<<1|1] = E;
		int tot = 0;
		M.clear();
		sort(Hash,Hash+2*n+2);
		for(int i = 0; i < ((n+1)<<1); i++)
			if(i == 0 || Hash[i] != Hash[i-1]){
				M[Hash[i]] = tot++;
			}
		build(1,0,tot-1);
		updata(1,0,0);
		sort(s,s+n);
		for(int i = 0; i < n; i++){
			int a = M[s[i].l];
			int b = M[s[i].r];
			LL c = s[i].t;
			LL res = query(1,a,b);
			updata(1,b,res+c);
		}
		LL res = query(1,M[E],tot-1);
		printf("Case #%d: %lld\n",cas,(res >= INF ? -1 : res));
	}
	return 0;
}