P1816线段树90pts,#9RE
  • 板块P1816 忠诚
  • 楼主AbelTomato
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/7/27 11:04
  • 上次更新2023/10/27 18:12:18
查看原帖
P1816线段树90pts,#9RE
561297
AbelTomato楼主2022/7/27 11:04

rt,应该不是数组越界的问题,我已经试过开大数组了

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<iomanip>
#define ll long long
#define ull unsigned long long
#define maxn 100005
#define ls k<<1
#define rs k<<1|1
using namespace std;
int m,n;
ll a[maxn];
int x,y;
struct node
{
	int l,r;
	int mn;
}t[maxn<<2];
void build(int l,int r,int k)
{
	t[k].l=l;
	t[k].r=r;
	if(l==r)
	{
		t[k].mn=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,ls);
	build(mid+1,r,rs);
	t[k].mn=min(t[ls].mn,t[rs].mn);
}
int ask(int x,int y,int k)
{
	if(t[k].l>=x&&t[k].r<=y)
	{
		return t[k].mn;
	}
	int mid=(t[k].l+t[k].r)>>1;
	int ans=2147483647;
	if(mid>=x)
	{
		ans=min(ans,ask(x,y,ls));
	}
	if(mid<y)
	{
		ans=min(ans,ask(x,y,rs));
	}
	return ans;
}
int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&a[i]);
	}
	build(1,n,1);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		printf("%d ",ask(x,y,1));
	}
	return 0;
}

2022/7/27 11:04
加载中...