题目传送门
1.线段树
线段树可以搞。
不过慢的要死1300+ms
1 #include <cstdio> 2 #include <iostream> 3 4 using namespace std; 5 6 int m, n, pos, ql, qr; 7 long long c[2000001], x, d, t; 8 char s; 9 10 void build(int o, int l, int r) 11 18 19 void update(int o, int l, int r) 20 26 int mid = (l + r) / 2; 27 if(pos <= mid) update(o * 2, l, mid); 28 else update(o * 2 + 1, mid + 1, r); 29 c[o] = max(c[o * 2], c[o * 2 + 1]); 30 } 31 32 int query(int o, int l, int r) 33 40 41 int main() 42 55 else 56 62 } return 0; 64 }View Code
2.单调栈
单调栈不仅快且代码量小。
300+ms
1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # include <cmath> 6 # include <vector> 7 # include <map> 8 # include <queue> 9 # include <cstdlib> 10 # include <algorithm> 11 # define MAXN 200001 12 using namespace std; 13 14 int m, d, t, len; 15 int top, s[MAXN], a[MAXN]; 16 17 int main() 18 32 else 33 37 } 38 return 0; 39 }View Code
上一篇：[luoguP2912] [USACO08OCT]牧场散步Pasture Walking（lca）
下一篇：[luoguP1266] 速度限制（spfa）
线段树 单调栈
