Artifact b1b5e925fa550aa02370d2768fa3ae40a0742c90:
0000: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d //--------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
0040: 2f 2f 20 52 61 6e 67 65 20 4d 69 6e 69 6d 75 6d // Range Minimum
0050: 20 51 75 65 72 79 0a 2f 2f 20 20 20 4f 28 4e 20 Query.// O(N
0060: 6c 6f 67 20 4e 29 20 63 6f 6e 73 74 72 75 63 74 log N) construct
0070: 69 6f 6e 0a 2f 2f 20 20 20 4f 28 6c 6f 67 20 4e ion.// O(log N
0080: 29 20 70 65 72 20 65 61 63 68 20 71 75 65 72 79 ) per each query
0090: 0a 2f 2f 0a 2f 2f 20 56 65 72 69 66 69 65 64 20 .//.// Verified
00a0: 62 79 0a 2f 2f 20 20 20 2d 20 53 52 4d 33 33 37 by.// - SRM337
00b0: 20 44 69 76 31 20 4c 56 32 0a 2f 2f 20 20 20 2d Div1 LV2.// -
00c0: 20 53 52 4d 34 33 31 20 44 69 76 31 20 4c 56 33 SRM431 Div1 LV3
00d0: 0a 2f 2f 20 20 20 2d 20 43 6f 64 65 66 6f 72 63 .// - Codeforc
00e0: 65 73 20 31 32 39 20 44 69 76 31 20 45 0a 2f 2f es 129 Div1 E.//
00f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0100: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0110: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0120: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 74 -------------..t
0130: 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 emplate<typename
0140: 20 54 3e 0a 73 74 72 75 63 74 20 52 4d 51 0a 7b T>.struct RMQ.{
0150: 0a 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 ..vector< vector
0160: 3c 69 6e 74 3e 20 3e 20 72 6d 3b 0a 09 76 65 63 <int> > rm;..vec
0170: 74 6f 72 3c 54 3e 20 64 3b 0a 0a 09 52 4d 51 28 tor<T> d;...RMQ(
0180: 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 3e const vector<T>
0190: 26 20 64 20 29 20 3a 20 64 28 64 29 20 7b 0a 09 & d ) : d(d) {..
01a0: 09 69 6e 74 20 6e 20 3d 20 64 2e 73 69 7a 65 28 .int n = d.size(
01b0: 29 3b 0a 0a 09 09 2f 2f 20 72 6d 5b 6b 5d 5b 78 );....// rm[k][x
01c0: 5d 20 3d 20 69 20 73 2e 74 2e 20 64 5b 69 5d 20 ] = i s.t. d[i]
01d0: 69 73 20 74 68 65 20 6d 69 6e 69 6d 75 6d 20 69 is the minimum i
01e0: 6e 20 5b 78 2c 20 78 2b 32 5e 6b 29 0a 09 09 72 n [x, x+2^k)...r
01f0: 6d 2e 70 75 73 68 5f 62 61 63 6b 28 20 76 65 63 m.push_back( vec
0200: 74 6f 72 3c 69 6e 74 3e 28 6e 29 20 29 3b 0a 09 tor<int>(n) );..
0210: 09 66 6f 72 28 69 6e 74 20 78 3d 30 3b 20 78 3c .for(int x=0; x<
0220: 6e 3b 20 2b 2b 78 29 0a 09 09 09 72 6d 5b 30 5d n; ++x)....rm[0]
0230: 5b 78 5d 20 3d 20 78 3b 0a 09 09 66 6f 72 28 69 [x] = x;...for(i
0240: 6e 74 20 6b 3d 31 3b 20 28 31 3c 3c 6b 29 3c 3d nt k=1; (1<<k)<=
0250: 6e 3b 20 2b 2b 6b 29 20 7b 0a 09 09 09 72 6d 2e n; ++k) {....rm.
0260: 70 75 73 68 5f 62 61 63 6b 28 20 72 6d 5b 6b 2d push_back( rm[k-
0270: 31 5d 20 29 3b 0a 09 09 09 66 6f 72 28 69 6e 74 1] );....for(int
0280: 20 78 3d 30 3b 20 78 2b 28 31 3c 3c 6b 2d 31 29 x=0; x+(1<<k-1)
0290: 3c 6e 3b 20 2b 2b 78 29 0a 09 09 09 09 69 66 28 <n; ++x).....if(
02a0: 20 64 5b 72 6d 5b 6b 5d 5b 78 5d 5d 20 3e 20 64 d[rm[k][x]] > d
02b0: 5b 72 6d 5b 6b 2d 31 5d 5b 78 20 2b 20 28 31 3c [rm[k-1][x + (1<
02c0: 3c 6b 2d 31 29 5d 5d 20 29 0a 09 09 09 09 09 72 <k-1)]] )......r
02d0: 6d 5b 6b 5d 5b 78 5d 20 3d 20 72 6d 5b 6b 2d 31 m[k][x] = rm[k-1
02e0: 5d 5b 78 20 2b 20 28 31 3c 3c 6b 2d 31 29 5d 3b ][x + (1<<k-1)];
02f0: 0a 09 09 7d 0a 09 7d 0a 0a 09 2f 2f 20 6d 69 6e ...}..}...// min
0300: 20 7b 69 20 69 6e 20 5b 4c 2c 52 5d 20 7c 20 64 {i in [L,R] | d
0310: 5b 69 5d 20 69 73 20 6d 69 6e 75 6d 75 6d 20 61 [i] is minumum a
0320: 6d 6f 6e 67 20 64 5b 4c 2e 2e 52 5d 7d 0a 09 69 mong d[L..R]}..i
0330: 6e 74 20 6f 70 65 72 61 74 6f 72 28 29 28 69 6e nt operator()(in
0340: 74 20 4c 2c 20 69 6e 74 20 52 29 20 63 6f 6e 73 t L, int R) cons
0350: 74 20 7b 0a 09 09 69 6e 74 20 6b 3d 30 3b 0a 09 t {...int k=0;..
0360: 09 66 6f 72 28 3b 20 4c 2b 28 31 3c 3c 6b 29 20 .for(; L+(1<<k)
0370: 3c 20 52 2d 28 31 3c 3c 6b 29 2b 31 3b 20 2b 2b < R-(1<<k)+1; ++
0380: 6b 29 20 7b 7d 0a 09 09 69 6e 74 20 69 20 3d 20 k) {}...int i =
0390: 72 6d 5b 6b 5d 5b 4c 5d 3b 0a 09 09 69 6e 74 20 rm[k][L];...int
03a0: 6a 20 3d 20 72 6d 5b 6b 5d 5b 52 2d 28 31 3c 3c j = rm[k][R-(1<<
03b0: 6b 29 2b 31 5d 3b 0a 09 09 72 65 74 75 72 6e 20 k)+1];...return
03c0: 28 64 5b 69 5d 3c 3d 64 5b 6a 5d 20 3f 20 69 20 (d[i]<=d[j] ? i
03d0: 3a 20 6a 29 3b 0a 09 7d 0a 0a 09 2f 2f 20 7b 69 : j);..}...// {i
03e0: 20 69 6e 20 5b 4c 2c 52 5d 20 7c 20 64 5b 69 5d in [L,R] | d[i]
03f0: 20 69 73 20 6d 69 6e 75 6d 75 6d 20 61 6d 6f 6e is minumum amon
0400: 67 20 64 5b 4c 2e 2e 52 5d 7d 0a 09 76 65 63 74 g d[L..R]}..vect
0410: 6f 72 3c 69 6e 74 3e 20 61 6c 6c 28 69 6e 74 20 or<int> all(int
0420: 4c 2c 20 69 6e 74 20 52 29 20 63 6f 6e 73 74 20 L, int R) const
0430: 7b 0a 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 {...vector<int>
0440: 61 6e 73 3b 0a 09 09 69 6e 74 20 6d 69 6e 56 61 ans;...int minVa
0450: 6c 75 65 20 3d 20 64 5b 28 2a 74 68 69 73 29 28 lue = d[(*this)(
0460: 4c 2c 20 52 29 5d 3b 0a 09 09 77 68 69 6c 65 28 L, R)];...while(
0470: 20 4c 20 3c 3d 20 52 20 29 20 7b 0a 09 09 09 69 L <= R ) {....i
0480: 6e 74 20 43 20 3d 20 28 2a 74 68 69 73 29 28 4c nt C = (*this)(L
0490: 2c 20 52 29 3b 0a 09 09 09 69 66 28 20 6d 69 6e , R);....if( min
04a0: 56 61 6c 75 65 20 3c 20 64 5b 43 5d 20 29 0a 09 Value < d[C] )..
04b0: 09 09 09 62 72 65 61 6b 3b 0a 09 09 09 61 6e 73 ...break;....ans
04c0: 2e 70 75 73 68 5f 62 61 63 6b 28 43 29 3b 0a 09 .push_back(C);..
04d0: 09 09 4c 20 3d 20 43 2b 31 3b 0a 09 09 7d 0a 09 ..L = C+1;...}..
04e0: 09 72 65 74 75 72 6e 20 61 6e 73 3b 0a 09 7d 0a .return ans;..}.
04f0: 0a 09 2f 2f 20 6d 61 78 20 7b 69 20 69 6e 20 5b ..// max {i in [
0500: 4c 2c 52 5d 20 7c 20 64 5b 69 5d 3c 58 7d 2c 20 L,R] | d[i]<X},
0510: 6f 72 20 2d 31 0a 09 69 6e 74 20 72 69 67 68 74 or -1..int right
0520: 6d 6f 73 74 5f 6c 65 73 73 5f 74 68 61 6e 5f 58 most_less_than_X
0530: 28 69 6e 74 20 4c 2c 20 69 6e 74 20 52 2c 20 54 (int L, int R, T
0540: 20 58 29 20 63 6f 6e 73 74 20 7b 0a 09 09 69 66 X) const {...if
0550: 28 4c 3e 52 29 20 72 65 74 75 72 6e 20 2d 31 3b (L>R) return -1;
0560: 0a 0a 09 09 69 6e 74 20 6b 3d 30 3b 0a 09 09 66 ....int k=0;...f
0570: 6f 72 28 3b 20 4c 2b 28 31 3c 3c 6b 29 20 3c 20 or(; L+(1<<k) <
0580: 52 2d 28 31 3c 3c 6b 29 2b 31 3b 20 2b 2b 6b 29 R-(1<<k)+1; ++k)
0590: 20 7b 7d 0a 0a 09 09 69 6e 74 20 69 20 3d 20 72 {}....int i = r
05a0: 6d 5b 6b 5d 5b 4c 5d 3b 0a 09 09 69 6e 74 20 6a m[k][L];...int j
05b0: 20 3d 20 72 6d 5b 6b 5d 5b 52 2d 28 31 3c 3c 6b = rm[k][R-(1<<k
05c0: 29 2b 31 5d 3b 0a 09 09 69 66 28 20 21 28 64 5b )+1];...if( !(d[
05d0: 69 5d 3c 58 20 7c 7c 20 64 5b 6a 5d 3c 58 29 20 i]<X || d[j]<X)
05e0: 29 0a 09 09 09 72 65 74 75 72 6e 20 2d 31 3b 0a )....return -1;.
05f0: 09 09 69 66 28 20 64 5b 6a 5d 20 3c 20 58 20 29 ..if( d[j] < X )
0600: 0a 09 09 09 4c 20 3d 20 52 2d 28 31 3c 3c 6b 29 ....L = R-(1<<k)
0610: 2b 31 3b 0a 0a 09 09 66 6f 72 28 3b 20 6b 3b 20 +1;....for(; k;
0620: 2d 2d 6b 29 20 7b 20 2f 2f 20 41 6e 73 77 65 72 --k) { // Answer
0630: 20 69 73 20 69 6e 20 5b 4c 2c 20 4c 2b 28 31 3c is in [L, L+(1<
0640: 3c 6b 29 29 0a 09 09 09 69 20 3d 20 72 6d 5b 6b <k))....i = rm[k
0650: 2d 31 5d 5b 4c 5d 3b 0a 09 09 09 6a 20 3d 20 72 -1][L];....j = r
0660: 6d 5b 6b 2d 31 5d 5b 4c 2b 28 31 3c 3c 6b 2d 31 m[k-1][L+(1<<k-1
0670: 29 5d 3b 0a 09 09 09 69 66 28 20 64 5b 6a 5d 20 )];....if( d[j]
0680: 3c 20 58 20 29 0a 09 09 09 09 4c 20 2b 3d 20 31 < X ).....L += 1
0690: 3c 3c 6b 2d 31 3b 0a 09 09 7d 0a 09 09 72 65 74 <<k-1;...}...ret
06a0: 75 72 6e 20 4c 3b 0a 09 7d 0a 0a 09 2f 2f 20 6d urn L;..}...// m
06b0: 69 6e 20 7b 69 20 69 6e 20 5b 4c 2c 52 5d 20 7c in {i in [L,R] |
06c0: 20 64 5b 69 5d 3c 58 7d 2c 20 6f 72 20 2d 31 0a d[i]<X}, or -1.
06d0: 09 69 6e 74 20 6c 65 66 74 6d 6f 73 74 5f 6c 65 .int leftmost_le
06e0: 73 73 5f 74 68 61 6e 5f 58 28 69 6e 74 20 4c 2c ss_than_X(int L,
06f0: 20 69 6e 74 20 52 2c 20 54 20 58 29 20 63 6f 6e int R, T X) con
0700: 73 74 20 7b 0a 09 09 69 66 28 4c 3e 52 29 20 72 st {...if(L>R) r
0710: 65 74 75 72 6e 20 2d 31 3b 0a 0a 09 09 69 6e 74 eturn -1;....int
0720: 20 6b 3d 30 3b 0a 09 09 66 6f 72 28 3b 20 4c 2b k=0;...for(; L+
0730: 28 31 3c 3c 6b 29 20 3c 20 52 2d 28 31 3c 3c 6b (1<<k) < R-(1<<k
0740: 29 2b 31 3b 20 2b 2b 6b 29 20 7b 7d 0a 0a 09 09 )+1; ++k) {}....
0750: 69 6e 74 20 69 20 3d 20 72 6d 5b 6b 5d 5b 4c 5d int i = rm[k][L]
0760: 3b 0a 09 09 69 6e 74 20 6a 20 3d 20 72 6d 5b 6b ;...int j = rm[k
0770: 5d 5b 52 2d 28 31 3c 3c 6b 29 2b 31 5d 3b 0a 09 ][R-(1<<k)+1];..
0780: 09 69 66 28 20 21 28 64 5b 69 5d 3c 58 20 7c 7c .if( !(d[i]<X ||
0790: 20 64 5b 6a 5d 3c 58 29 20 29 0a 09 09 09 72 65 d[j]<X) )....re
07a0: 74 75 72 6e 20 2d 31 3b 0a 09 09 69 66 28 20 21 turn -1;...if( !
07b0: 28 64 5b 69 5d 20 3c 20 58 29 20 29 0a 09 09 09 (d[i] < X) )....
07c0: 4c 20 3d 20 52 2d 28 31 3c 3c 6b 29 2b 31 3b 0a L = R-(1<<k)+1;.
07d0: 0a 09 09 66 6f 72 28 3b 20 6b 3b 20 2d 2d 6b 29 ...for(; k; --k)
07e0: 20 7b 20 2f 2f 20 41 6e 73 77 65 72 20 69 73 20 { // Answer is
07f0: 69 6e 20 5b 4c 2c 20 4c 2b 28 31 3c 3c 6b 29 29 in [L, L+(1<<k))
0800: 0a 09 09 09 69 20 3d 20 72 6d 5b 6b 2d 31 5d 5b ....i = rm[k-1][
0810: 4c 5d 3b 0a 09 09 09 6a 20 3d 20 72 6d 5b 6b 2d L];....j = rm[k-
0820: 31 5d 5b 4c 2b 28 31 3c 3c 6b 2d 31 29 5d 3b 0a 1][L+(1<<k-1)];.
0830: 09 09 09 69 66 28 20 21 28 64 5b 69 5d 20 3c 20 ...if( !(d[i] <
0840: 58 29 20 29 0a 09 09 09 09 4c 20 2b 3d 20 31 3c X) ).....L += 1<
0850: 3c 6b 2d 31 3b 0a 09 09 7d 0a 09 09 72 65 74 75 <k-1;...}...retu
0860: 72 6e 20 4c 3b 0a 09 7d 0a 7d 3b 0a rn L;..}.};.