Ensamblador

 

#include<iostream>

02	using namespace std;

03	#include<math.h>

04

05	template<class T>

06	class SegmentTree

07

{

08	int *A,size;

09

public:

10	SegmentTree(int N)

11

{

12	int x = (int)(ceil(log(N)))+1;

13	size = 2*(int)pow(2,x);

14	A = new int[size];

15	memset(A,-1,sizeof(A));

16

}

17	void initialize(int node, int start,

18	int end, T *array)

19

{

20

21	if (start==end)

22	A[node] = start;

23

else

24

{

25	int mid = (start+end)/2;

26	initialize(2*node,start,mid,array);

27	initialize(2*node+1,mid+1,end,array);

28	if (array[A[2*node]]<=

29	array[A[2*node+1]])

30	A[node] = A[2 * node];

31

else

32	A[node] = A[2 * node + 1];

33

}

34

}

35	int query(int node, int start,

36	int end, int i, int j, T *array)

37

{

38	int id1,id2;

39	if (i>end || j<start)

40	return -1;

41

42	if (start>=i && end<=j)

43	return A[node];

44

45	int mid = (start+end)/2;

46	id1 = query(2*node,start,mid,i,j,array);

47	id2 = query(2*node+1,mid+1,end,i,j,array);

48

49	if (id1==-1)

50	return A[node] = id2;

51	if (id2==-1)

52	return A[node] = id1;

53

54	if (array[id1]<=array[id2])

55	return A[node] = id1;

56

else

57	return A[node] = id2;

58

}

59

};

60

61	int main()

62

{

63	int i,j,N;

64	int A[1000];

65	scanf("%d",&N);

66	for (i=0;i<N;i++)

67	scanf("%d",&A[i]);

68

69	SegmentTree<int> s(N);

70	s.initialize(1,0,N-1,A);

71	while (scanf("%d%d",&i,&j)!=EOF)

72	printf("%d\n",A[s.query(1,0,N-1,i-1,j-1,A)]);