首页 > 代码库 > tyvj1297 小气的小B

tyvj1297 小气的小B

2024-08-01 18:46:30   220人阅读

描述

其实你们都不知道，小B是很小气的。一天小B带着他的弟弟小B‘一起去摘果子，走着走着，他们忽然发现了一颗长满了果子的树。由于弟弟长得太矮了，弟弟只有让哥哥小B帮他摘一些果子下来。哥哥小B说:"弟弟啊，不是我不想给你摘多，我只是一次拿不了那么多，昨天晚上又没睡好，只能上一次树。所以哥哥只能给你摘一个哈。"没办法，弟弟只有答应了这个要求。
于是几下小B就上了树，树上的果子还真多，有N个呢！！但是小B很快发现这些果子大小不一。抠门的小B就想给自己拿个最大的，给弟弟拿个最小的果子。但是由于树上有些果子太高，小B不一定可以够着，所以他给你选了P个可以够着的果子区间，让你在这些区间里面找一个最大的果子和一个最小的果子。

输入格式

共p+2行，
  第一行为n和p，
  第二行为区间[1,n]的果子大小（用正整数表示）
  后面p行形如a b，意为每次询问的区间的左界和右界

输出格式

共p行，第i行为第i次询问时得到的最大值以及最小值（一个询问用空格空开max和min）

【注意】在输入数据中果子的大小是无序的。

测试样例1

输入

5 2 
1 3 2 4 5 
1 4 
2 5 

输出

4 1 
5 2 

备注

【数据范围】
  保证果子大小不超过maxlongint
  40%的数据：1<=n,p<=1,000
  100%的数据：1<=n<=50,000
               1<=p<=20,000

刷水了……裸的线段树维护最大最小值

#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){    LL x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}struct segtree{	int l,r,mn,mx;}tree[300000];int n,m;int a[50010];inline void update(int k){	tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx);	tree[k].mn=min(tree[k<<1].mn,tree[k<<1|1].mn);}inline void buildtree(int k,int l,int r){	tree[k].l=l;tree[k].r=r;	if (l==r)	{		tree[k].mx=tree[k].mn=a[l];		return;	}	int mid=(l+r)>>1;	buildtree(k<<1,l,mid);	buildtree(k<<1|1,mid+1,r);	update(k);}inline int query(int k,int l,int r,int opr){	int x=tree[k].l,y=tree[k].r;	if (x==l&&y==r)	{		if (opr==1)return tree[k].mx;		if (opr==2)return tree[k].mn;	}	int mid=(x+y)>>1;	if (r<=mid)return query(k<<1,l,r,opr);	if (l>mid)return query(k<<1|1,l,r,opr);	if (opr==1)return max(query(k<<1,l,mid,opr),query(k<<1|1,mid+1,r,opr));	if (opr==2)return min(query(k<<1,l,mid,opr),query(k<<1|1,mid+1,r,opr));}int main(){	n=read();m=read();	for(int i=1;i<=n;i++)a[i]=read();	buildtree(1,1,n);	for (int i=1;i<=m;i++)	  {	  	int x=read(),y=read();	  	printf("%d %d\n",query(1,x,y,1),query(1,x,y,2));	  }	return 0;}

　　

tyvj1297 小气的小B


联系
我们