ko_no_lzx_da @ 2022-07-16 10:36:20
线段树可以过吗
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
int n,k,a[10000010];
struct node{
int maxx;
int minn;
}tree[1000010];
void build(int l,int r,int n){
if(l==r){
tree[n].maxx=tree[n].minn=a[(l+r)/2];
return;
}
int mid=(l+r)/2;
build(l,mid,n*2);
build(mid+1,r,n*2+1);
tree[n].maxx=max(tree[n*2].maxx,tree[n*2+1].maxx);
tree[n].minn=min(tree[n*2].minn,tree[n*2+1].minn);
}
int fmin(int l,int r,int n,int L,int R){
cout <<'-';
if(L<=l&&r<=R){
return tree[n].minn;
}
int mid=(l+r)/2;
return min(fmin(l,mid,n*2,L,R),fmin(mid+1,r,n*2+1,L,R));
}
int fmax(int l,int r,int n,int L,int R){
if(L<=l&&r<=R){
return tree[n].maxx;
}
int mid=(l+r)/2;
return max(fmax(l,mid,n*2,L,R),fmax(mid+1,r,n*2+1,L,R));
}
int main(){
cin >>n>>k;
for(int i=1;i<=n;i++){
cin >>a[i];
}
build(1,n,1);
cout <<'-';
for(int i=1;i<=n-k;i++){
cout<<fmin(1,n,1,i,i+k-1)<<endl<<fmax(1,n,1,i,i+k-1);
}
return 0;
}
by 1lgorithm @ 2022-07-16 10:37:01
可以,但是估计要卡常
by MSqwq @ 2022-07-16 10:40:07
显然可以做,毕竟标签都有线段树
by char_cha_ch @ 2022-07-16 10:46:19
@ko_no_lzx_da 输出有问题吧
by ko_no_lzx_da @ 2022-07-16 10:55:39
@kirihara233 可以指出来吗
by 1lgorithm @ 2022-07-16 10:56:40
@ko_no_lzx_da 最小值最大值分别写循环输出吧
by ko_no_lzx_da @ 2022-07-16 11:02:41
@1lgorithm 感谢!!!Orz %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%