简单的线段树问题, 但是不加读入优化会超时(正解是单调队列)
线段树直接背模板
- #include <bits/stdc++.h>
- using namespace std;
- /* 注意: 本题线段树解法非正解, 请自行搜索单调队列 */
- const int N = 25100;
- int a[N],M;// 数组 a 是原序列
- struct ST{
- int l,r,max;//l,r 分别表示当前节点所维护的左右区间, max 表示在区间 l - r 里的最大值
- }tree[N <<2];// 线段树空间开四倍
- int read(){// 读入优化
- int n = 0,m = 1; char ch = getchar();//m 判断正负
- while(ch < '0' || ch> '9'){ if(ch == '-') m = -1; ch = getchar(); }
- while(ch>= '0' && ch <= '9'){ n = (n <<3) + (n << 1) + ch - 48; ch = getchar(); }
- return n * m;
- }
- void pushup(int rt){// 更新当前节点的最大值, 等于 max(左儿子的最大值, 右儿子的最大值)
- tree[rt].max = max(tree[rt << 1].max,tree[rt << 1 | 1].max);//rt << 1 = rt * 2; rt << 1 | 1 = rt * 2 + 1
- }
- void build(int l,int r,int rt){// 建树过程, rt: 当前节点编号
- tree[rt].l = l; tree[rt].r = r; // 先初始化一下
- if(l == r) {tree[rt].max = a[l]; return;}// 如果 l == r 则说明当前是叶子节点也就是只有一个元素 (a[l] 或 a[r]) 所以叶子节点的最大值就是它本身, 也是递归边界, 不用再进行递归
- int mid = (l + r)>> 1;// 建立中点
- build(l,mid,rt <<1); build(mid + 1,r,rt << 1 | 1);// 分别建立左儿子和右儿子
- pushup(rt);// 更新当前节点的最大值
- }
- int Query(int L,int R,int l,int r,int rt){// 查询 L - R 操作
- if(L <= l && r <= R) return tree[rt].max;// 如果当前节点所维护的区间被所求的区间包含, 直接返回最大值
- int mid = (l + r)>> 1,ans = -9999999;// 否则到左右儿子中寻找最大值
- if(L <= mid) ans = max(ans,Query(L,R,l,mid,rt <<1));
- if(R> mid) ans = max(ans,Query(L,R,mid + 1,r,rt << 1 | 1));
- return ans;// 返回最大值
- }
- int main(){
- M = read();
- int v = 0;
- while(1){
- v++;
- a[v] = read();
- if(a[v] == -1){
- v--; break;
- }
- }
- build(1,v,1);
- for(int i = 1;i <= v - M + 1; i++){
- cout << Query(i,i + M - 1,1,v,1) << endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2677133.html