Differences From Artifact [a0dd84df47a73891]:
- File
_lib/dataStructure/rmq.cpp
- 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
- File
lib/dataStructure/rmq.cpp
- 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]
To Artifact [b1b5e925fa550aa0]:
- File
lib/dataStructure/rmq.cpp
- 2012-07-22 18:00:41 - part of checkin [cd0467fefc] on branch trunk - Suffix Array. (user: kinaba) [annotate]
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 };