SalomeJLQ @ 2020-09-07 22:13:26
还是一道水题,用线段树写的,九点WA一点T,
调试的眼都花了,不知道样例怎么就输出了-3 -3 -3 -3 3 3
和3 3 5 5 7 7
改了很多次,越改越错,然后又改回来了,我线段树真的太屑了
所以怎么改,有人给我改一改吗,
#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],k;
struct node{int maxn,minn;}t[4000020];
void build(int l,int r,int p){
if(l==r){t[p].maxn=a[l];t[p].minn=a[l];return;}
int mid=l+r>>1;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
t[p].maxn=max(t[p*2].maxn,t[p*2+1].maxn);
t[p].minn=min(t[p*2].minn,t[p*2+1].minn);
// cout<<l<<" "<<r<<" "<<mid<<" "<<p<<" "<<t[p].maxn<<" "<<t[p].minn<<endl;
}
int askmaxn(int x,int y,int l,int r,int p){
int max1=-11111,max2=-11111;
if(l==r)return a[l];
if(l>y||r<x)return -11111;
if(l>=x&&r<=y)return t[p].maxn;
int mid=l+r>>1;
if(r>=x)max1=askmaxn(x,y,l,mid,p*2);
if(l<=y)max2=askmaxn(x,y,mid+1,r,p*2+1);
cout<<x<<" "<<y<<" "<<max1<<" "<<max2<<endl;
return max(max1,max2);
}
int askminn(int x,int y,int l,int r,int p){
int min1=99999999,min2=99999999;
if(l==r)return a[l];
if(l>y||r<x)return 99999999;
if(l>=x&&r<=y)return t[p].minn;
int mid=l+r>>1;
if(r>=x)min1=askminn(x,y,l,mid,p*2);
if(l<=y)min2=askminn(x,y,mid+1,r,p*2+1);
cout<<x<<" "<<y<<" "<<min1<<" "<<min2<<endl;
return min(min1,min2);
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,n,1);
for(int i=1;i<=n-k+1;i++)cout<<askminn(i,i+k-1,1,n,1)<<" ";
cout<<endl;
for(int i=1;i<=n-k+1;i++)cout<<askmaxn(i,i+k-1,1,n,1)<<" ";
return 0;
}
by Little09 @ 2020-09-07 22:16:42
这不是单调队列吗
by SalomeJLQ @ 2020-09-07 22:22:58
@AC_WA自动机 想用线段树做,
每天花费半小时写一棵线段树,全是bug,,
by 7KByte @ 2020-09-07 22:44:41
极值设小了吧
by ducati @ 2020-11-03 15:42:31
这题宁愿用RMQ做,我也不愿上一棵线段树QAQ