Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 线段树也不长啊，38行，在2016年跑了2016MS，有趣！！！

Posted by wtl666wtl at 2016-03-28 08:32:24 on Problem 3264 and last updated at 2016-03-28 08:32:52
```#include <cstdio>
#include <algorithm>
using namespace std;
int q,x,y,n,a[50005],f1[150005],f2[150005];
void JZ (int i,int x,int y)
{
if(x==y){f1[i]=a[x];f2[i]=a[x];return;}
int m=(x+y)/2;JZ (2*i,x,m);JZ (2*i+1,m+1,y);
f1[i]=max(f1[i*2],f1[i*2+1]);f2[i]=min(f2[i*2],f2[i*2+1]);
}
int CZ1 (int i,int x,int y,int q,int w)
{
if(x>=q&&y<=w)return f1[i];
int m=(x+y)/2;
if(w<=m)return CZ1 (i*2,x,m,q,w);
else if(q>m)return CZ1 (i*2+1,m+1,y,q,w);
else return max(CZ1 (i*2,x,m,q,w),CZ1 (i*2+1,m+1,y,q,w));
}
int CZ2 (int i,int x,int y,int q,int w)
{
if(x>=q&&y<=w)return f2[i];
int m=(x+y)/2;
if(w<=m)return CZ2 (i*2,x,m,q,w);
else if(q>m)return CZ2 (i*2+1,m+1,y,q,w);
else return min(CZ2 (i*2,x,m,q,w),CZ2 (i*2+1,m+1,y,q,w));
}
int main ()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
JZ (1,1,n);
for(int i=1;i<=q;i++){
scanf("%d%d",&x,&y);
int m1=CZ1 (1,1,n,x,y);
int m2=CZ2 (1,1,n,x,y);
printf("%d\n",m1-m2);
}
}```

Followed by: