[题解]IOI2014-Wall

Posted on Edited on In

English version

We will use lazy tag to solve this problem. Let \(upv[x]\) be the maximum bound of node \(x\), and \(lowv[x]\) be the minimum bound of node \(x\). As we only care about single point value, the leaf node's \(lowv[]\) is the answer. Now the problem is how to maintain those two arrays. Now we assume we are operating on node \(x\), and the value of operation is \(h\).

Part 1: Adding phase

​ In this part we maintain \(lowv[x]\). If \(lowv[x] < h\) or there's no operation on \(x\), let \(lowv[x] = h\).

Part 2: Removing phase

​ We maintain \(upv[x]\) just like part one. If \(upv[x] > h\),let \(upv[x] = h\). Notice if \(lowv[x] > h\), let \(lowv[x] = h\).

Part 3: Pushdown.

​ Just apply Part 1 and 2 on child nodes(\(y\)). If node's \(lowv[y]\) greater than \(upv[x]\), cut it off and vice versa.

Code

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
//P-4-E 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NO_OPT = INT_MAX;
struct segtree{
	int size = 1;
	vector<int>upv,lowv;
	void init(int n){
		while(size < n)size *= 2;
		upv.assign(size*2,NO_OPT);
		lowv.assign(size*2,NO_OPT);
	}
	inline int ls(int x){
		return (x<<1)|1;
	}
	inline int rs(int x){
		return (x<<1)+2;
	}
	void pushdown(int x,int lx,int rx){
		if(rx - lx == 1)return;
		if(upv[x] != NO_OPT){
			upv[ls(x)] = min(upv[x],upv[ls(x)]);
			upv[rs(x)] = min(upv[x],upv[rs(x)]);
			if(lowv[ls(x)] != NO_OPT and lowv[ls(x)] > upv[x])lowv[ls(x)] = upv[x];
			if(lowv[rs(x)] != NO_OPT and lowv[rs(x)] > upv[x])lowv[rs(x)] = upv[x];
			upv[x] = NO_OPT;
		}
		if(lowv[x] != NO_OPT){
			if(lowv[ls(x)] != NO_OPT)lowv[ls(x)] = max(lowv[ls(x)],lowv[x]);
			else lowv[ls(x)] = lowv[x];
			if(lowv[rs(x)] != NO_OPT)lowv[rs(x)] = max(lowv[rs(x)],lowv[x]);
			else lowv[rs(x)] = lowv[x];
			if(upv[ls(x)] != NO_OPT and upv[ls(x)] < lowv[x])upv[ls(x)] = lowv[x];
			if(upv[rs(x)] != NO_OPT and upv[rs(x)] < lowv[x])upv[rs(x)] = lowv[x];
			lowv[x] = NO_OPT;
		}
	}
	void up(int l,int r,int v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			upv[x] = min(upv[x],v);
			if(lowv[x] != NO_OPT and lowv[x] > v)lowv[x] = v;
			return;
		}
		int m = (lx+rx)/2;
		up(l,r,v,ls(x),lx,m);
		up(l,r,v,rs(x),m,rx);
		return;
	}
	void up(int l,int r,int v){
		up(l,r,v,0,0,size);
	}
	void low(int l,int r,int v,int x,int lx,int rx){
		if(l >= rx or lx >= r)return;
		pushdown(x,lx,rx);
		if(l <= lx and rx <= r){
			if(lowv[x] == NO_OPT or lowv[x] < v)lowv[x] = v;
			return;
		} 
		int m = (lx+rx)/2;
		low(l,r,v,ls(x),lx,m);
		low(l,r,v,rs(x),m,rx);
		return;
	}
	void low(int l,int r,int v){
		low(l,r,v,0,0,size);
	}
	int get(int idx,int x,int lx,int rx){
		if(idx >= rx)return NO_OPT;
		pushdown(x,lx,rx);
		if(rx - lx == 1)return lowv[x];
		int m = (lx+rx)/2;
		if(idx < m)return get(idx,ls(x),lx,m);
		else return get(idx,rs(x),m,rx);
	}
	int get(int idx){
		return get(idx,0,0,size);
	}
};
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	segtree seg;
	seg.init(n+1);
	while(m--){
		int opt,l,r,v;
		r++;
		cin >> opt >> l >> r >> v;
		r++;
		if(opt == 1)seg.low(l,r,v);
		else seg.up(l,r,v);
	}
	for(int i = 0;i < n;i++){
		int ans = seg.get(i);
		cout << (ans == NO_OPT?0:ans) << '\n';
	}
	return 0;
}

题意简述

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/E

或:

https://www.luogu.com.cn/problem/P4560

长度为\(n\)的序列初始为空,维护两种操作:

  1. Add(L,R,v): 将\([L,R]\)中小于\(v\)的值改变为\(v\)
  2. Remove(L,R,v):将\([L,R]\)中大于\(v\)的值改变为\(v\)

给出\(m\)个操作,输出操作全部完成后的序列.

\(1 \leq n \leq 2\cdot10^6,1 \leq m \leq 5\cdot10^5\)

思路

对每个节点维护\(upv[]\)和\(lowv[]\),表示该节点值的上限和下限.查询时对每个点做一次单点查询,答案为\(lowv[x]\).

下放节点时\(upv\)和\(lowv\)的关系比较显然,细节请见代码.