LowerBound
Time Limit: 1 Sec Memory Limit: 128 MB
Submissions: 8 Solved: 7
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
在划分树基础上进行二分
n*log(n)*log(n)
#include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> using namespace std; const int maxn = 110000; int rec[maxn]; struct node{ int left; int right; int mid; }tree[maxn*5]; struct point{ int value; int right; bool is_right; }po[20][maxn]; int n,m; int build_tree(int left,int right,int deepth,int pos){ tree[pos].left=left; tree[pos].right=right; tree[pos].mid=(left+right)>>1; int mid=rec[tree[pos].mid],l=left,r=tree[pos].mid+1,i,j,k; point *now=po[deepth-1],*then=po[deepth]; int ll=0; for(i=tree[pos].mid;i>=left;i--){ if(rec[i]==mid) ll++; } for(i=left;i<=right;i++){ if(now[i].value==mid && ll){ ll--; then[l++].value=mid; now[i].is_right=false; continue; } if(now[i].value>=mid){ then[r++].value=now[i].value; now[i].is_right=true; }else{ then[l++].value=now[i].value; now[i].is_right=false; } } now[left].right=now[left].is_right; for(i=left+1;i<=right;i++){ now[i].right=now[i-1].right+now[i].is_right; } if(left == right) return 0; build_tree(left,tree[pos].mid,deepth+1,pos<<1); build_tree(tree[pos].mid+1,right,deepth+1,(pos<<1)+1); return 0; } int query(int left,int right,int k,int deepth,int pos){ int num=0; point *now=po[deepth]; if(tree[pos].left == tree[pos].right) return now[tree[pos].left].value; num=right-left+1-(now[right].right-now[left].right+now[left].is_right); if(num>=k) return query(left-now[left].right+now[left].is_right,right-now[right].right,k,deepth+1,pos<<1); else return query(tree[pos].mid+now[left].right+1-now[left].is_right,\ tree[pos].mid+now[right].right,k-num,deepth+1,(pos<<1)+1); } int find_ans(int a,int b,int num){ int mid,l=1,r=b-a+1,now,ans=-2000000010; while(l<=r){ mid=(l+r)>>1; now=query(a,b,mid,0,1); if(now <= num) l=mid+1; else{ r=mid-1; ans=now; } } return ans; } int main(){ int i,j,a,b,k,t,ans; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ scanf("%d",&rec[i]); po[0][i].value=rec[i]; } sort(rec+1,rec+1+n); build_tree(1,n,1,1); while(m--){ scanf("%d%d%d",&a,&b,&k); ans=find_ans(a,b,k); if(ans>k){ printf("%d\n",ans); }else{ printf("not exist\n"); } } } return 0; }