山姆的競程日記

從綠牌開始的旅途

0%

IOI 2014 Wall & IOI 2005 Mountain

發表於 更新於 Disqus：

IOI 2014 Wall & IOI 2005 Mountain

上週瘋狂的在解Codeforces EDU的線段樹題目
其中有各式各樣的線段樹題目 而這兩題剛好是過往的IOI題目 所以來紀錄一下解法

IOI 2014 Wall

題目：
中文：
http://ioi.te.lv/locations/ioi14/contest/day1/wall/twn.pdf
英文：
http://ioi.te.lv/locations/ioi14/contest/day1/wall/wall.pdf

總而言之，今天有個人建造磚牆，一開始整個牆都沒有任何磚塊，他會進行 $k$ 次操作，
每次進行第 $t$ 種操作 給予區間 $[l,r]$ 以及 $h$
操作共有兩種

（一）把 $[l,r]$ 高度不到 $h$ 的牆全部提升到 $h$

（二）把 $[l,r]$ 高度高於 $h$ 的牆全部降低為 $h$

問最後每一面牆的高度為何？

這題用到區間修改 不過只有最後去進行每個點的單點詢問
我們可以想想看要如何去進行修改

我們給予線段樹上的每個節點兩個標記 分別紀錄提昇與降低的高度
在這裡將他們命名為 $up$, $down$
預設先將$up=0$, $down = INF$（$INF$的數值只要大於$100000$就可以了）

在進行區間更新時

當我們要進行提昇的動作
修改節點的$up=max(up,h)$, $down=max(down,h)$

而相反的 要降低高度時
修改節點的$up=min(up,h)$, $down=min(down,h)$

這樣我們對於節點的標記就完成了

而當我們要下推節點的標記時 我們會有四種動作（$up’,down’$為我們要下推的標記）

$1.up=max(up,up’)$

$2.up=min(up,down’)$

$3.down=max(down,up’)$

$4.down=min(down,down’)$

仔細想一下 這四種操作分別能夠在提昇與降低時更新節點的數值
而最後就可以輸出所有的葉節點了

程式碼

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
#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 2e6+5;
struct node{
	int up = 0, down = 1e5+5;
	node(){}
} d[4*N];
void apply(int ind, int up, int down){
	if(ind>=0&&ind<4*N){
		d[ind].down = min(d[ind].down,down);
		d[ind].down = max(d[ind].down,up);
		d[ind].up = max(d[ind].up,up);
		d[ind].up = min(d[ind].up,down);
	}
}
void range_modify(int mode, int ml, int mr, int val, int ind = 1, int l = 0, int r = N-1){
	if(ml>r||mr<l) return;
	if(ml<=l&&mr>=r){
		if(mode){
			d[ind].down = min(d[ind].down,val);
			d[ind].up = min(d[ind].up,val);
		}
		else{
			d[ind].down = max(d[ind].down,val);
			d[ind].up = max(d[ind].up,val);
		}
		return;
	}
	int mid = (l+r)/2;
	apply(ind<<1,d[ind].up,d[ind].down);
	apply(ind<<1|1,d[ind].up,d[ind].down);
	d[ind].up = 0, d[ind].down = 1e5+5;
	range_modify(mode,ml,mr,val,ind<<1,l,mid);
	range_modify(mode,ml,mr,val,ind<<1|1,mid+1,r);
}
int n,k;
void query(int ind, int l, int r){
	if(l==r){
		if(l!=n) cout << min(d[ind].up,d[ind].down) << "\n";
		return;
	}
	apply(ind<<1,d[ind].up,d[ind].down);
	apply(ind<<1|1,d[ind].up,d[ind].down);
	d[ind].up = 0, d[ind].down = 1e5+5;
	int mid = l+r>>1;
	query(ind<<1,l,mid);
	query(ind<<1|1,mid+1,r);
}

signed main(){
	fastio
	cin >> n >> k;
	while(k--){
		int mode,l,r,val;
		cin >> mode >> l >> r >> val;
		range_modify(mode-1,l,r,val,1,0,n);
	}
	query(1,0,n);
}

IOI 2005 Mountain

題目：
英文：http://ioi.te.lv/locations/ioi05/contest/day1/mou/mou.pdf

這題的意思是說有 $n$ 條鐵路軌道 每個火車最高只能爬到 $h$ 的高度
他會給予很多次修改鐵路上升的幅度以及每一台火車所能爬到的高度
問火車能爬完幾條鐵路

這題其實還滿簡單的 不過要注意的是 $n$ 的範圍 $1<n<10^9$
很明顯需要使用動態開點的線段樹

一開始看到這題時 因為Codeforces前面的練習題有「區間加等差數列」還有「第一個大於X的元素」
看到時就馬上刻了一棵超級毒瘤的線段樹
不過仔細想想 這題根本沒原本想的那麼難

這題需要的只是一棵區間加值的線段樹 然後找到總和大於X的第一個元素

要找大於X的元素時 我們會做的是維護區間元素的最大值
所以換成找總和時 則是在每個節點維護區間總和的最大值
在這裡我稱他為$mx$

而要維護總和的最大值
我們只需要在區間更新時 順便更新每個節點mx的值

附上我的程式碼

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
#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int INF = 1e9+7;
int N;
struct node{
	node *lc, *rc;
	int l, r, sum, lz, mx;
	node():lc(NULL), rc(NULL), l(0), r(N), sum(0), lz(-INF), mx(0){}
	void ext(){
		if(lc==NULL){
			lc = new node();
			rc = new node();
			lc->l = l, lc->r = l+r>>1;
			rc->l = (l+r>>1)+1, rc->r = r;
		}
	}
};

void apply(node *&t){
	if(t->l!=t->r) t->ext();
	if(t->lz>-INF){
		t->sum = t->mx = (t->r-t->l+1)*t->lz;
		if(t->l!=t->r){
			t->lc->lz = t->lz;
			t->rc->lz = t->lz;
		}
		t->lz = -INF;
	}
}

void modify(node *&t, int l, int r, int val){
	apply(t);
	if(t->l > r || t->r < l) return;
	if(t->l >= l && t->r <= r){
		t->sum = t->mx = (t->r-t->l+1)*val;
		if(t->l!=t->r){
			t->ext();
			t->lc->lz = val;
			t->rc->lz = val;
		}
		return;
	}
	t->ext();
	modify(t->lc,l,r,val);
	modify(t->rc,l,r,val);
	t->sum = t->lc->sum + t->rc->sum;
	t->mx = max(t->lc->mx, t->lc->sum + t->rc->mx);
}



int query(node *&t, int val){
	apply(t);
	if(t->l==t->r){
		if(t->mx > val) return t->l-1;
		return t->l;
	}
	apply(t->lc);
	if(t->lc->mx > val) return query(t->lc,val);
	return query(t->rc,val-t->lc->sum);	
}


signed main(){
	fastio 	
	cin >> N;
	node *t = new node();
	char q;
	while(cin >> q){
		if(q=='E') return 0;
		if(q=='Q'){
			int val;
			cin >> val;
			cout << query(t,val) << "\n";
		}else{
			int l,r,d;
			cin >> l >> r >> d;
			modify(t,l,r,d);
		}
	}
}