# 请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1) O(1)
by SSerxhs @ 2019-04-13 21:31:23
@[SSerxhs](/space/show?uid=29826) 题解的线段树可以A啊..比如这篇
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 8000001
#define re register
#define FOR(i,l,r) for(re int i=l;i<=r;i++)
using namespace std;
int a[maxn],b[maxn],ans[maxn],tag[maxn],m,n,maxx,minn,c,t,x,y;
inline int in(){
char ch;
int a=0,w=1;
while(!(((ch=getchar())>='0')&&(ch<='9')));
a*=10;a+=ch-'0';
while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0';
return a*w;
}
inline void out(int a){
if(a>=10)out(a/10);
putchar(a%10+'0');
}
inline int ls(int k){
return k<<1;
}
inline int rs(int k){
return k<<1|1;
}
inline void push_up(int k){
ans[k]=max(ans[ls(k)],ans[rs(k)]);
}
void build(int p,int l,int r){
if(l==r){
ans[p]=a[l];
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
int query(int q_x,int q_y,int l,int r,int p){
int res=0;
if(q_x<=l&&r<=q_y)
return ans[p];
int mid=(l+r)>>1;
if(q_x<=mid) res=max(res,query(q_x,q_y,l,mid,ls(p)));
if(q_y>mid) res=max(res,query(q_x,q_y,mid+1,r,rs(p)));
return res;
}
int main(){
n=in(),m=in();
FOR(i,1,n)
a[i]=in();
build(1,1,n);
FOR(i,1,m){
x=in(),y=in();
out(query(x,y,1,n,1));
puts("");
}
}
```
by RoRoyyy @ 2019-04-13 21:32:39
我觉得可能是玄学问题
我的远古代码
~~~cpp
#include<iostream>
#include<cstdio>
using namespace std;
struct shu
{
int l,r,s;
}a[8000004];
int shu(int l,int r,int k)
{
a[k].l=l;
a[k].r=r;
if(l==r)cin>>a[k].s;
else a[k].s=max(shu((l+r)/2+1,r,k*2+1),shu(l,(l+r)/2,k*2));
return a[k].s;
}
int findmax(int l,int r,int k)
{
if(a[k].l>r||a[k].r<l)return -2147482647;
if(a[k].l>=l&&a[k].r<=r)return a[k].s;
return max(findmax(l,r,2*k),findmax(l,r,2*k+1));
}
int main()
{
int n,m,ll,rr;
scanf("%d%d",&n,&m);
shu(1,n,1);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&ll,&rr);
printf("%d\n",findmax(ll,rr,1));
}
return 0;
//system("pause");
return 0;
}
~~~cpp
by ttklwxx @ 2019-04-13 21:36:10
@[董鲤鱼烧](/space/show?uid=65309) 我的没错吧..
by RoRoyyy @ 2019-04-13 21:38:30
~~俗话说得好：人丑常数大~~
by hyfhaha @ 2019-04-13 21:53:18
emmm蒟蒻才交的，时间最大单点400ms+
```cpp
#include<bits/stdc++.h>
namespace IO{
//#define R register
#define num (ch-'0')
template<typename T>inline void read(T& res){
char ch;bool flag=false;
while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getchar());res=res*10+num);
(flag)&&(res=-res);
}
template<typename T>inline void print(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}
template<typename T>inline T min(T a,T b){ return a >= b ? b : a; }
template<typename T>inline T max(T a,T b){ return a >= b ? a : b; }
}
using namespace IO;
using namespace std;
typedef long long LL;
#define Mid(l,r) ((l+r)>>1)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
const LL maxn=100010;
LL n,m,a[maxn],ans[maxn<<2],lazy[maxn<<2],maxx[maxn<<2],cnt;
inline void build(LL p,LL l,LL r){
if(l==r){ans[p]=a[l],maxx[p]=a[++cnt];return;}
LL mid=Mid(l,r);
build(ls(p),l,mid);
build(rs(p),mid+1,r);
maxx[p]=IO::max(maxx[ls(p)],maxx[rs(p)]);
}
inline LL get_max(LL p,LL l,LL r,LL nl,LL nr){
LL re=-0x3f3f3f3f;
if(nl<=l&&r<=nr) re=maxx[p];
else{
LL m=Mid(l,r);
if(nl<=m) re=IO::max(re,get_max(ls(p),l,m,nl,nr));
if(nr>m) re=IO::max(re,get_max(rs(p),m+1,r,nl,nr));
}
return re;
}
signed main(){
read(n),read(m);
for(LL i=1;i<=n;i++) read(a[i]);
build(1,1,n);
while(m--){
LL l,r;
read(l),read(r);
print(get_max(1,1,n,l,r)),putchar('\n');
}
return 0;
}
```
by c20191623 @ 2019-05-07 18:22:59
这题卡cin、cout（都改scanf/printf才有用）
by 蒟蒻lxy @ 2019-07-01 23:00:24