1628 - LowerBound
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 123
Solved: 49
- Description
- You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 2*10^9, 1 ≤ N ≤ 100000 ). A query is defined as follows:
(L,R,V) : find the smallest number of A[i] such that L<=i<=R and A[i]>V, if not exist, output
“not exist”.
Given M queries, your program must output the results of these queries.
- Input
- The first line contains a single integer T, the number of test cases.
For each case, there are two integers N and M (1<= N, M <=100000).
The next line contain N elements.
A1 A2 … AN
The next M lines contain the operation in following form.
L1 R1 V1
L2 R2 V2
…
LM RM VM
- Output
- For each question, output the answer in one line.
- sample input
-
1 5 5 5 4 3 2 1 1 5 2 2 4 0 3 5 3 1 4 3 2 5 1
- sample output
-
3 2 not exist 4 2
- hint
- source
- The 8th(2013) ACM Programming Contest of HUST