POJ3264(线段树入门题)
Balanced LineupCrawling in process... Crawling failed Time Limit:5000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Time Limit:5000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.
Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.
Input
Output
Sample Input
6 3
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0
#include"cstdio"
#include"cstring"
#include"algorithm"
#define lson (rt<<1),l,mid
#define rson (rt<<1)|1,mid+1,r
#define gmid (a[rt].l+a[rt].r)>>1;
using namespace std;
const int MAXN=;
struct node{
int l,r;
int maxn,minn;
}a[MAXN*]; void build(int rt,int l,int r)
{
a[rt].l=l;
a[rt].r=r;
if(l==r)
{
scanf("%d",&a[rt].maxn);
a[rt].minn=a[rt].maxn;
return ;
} int mid=gmid;
build(lson);
build(rson);
a[rt].maxn=max(a[rt<<].maxn,a[(rt<<)|].maxn);
a[rt].minn=min(a[rt<<].minn,a[(rt<<)|].minn);
} int query(int rt,int l,int r,int op)
{
if(a[rt].l==l&&a[rt].r==r)
{
if(op==) return a[rt].maxn;
else return a[rt].minn;
} int mid=gmid; if(r<=mid) return query(rt<<,l,r,op);
else if(mid<l) return query((rt<<)|,l,r,op);
else{
if(op==) return max(query(rt<<,l,mid,op),query((rt<<)|,mid+,r,op));
else return min(query(rt<<,l,mid,op),query((rt<<)|,mid+,r,op));
}
} int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
build(,,n);
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
int diff=query(,l,r,)-query(,l,r,);//1表示求最大值,2表示求最小值
printf("%d\n",diff);
}
} }
最新文章
- 在EF4.1的DBContext中实现事务处理(BeginTransaction)和直接执行SQL语句的示例
- BestCoder Round #65
- ASP.NET导出bdf文件
- oracle怎么卸载(转)
- SteamVR Unity工具包(VRTK)之激光和移动
- 炮兵阵地 - POJ 1185(状态压缩)
- 将.lib库文件转换成.a库文件的工具
- ngnix 一 入门指南
- JSP脚本元素上机手册
- 浅谈position: absolute和position:relative
- ConcurrentHashMap实现原理及源码分析
- shiro 权限管理配置
- js事件冒泡机制
- python模块:subprocess
- Tomcat搭建Web 应用服务器
- 【XSY2719】prime 莫比乌斯反演
- .Net MVC关于子页面引用js库问题
- vim : Depends: vim-common (= 2:7.4.052-1ubuntu3.1) but 2:7.4.273-2ubuntu4 is to be installed
- 找进程的窗口Handle
- 主成分分析PCA