记录编号	166281	评测结果	AAAAAAAAAA
题目名称	忠诚	最终得分	100
用户昵称	lenibomb	是否通过	通过
代码语言	C++	运行时间	0.231 s
提交时间	2015-06-14 21:03:55	内存使用	12.31 MiB

#include<cstdio>
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

int sum[3050000],n,a[100050],m;
int max(int a,int b)
{
	return a<b?a:b;
}
void Push(int x)
{
    sum[x]=max(sum[x<<1],sum[x<<1|1]);
    return ;
}
void Build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%d",&sum[rt]);
        //sum[rt]=sum[rt]-sum[rt-1];
        return ;
    }
    int m=(l+r)>>1;
    Build(lson);
    Build(rson);
    Push(rt);
}
void Updata(int p,int add,int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]+=add;
        return ;
    }
    int m=(l+r)>>1;
    if(p<=m)
     Updata(p,add,lson);
    else
    Updata(p,add,rson);
    Push(rt);
}
int Query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&R>=r)
       return sum[rt];
    int result=0x7fffffff;
    int m=(l+r)>>1;
    if(L<=m)
        result=max(Query(L,R,lson),result);
    if(R>m)
        result=max(Query(L,R,rson),result);
    return result;
}
int main()
{
    freopen("faithful.in","r",stdin);
	freopen("faithful.out","w",stdout);
    int n;

    scanf("%d",&n);scanf("%d",&m);
    for(int i=0;i<=n+1;i++)
    sum[i]=0x7fffffff;
    Build(1,n,1);
    
    char s[6];
    int x,y;
    for(int i=1;i<=m;i++)
    {
            scanf("%d%d",&x,&y);
            printf("%d",Query(x,y,1,n,1));
            if(m!=i) printf(" ");
    }
//while(1);
}