记录编号	426943	评测结果	AAAAAAAAAA
题目名称	延绵的山峰	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.219 s
提交时间	2017-07-19 20:54:48	内存使用	4.63 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define MAXN (1000010)

char ops[1 << 18], *opt = ops, *const opt_end = ops + (1 << 18);

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, sizeof(buf), stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res;
}

inline void write_all(void) { 
    fwrite(ops, 1, opt - ops, stdout);
    opt = ops; return ;
}

inline void write(int x) { 
    static char *p = new char[20]();
    do{ 
        *(++p) = (x % 10) | 0x30;
        x /= 10;
    }while(x);

    while(*p) { 
        *(opt++) = *(p--);
        if(opt == opt_end) write_all();
    }

    *(opt++) = '\n';
    if(opt == opt_end) write_all();
    return ;
}

struct NODE{ 
    int mx;
    NODE *ls, *rs;

    NODE() { 
        ls = rs = NULL;
    }
};

NODE *Build(int l, int r);
int Query(NODE *node, int l, int r, int L, int R);

NODE *root;
int s[MAXN];
int N, Q;

int main() { 
#ifndef LOCAL
    freopen("climb.in", "r", stdin);
    freopen("climb.out", "w", stdout);
#endif
    N = read();
    for(int i = 0, *p = s; i <= N; ++i, ++p) *p = read();
    root = Build(0, N);
    Q = read();
    for(int i = 0, l, r; i < Q; ++i) { 
        l = read(), r = read();
        write(Query(root, l, r, 0, N));
    }
    write_all();
    return 0;
}

NODE *Build(int l, int r) { 
    NODE *p = new NODE();
    if(l ^ r) { 
        register int mid = (l + r) >> 1;
        p->ls = Build(l, mid);
        p->rs = Build(mid + 1, r);
        p->mx = max(p->ls->mx, p->rs->mx);
    } else p->mx = s[l];
    return p;
}

int Query(NODE *node, int l, int r, int L, int R) { 
    if(l == L && r == R) return node->mx;
    register int mid = (L + R) >> 1;
    if(r <= mid) return Query(node->ls, l, r, L, mid);
    if(mid < l) return Query(node->rs, l, r, mid + 1, R);
    return max(Query(node->ls, l, mid, L, mid), Query(node->rs, mid + 1, r, mid + 1, R));
}