Artifact a0dd84df47a73891341ee803993c750cd094848c:
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 31 29 20 70 65 ion.// O(1) pe
0080: 72 20 65 61 63 68 20 71 75 65 72 79 0a 2f 2f 20 r each query.//
0090: 20 20 72 65 74 75 72 6e 73 20 74 68 65 20 4c 45 returns the LE
00a0: 46 54 4d 4f 53 54 2f 41 4c 4c 20 6d 69 6e 69 6d FTMOST/ALL minim
00b0: 75 6d 20 69 6e 64 65 78 20 28 49 20 68 6f 70 65 um index (I hope
00c0: 29 0a 2f 2f 0a 2f 2f 20 56 65 72 69 66 69 65 64 ).//.// Verified
00d0: 20 62 79 0a 2f 2f 20 20 20 2d 20 53 52 4d 33 33 by.// - SRM33
00e0: 37 20 44 69 76 31 20 4c 56 32 0a 2f 2f 20 20 20 7 Div1 LV2.//
00f0: 2d 20 53 52 4d 34 33 31 20 44 69 76 31 20 4c 56 - SRM431 Div1 LV
0100: 33 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 3.//------------
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 2d 2d 2d ----------------
0130: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0140: 2d 0a 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 -..template<type
0150: 6e 61 6d 65 20 54 3e 0a 73 74 72 75 63 74 20 52 name T>.struct R
0160: 4d 51 0a 7b 0a 09 76 65 63 74 6f 72 3c 20 76 65 MQ.{..vector< ve
0170: 63 74 6f 72 3c 69 6e 74 3e 20 3e 20 72 6d 3b 0a ctor<int> > rm;.
0180: 09 76 65 63 74 6f 72 3c 54 3e 20 64 3b 0a 0a 09 .vector<T> d;...
0190: 52 4d 51 28 20 63 6f 6e 73 74 20 76 65 63 74 6f RMQ( const vecto
01a0: 72 3c 54 3e 26 20 64 20 29 20 3a 20 64 28 64 29 r<T>& d ) : d(d)
01b0: 20 7b 0a 09 09 69 6e 74 20 6e 20 3d 20 64 2e 73 {...int n = d.s
01c0: 69 7a 65 28 29 3b 0a 0a 09 09 2f 2f 20 72 6d 5b ize();....// rm[
01d0: 6b 5d 5b 78 5d 20 3d 20 69 20 73 2e 74 2e 20 64 k][x] = i s.t. d
01e0: 5b 69 5d 20 69 73 20 74 68 65 20 6d 69 6e 69 6d [i] is the minim
01f0: 75 6d 20 69 6e 20 5b 78 2c 20 78 2b 32 5e 6b 29 um in [x, x+2^k)
0200: 0a 09 09 72 6d 2e 70 75 73 68 5f 62 61 63 6b 28 ...rm.push_back(
0210: 20 76 65 63 74 6f 72 3c 69 6e 74 3e 28 6e 29 20 vector<int>(n)
0220: 29 3b 0a 09 09 66 6f 72 28 69 6e 74 20 78 3d 30 );...for(int x=0
0230: 3b 20 78 3c 6e 3b 20 2b 2b 78 29 0a 09 09 09 72 ; x<n; ++x)....r
0240: 6d 5b 30 5d 5b 78 5d 20 3d 20 78 3b 0a 09 09 66 m[0][x] = x;...f
0250: 6f 72 28 69 6e 74 20 6b 3d 31 3b 20 28 31 3c 3c or(int k=1; (1<<
0260: 6b 29 3c 3d 6e 3b 20 2b 2b 6b 29 20 7b 0a 09 09 k)<=n; ++k) {...
0270: 09 72 6d 2e 70 75 73 68 5f 62 61 63 6b 28 20 72 .rm.push_back( r
0280: 6d 5b 6b 2d 31 5d 20 29 3b 0a 09 09 09 66 6f 72 m[k-1] );....for
0290: 28 69 6e 74 20 78 3d 30 3b 20 78 2b 28 31 3c 3c (int x=0; x+(1<<
02a0: 6b 2d 31 29 3c 6e 3b 20 2b 2b 78 29 0a 09 09 09 k-1)<n; ++x)....
02b0: 09 69 66 28 20 64 5b 72 6d 5b 6b 5d 5b 78 5d 5d .if( d[rm[k][x]]
02c0: 20 3e 20 64 5b 72 6d 5b 6b 2d 31 5d 5b 78 20 2b > d[rm[k-1][x +
02d0: 20 28 31 3c 3c 6b 2d 31 29 5d 5d 20 29 0a 09 09 (1<<k-1)]] )...
02e0: 09 09 09 72 6d 5b 6b 5d 5b 78 5d 20 3d 20 72 6d ...rm[k][x] = rm
02f0: 5b 6b 2d 31 5d 5b 78 20 2b 20 28 31 3c 3c 6b 2d [k-1][x + (1<<k-
0300: 31 29 5d 3b 0a 09 09 7d 0a 09 7d 0a 0a 09 69 6e 1)];...}..}...in
0310: 74 20 6f 70 65 72 61 74 6f 72 28 29 28 69 6e 74 t operator()(int
0320: 20 4c 2c 20 69 6e 74 20 52 29 20 63 6f 6e 73 74 L, int R) const
0330: 20 7b 20 2f 2f 20 69 6e 63 6c 75 73 69 76 65 0a { // inclusive.
0340: 09 09 69 6e 74 20 6b 3d 30 3b 0a 09 09 66 6f 72 ..int k=0;...for
0350: 28 3b 20 4c 2b 28 31 3c 3c 6b 29 20 3c 20 52 2d (; L+(1<<k) < R-
0360: 28 31 3c 3c 6b 29 2b 31 3b 20 2b 2b 6b 29 20 7b (1<<k)+1; ++k) {
0370: 7d 0a 09 09 4c 4c 20 69 20 3d 20 72 6d 5b 6b 5d }...LL i = rm[k]
0380: 5b 4c 5d 3b 0a 09 09 4c 4c 20 6a 20 3d 20 72 6d [L];...LL j = rm
0390: 5b 6b 5d 5b 52 2d 28 31 3c 3c 6b 29 2b 31 5d 3b [k][R-(1<<k)+1];
03a0: 0a 09 09 72 65 74 75 72 6e 20 28 64 5b 69 5d 3c ...return (d[i]<
03b0: 3d 64 5b 6a 5d 20 3f 20 69 20 3a 20 6a 29 3b 0a =d[j] ? i : j);.
03c0: 09 7d 0a 0a 09 76 65 63 74 6f 72 3c 69 6e 74 3e .}...vector<int>
03d0: 20 61 6c 6c 28 69 6e 74 20 4c 2c 20 69 6e 74 20 all(int L, int
03e0: 52 29 20 63 6f 6e 73 74 20 7b 0a 09 09 76 65 63 R) const {...vec
03f0: 74 6f 72 3c 69 6e 74 3e 20 61 6e 73 3b 0a 09 09 tor<int> ans;...
0400: 69 6e 74 20 6d 69 6e 56 61 6c 75 65 20 3d 20 64 int minValue = d
0410: 5b 28 2a 74 68 69 73 29 28 4c 2c 20 52 29 5d 3b [(*this)(L, R)];
0420: 0a 09 09 77 68 69 6c 65 28 20 4c 20 3c 3d 20 52 ...while( L <= R
0430: 20 29 20 7b 0a 09 09 09 69 6e 74 20 43 20 3d 20 ) {....int C =
0440: 28 2a 74 68 69 73 29 28 4c 2c 20 52 29 3b 0a 09 (*this)(L, R);..
0450: 09 09 69 66 28 20 6d 69 6e 56 61 6c 75 65 20 3c ..if( minValue <
0460: 20 64 5b 43 5d 20 29 0a 09 09 09 09 62 72 65 61 d[C] ).....brea
0470: 6b 3b 0a 09 09 09 61 6e 73 2e 70 75 73 68 5f 62 k;....ans.push_b
0480: 61 63 6b 28 43 29 3b 0a 09 09 09 4c 20 3d 20 43 ack(C);....L = C
0490: 2b 31 3b 0a 09 09 7d 0a 09 09 72 65 74 75 72 6e +1;...}...return
04a0: 20 61 6e 73 3b 0a 09 7d 0a 7d 3b 0a ans;..}.};.