[luoguP1198][JSOI2008] 最大数（线段树 || 单调栈）

题目传送门

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

上一篇：【模板】splay

下一篇：[NOI2003]Editor（块状链表）

---

线段树 单调栈