首页 > 代码库 > 线段树
线段树
A - An easy problem A
Time Limit: 1000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
N个数排成一列,Q个询问,每次询问一段区间内的数的极差是多少。
Input
第一行两个整数N(1≤N≤50000),Q(1≤Q≤200000)。接下来一行N个整数a1 a2 a3 ....an,(1≤ai≤1000000000)。接下来Q行,每行两个整数L,R(1≤L≤R≤N)。
Output
对于每个询问输出一行,一个整数表示区间内的极差。
Sample input and output
Sample Input | Sample Output |
---|---|
5 3 3 2 7 9 10 1 5 2 3 3 5 |
8 5 3 |
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int MAXN = 50000; 6 7 typedef struct 8 { 9 int left,right,maxv,minv; 10 }Node; 11 Node rt[MAXN<<2]; 12 int a[MAXN+5]; 13 14 void build(int x, int L, int R) 15 { 16 rt[x].left = L; rt[x].right = R; 17 if(L==R) 18 { 19 rt[x].maxv = rt[x].minv = a[L]; 20 return ; 21 } 22 int mid = L + R >>1; 23 build(x<<1,L,mid); build((x<<1)+1,mid+1,R); 24 rt[x].maxv = max(rt[x<<1].maxv,rt[(x<<1)+1].maxv); 25 rt[x].minv = min(rt[x<<1].minv,rt[(x<<1)+1].minv); 26 } 27 28 Node query(int x, int L, int R) 29 { 30 Node t,tt; 31 int mid = (rt[x].left + rt[x].right)>>1; 32 if(L == rt[x].left && R == rt[x].right) 33 { 34 return rt[x]; 35 } 36 else if(R<=mid) 37 { 38 tt = query(x<<1,L,R); 39 t.maxv = tt.maxv; 40 t.minv = tt.minv; 41 return t; 42 } 43 else if(L>mid) 44 { 45 tt = query((x<<1)+1,L,R); 46 t.maxv = tt.maxv; 47 t.minv = tt.minv; 48 return t; 49 } 50 else 51 { 52 t = query(x<<1,L,mid); 53 tt = query((x<<1)+1,mid+1,R); 54 t.maxv = max(t.maxv,tt.maxv); 55 t.minv = min(t.minv,tt.minv); 56 return t; 57 } 58 59 } 60 61 int main() 62 { 63 int n,q,l,r; 64 Node t; 65 scanf("%d %d",&n,&q); 66 for(int i=1;i<=n;++i) 67 scanf("%d",&a[i]); 68 build(1,1,n); 69 //for(int i=1;i<=9;++i) 70 //printf("%d,%d\t",rt[i].maxv,rt[i].minv); 71 while(q--) 72 { 73 scanf("%d %d",&l,&r); 74 t = query(1,l,r); 75 printf("%d\n",t.maxv-t.minv); 76 } 77 78 return 0; 79 }
线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。