第二次更新

题目描述

输入 输出 样例输入 5 2 3 1 5 2 7 2 3 1 5 样例输出 4 6

这题可以用线段树的思想做

只要我们得到任意一个区间的最大值和最小值，将其存储在数组 Max[] 和 Min[] 中，每查询一次就输出一次,就能愉快的AC这题了

Max[ ]数组和Min[ ]数组的建立方法与线段树建树方法一样

建立 Max[ ]数组和 Min[ ]数组

void build(long long l,long long r,long long root) { if(l==r) { Max[root]=data[l]; Min[root]=data[l]; return ; } long long mid=(l+r)>>1; build(l,mid,root<<1); build(mid+1,r,root<<1|1); Max[root]=max(Max[root<<1],Max[root<<1|1]); Min[root]=min(Min[root<<1],Min[root<<1|1]); }

总的代码

#include<cstdio> #include<iostream> using namespace std; #define digit 1000101 long long data[digit],Max[digit<<1|1],Min[digit<<1|1]; long long length,len; void build(long long l,long long r,long long root) { if(l==r) { Max[root]=data[l]; Min[root]=data[l]; return ; } long long mid=(l+r)>>1; build(l,mid,root<<1); build(mid+1,r,root<<1|1); Max[root]=max(Max[root<<1],Max[root<<1|1]); Min[root]=min(Min[root<<1],Min[root<<1|1]); } long long query_max(long long l,long long r,long long st,long long ed,long long root) { if(l>ed||r<st) return 0; if(l<=st&&r>=ed) return Max[root]; long long mid=(st+ed)>>1; return max(query_max(l,r,st,mid,root<<1),query_max(l,r,mid+1,ed,root<<1|1)); } long long query_min(long long l,long long r,long long st,long long ed,long long root) { if(l>ed||r<st) return 0x3f3f3f3f; if(l<=st&&r>=ed) return Min[root]; long long mid=(st+ed)>>1; return min(query_min(l,r,st,mid,root<<1),query_min(l,r,mid+1,ed,root<<1|1)); } void enter() { scanf("%lld%lld",&length,&len); for(long long i=1;i<=length;i++) scanf("%lld",&data[i]); build(1,length,1); long long times=length-len+1; long long st=1,ed=len; while(times--) { printf("%lld ",query_min(st,ed,1,length,1)); st++; ed++; } printf("\n"); times=length-len+1; st=1;ed=len; while(times--) { printf("%lld ",query_max(st,ed,1,length,1)); st++; ed++; } } int main() { enter(); return 0; }

关于

这个算法还有很大的不足：无法一次返回最大值和最小值 分别建立两棵树并分别查询的时间复杂度难以接受 滑动窗口 以后再改