1 //------------------------------------------------------------- 1 //------------------------------------------------------------- 2 // Range Minimum Query 2 // Range Minimum Query 3 // O(N log N) construction 3 // O(N log N) construction 4 // O(1) per each query | 4 // O(log N) per each query 5 // returns the LEFTMOST/ALL minimum index (I hope) < 6 // 5 // 7 // Verified by 6 // Verified by 8 // - SRM337 Div1 LV2 7 // - SRM337 Div1 LV2 9 // - SRM431 Div1 LV3 8 // - SRM431 Div1 LV3 > 9 // - Codeforces 129 Div1 E 10 //------------------------------------------------------------- 10 //------------------------------------------------------------- 11 11 12 template<typename T> 12 template<typename T> 13 struct RMQ 13 struct RMQ 14 { 14 { 15 vector< vector<int> > rm; 15 vector< vector<int> > rm; 16 vector<T> d; 16 vector<T> d; ................................................................................................................................................................................ 26 rm.push_back( rm[k-1] ); 26 rm.push_back( rm[k-1] ); 27 for(int x=0; x+(1<<k-1)<n; ++x) 27 for(int x=0; x+(1<<k-1)<n; ++x) 28 if( d[rm[k][x]] > d[rm[k-1][x + (1<<k-1)]] ) 28 if( d[rm[k][x]] > d[rm[k-1][x + (1<<k-1)]] ) 29 rm[k][x] = rm[k-1][x + (1<<k-1)]; 29 rm[k][x] = rm[k-1][x + (1<<k-1)]; 30 } 30 } 31 } 31 } 32 32 > 33 // min {i in [L,R] | d[i] is minumum among d[L..R]} 33 int operator()(int L, int R) const { // inclusive | 34 int operator()(int L, int R) const { 34 int k=0; 35 int k=0; 35 for(; L+(1<<k) < R-(1<<k)+1; ++k) {} 36 for(; L+(1<<k) < R-(1<<k)+1; ++k) {} 36 LL i = rm[k][L]; | 37 int i = rm[k][L]; 37 LL j = rm[k][R-(1<<k)+1]; | 38 int j = rm[k][R-(1<<k)+1]; 38 return (d[i]<=d[j] ? i : j); 39 return (d[i]<=d[j] ? i : j); 39 } 40 } 40 41 > 42 // {i in [L,R] | d[i] is minumum among d[L..R]} 41 vector<int> all(int L, int R) const { 43 vector<int> all(int L, int R) const { 42 vector<int> ans; 44 vector<int> ans; 43 int minValue = d[(*this)(L, R)]; 45 int minValue = d[(*this)(L, R)]; 44 while( L <= R ) { 46 while( L <= R ) { 45 int C = (*this)(L, R); 47 int C = (*this)(L, R); 46 if( minValue < d[C] ) 48 if( minValue < d[C] ) 47 break; 49 break; 48 ans.push_back(C); 50 ans.push_back(C); 49 L = C+1; 51 L = C+1; 50 } 52 } 51 return ans; 53 return ans; 52 } 54 } > 55 > 56 // max {i in [L,R] | d[i]<X}, or -1 > 57 int rightmost_less_than_X(int L, int R, T X) const { > 58 if(L>R) return -1; > 59 > 60 int k=0; > 61 for(; L+(1<<k) < R-(1<<k)+1; ++k) {} > 62 > 63 int i = rm[k][L]; > 64 int j = rm[k][R-(1<<k)+1]; > 65 if( !(d[i]<X || d[j]<X) ) > 66 return -1; > 67 if( d[j] < X ) > 68 L = R-(1<<k)+1; > 69 > 70 for(; k; --k) { // Answer is in [L, L+(1<<k)) > 71 i = rm[k-1][L]; > 72 j = rm[k-1][L+(1<<k-1)]; > 73 if( d[j] < X ) > 74 L += 1<<k-1; > 75 } > 76 return L; > 77 } > 78 > 79 // min {i in [L,R] | d[i]<X}, or -1 > 80 int leftmost_less_than_X(int L, int R, T X) const { > 81 if(L>R) return -1; > 82 > 83 int k=0; > 84 for(; L+(1<<k) < R-(1<<k)+1; ++k) {} > 85 > 86 int i = rm[k][L]; > 87 int j = rm[k][R-(1<<k)+1]; > 88 if( !(d[i]<X || d[j]<X) ) > 89 return -1; > 90 if( !(d[i] < X) ) > 91 L = R-(1<<k)+1; > 92 > 93 for(; k; --k) { // Answer is in [L, L+(1<<k)) > 94 i = rm[k-1][L]; > 95 j = rm[k-1][L+(1<<k-1)]; > 96 if( !(d[i] < X) ) > 97 L += 1<<k-1; > 98 } > 99 return L; > 100 } 53 }; 101 };