60求调
查看原帖
60求调
737014
Xuwindows_WS楼主2024/7/26 09:30

为什么线段树会WA?

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll a[1000010];
ll tr[4000040];
void build(ll l,ll r,ll id)
{
	if(l==r)
	{
		tr[id]=a[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(l,mid,id*2);
	build(mid+1,r,id*2+1);
	tr[id]=min(tr[id*2],tr[id*2+1]);
}
ll getmin(ll lt,ll rt,ll l,ll r,ll id)
{
	if(l>=lt&&r<=rt)
	{
		return tr[id];
	}
	ll mid=(l+r)>>1;
	ll minx=1e10+10;
	if(lt<=mid)minx=min(minx,getmin(lt,rt,l,mid,id*2));
	if(rt>mid)minx=min(minx,getmin(lt,rt,mid+1,r,id*2+1));
	return minx;
}
int main()
{
	cin>>n>>m;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,n,1);
	for(ll i=1;i<=n-m+1;i++)
	{
		cout<<getmin(i,i+m,1,n,1)<<'\n';
	}
	return 0;
}
2024/7/26 09:30
加载中...