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 2 // Range Minimum Query
3 3 // O(N log N) construction
4 -// O(1) per each query
5 -// returns the LEFTMOST/ALL minimum index (I hope)
4 +// O(log N) per each query
6 5 //
7 6 // Verified by
8 7 // - SRM337 Div1 LV2
9 8 // - SRM431 Div1 LV3
9 +// - Codeforces 129 Div1 E
10 10 //-------------------------------------------------------------
11 11
12 12 template<typename T>
13 13 struct RMQ
14 14 {
15 15 vector< vector<int> > rm;
16 16 vector<T> d;
................................................................................
26 26 rm.push_back( rm[k-1] );
27 27 for(int x=0; x+(1<<k-1)<n; ++x)
28 28 if( d[rm[k][x]] > d[rm[k-1][x + (1<<k-1)]] )
29 29 rm[k][x] = rm[k-1][x + (1<<k-1)];
30 30 }
31 31 }
32 32
33 - int operator()(int L, int R) const { // inclusive
33 + // min {i in [L,R] | d[i] is minumum among d[L..R]}
34 + int operator()(int L, int R) const {
34 35 int k=0;
35 36 for(; L+(1<<k) < R-(1<<k)+1; ++k) {}
36 - LL i = rm[k][L];
37 - LL j = rm[k][R-(1<<k)+1];
37 + int i = rm[k][L];
38 + int j = rm[k][R-(1<<k)+1];
38 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 43 vector<int> all(int L, int R) const {
42 44 vector<int> ans;
43 45 int minValue = d[(*this)(L, R)];
44 46 while( L <= R ) {
45 47 int C = (*this)(L, R);
46 48 if( minValue < d[C] )
47 49 break;
48 50 ans.push_back(C);
49 51 L = C+1;
50 52 }
51 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 };