线段树一片红求助
查看原帖
线段树一片红求助
246979
SalomeJLQ楼主2020/9/7 22:13

还是一道水题,用线段树写的,九点WA一点T,

调试的眼都花了,不知道样例怎么就输出了-3 -3 -3 -3 3 33 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;
}
2020/9/7 22:13
加载中...