Artifact 8e84d319ff86cb61de52f2b3b463b3e242ab6b7d:
0000: 2f 2f 0a 2f 2f 20 61 63 63 75 6d 75 6c 61 74 69 //.// accumulati
0010: 76 65 20 6d 61 70 0a 2f 2f 20 20 20 62 61 73 69 ve map.// basi
0020: 63 61 6c 6c 79 20 61 20 6d 61 70 3c 4b 2c 56 3e cally a map<K,V>
0030: 2c 20 62 75 74 20 69 74 20 65 6c 69 6d 69 6e 61 , but it elimina
0040: 74 65 73 20 64 75 70 6c 69 63 61 74 69 6f 6e 20 tes duplication
0050: 6c 61 7a 69 6c 79 0a 2f 2f 20 20 20 66 69 72 73 lazily.// firs
0060: 74 20 6b 65 65 70 20 61 6c 6c 20 69 6e 73 65 72 t keep all inser
0070: 74 65 64 20 65 6c 65 6d 65 6e 74 73 20 69 6e 20 ted elements in
0080: 61 20 76 65 63 74 6f 72 2e 20 6f 6e 6c 79 20 77 a vector. only w
0090: 68 65 6e 20 74 68 65 20 62 75 66 66 65 72 0a 2f hen the buffer./
00a0: 2f 20 20 20 6f 76 65 72 66 6c 6f 77 73 2c 20 69 / overflows, i
00b0: 74 20 65 6c 69 6d 69 6e 61 74 65 73 20 64 75 70 t eliminates dup
00c0: 6c 69 63 61 74 69 6f 6e 0a 2f 2f 0a 0a 74 65 6d lication.//..tem
00d0: 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 4b plate<typename K
00e0: 2c 20 74 79 70 65 6e 61 6d 65 20 56 2c 20 69 6e , typename V, in
00f0: 74 20 4c 49 4d 49 54 20 3d 20 28 31 3c 3c 32 36 t LIMIT = (1<<26
0100: 29 2f 33 2f 73 69 7a 65 6f 66 28 70 61 69 72 3c )/3/sizeof(pair<
0110: 4b 2c 56 3e 29 3e 0a 73 74 72 75 63 74 20 61 6d K,V>)>.struct am
0120: 61 70 0a 7b 0a 09 74 79 70 65 64 65 66 20 74 79 ap.{..typedef ty
0130: 70 65 6e 61 6d 65 20 76 65 63 74 6f 72 3c 20 70 pename vector< p
0140: 61 69 72 3c 4b 2c 56 3e 20 3e 3a 3a 69 74 65 72 air<K,V> >::iter
0150: 61 74 6f 72 20 69 74 65 72 61 74 6f 72 3b 0a 0a ator iterator;..
0160: 09 76 65 63 74 6f 72 3c 20 70 61 69 72 3c 4b 2c .vector< pair<K,
0170: 56 3e 20 3e 20 6b 76 3b 0a 09 61 6d 61 70 28 29 V> > kv;..amap()
0180: 20 7b 20 6b 76 2e 72 65 73 65 72 76 65 28 4c 49 { kv.reserve(LI
0190: 4d 49 54 29 3b 20 7d 0a 0a 09 76 6f 69 64 20 61 MIT); }...void a
01a0: 64 64 28 63 6f 6e 73 74 20 4b 26 20 6b 2c 20 63 dd(const K& k, c
01b0: 6f 6e 73 74 20 56 26 20 76 29 0a 09 7b 0a 09 09 onst V& v)..{...
01c0: 6b 76 2e 70 75 73 68 5f 62 61 63 6b 28 20 6d 61 kv.push_back( ma
01d0: 6b 65 5f 70 61 69 72 28 6b 2c 76 29 20 29 3b 0a ke_pair(k,v) );.
01e0: 09 09 69 66 28 20 6b 76 2e 73 69 7a 65 28 29 20 ..if( kv.size()
01f0: 3d 3d 20 4c 49 4d 49 54 20 29 0a 09 09 09 6e 6f == LIMIT )....no
0200: 72 6d 61 6c 69 7a 65 28 29 3b 0a 09 7d 0a 0a 09 rmalize();..}...
0210: 69 74 65 72 61 74 6f 72 20 62 65 67 69 6e 28 29 iterator begin()
0220: 20 20 20 20 20 20 20 7b 20 72 65 74 75 72 6e 20 { return
0230: 6b 76 2e 62 65 67 69 6e 28 29 3b 20 7d 0a 09 69 kv.begin(); }..i
0240: 74 65 72 61 74 6f 72 20 65 6e 64 28 29 20 20 20 terator end()
0250: 20 20 20 20 20 20 7b 20 72 65 74 75 72 6e 20 6b { return k
0260: 76 2e 65 6e 64 28 29 3b 20 7d 0a 09 76 6f 69 64 v.end(); }..void
0270: 20 73 77 61 70 28 20 61 6d 61 70 26 20 72 68 73 swap( amap& rhs
0280: 20 29 20 7b 20 6b 76 2e 73 77 61 70 28 72 68 73 ) { kv.swap(rhs
0290: 2e 6b 76 29 3b 20 7d 0a 0a 09 2f 2f 20 54 65 73 .kv); }...// Tes
02a0: 74 65 64 3a 20 53 52 4d 20 34 36 39 20 4c 76 33 ted: SRM 469 Lv3
02b0: 0a 09 76 6f 69 64 20 6e 6f 72 6d 61 6c 69 7a 65 ..void normalize
02c0: 28 29 0a 09 7b 0a 09 09 73 6f 72 74 28 6b 76 2e ()..{...sort(kv.
02d0: 62 65 67 69 6e 28 29 2c 20 6b 76 2e 65 6e 64 28 begin(), kv.end(
02e0: 29 29 3b 0a 09 09 69 6e 74 20 69 3d 30 3b 0a 09 ));...int i=0;..
02f0: 09 66 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a 3c .for(int j=0; j<
0300: 6b 76 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0a kv.size(); ++i).
0310: 09 09 7b 0a 09 09 09 69 6e 74 20 6b 20 3d 20 6a ..{....int k = j
0320: 3b 0a 09 09 09 6b 76 5b 69 5d 20 3d 20 6b 76 5b ;....kv[i] = kv[
0330: 6b 5d 3b 0a 09 09 09 77 68 69 6c 65 28 20 2b 2b k];....while( ++
0340: 6a 3c 6b 76 2e 73 69 7a 65 28 29 20 26 26 20 6b j<kv.size() && k
0350: 76 5b 6b 5d 2e 66 69 72 73 74 3d 3d 6b 76 5b 6a v[k].first==kv[j
0360: 5d 2e 66 69 72 73 74 20 29 0a 09 09 09 09 6b 76 ].first ).....kv
0370: 5b 69 5d 2e 73 65 63 6f 6e 64 20 2b 3d 20 6b 76 [i].second += kv
0380: 5b 6a 5d 2e 73 65 63 6f 6e 64 3b 0a 09 09 7d 0a [j].second;...}.
0390: 09 09 6b 76 2e 72 65 73 69 7a 65 28 69 29 3b 0a ..kv.resize(i);.
03a0: 09 7d 0a 2f 2a 0a 09 2f 2f 20 4e 6f 74 20 54 65 .}./*..// Not Te
03b0: 73 74 65 64 20 28 50 72 65 66 65 72 20 46 69 72 sted (Prefer Fir
03c0: 73 74 29 0a 09 76 6f 69 64 20 6e 6f 72 6d 61 6c st)..void normal
03d0: 69 7a 65 28 29 0a 09 7b 0a 09 09 73 6f 72 74 28 ize()..{...sort(
03e0: 6b 76 2e 62 65 67 69 6e 28 29 2c 20 6b 76 2e 65 kv.begin(), kv.e
03f0: 6e 64 28 29 29 3b 0a 09 09 69 6e 74 20 69 3d 30 nd());...int i=0
0400: 3b 0a 09 09 66 6f 72 28 69 6e 74 20 6a 3d 30 3b ;...for(int j=0;
0410: 20 6a 3c 6b 76 2e 73 69 7a 65 28 29 3b 20 2b 2b j<kv.size(); ++
0420: 69 29 0a 09 09 7b 0a 09 09 09 69 6e 74 20 6b 20 i)...{....int k
0430: 3d 20 6a 3b 0a 09 09 09 6b 76 5b 69 5d 20 3d 20 = j;....kv[i] =
0440: 6b 76 5b 6b 5d 3b 0a 09 09 09 77 68 69 6c 65 28 kv[k];....while(
0450: 20 2b 2b 6a 3c 6b 76 2e 73 69 7a 65 28 29 20 26 ++j<kv.size() &
0460: 26 20 6b 76 5b 6b 5d 2e 66 69 72 73 74 3d 3d 6b & kv[k].first==k
0470: 76 5b 6a 5d 2e 66 69 72 73 74 20 29 0a 09 09 09 v[j].first )....
0480: 09 7b 7d 0a 09 09 7d 0a 09 09 6b 76 2e 72 65 73 .{}...}...kv.res
0490: 69 7a 65 28 69 29 3b 0a 09 7d 0a 0a 09 2f 2f 20 ize(i);..}...//
04a0: 4e 6f 74 20 54 65 73 74 65 64 20 28 50 72 65 66 Not Tested (Pref
04b0: 65 72 20 4c 61 73 74 29 0a 09 76 6f 69 64 20 6e er Last)..void n
04c0: 6f 72 6d 61 6c 69 7a 65 28 29 0a 09 7b 0a 09 09 ormalize()..{...
04d0: 73 6f 72 74 28 6b 76 2e 62 65 67 69 6e 28 29 2c sort(kv.begin(),
04e0: 20 6b 76 2e 65 6e 64 28 29 29 3b 0a 09 09 69 6e kv.end());...in
04f0: 74 20 69 3d 30 3b 0a 09 09 66 6f 72 28 69 6e 74 t i=0;...for(int
0500: 20 6a 3d 30 3b 20 6a 3c 6b 76 2e 73 69 7a 65 28 j=0; j<kv.size(
0510: 29 3b 20 2b 2b 69 29 0a 09 09 7b 0a 09 09 09 69 ); ++i)...{....i
0520: 6e 74 20 6b 20 3d 20 6a 3b 0a 09 09 09 77 68 69 nt k = j;....whi
0530: 6c 65 28 20 2b 2b 6a 3c 6b 76 2e 73 69 7a 65 28 le( ++j<kv.size(
0540: 29 20 26 26 20 6b 76 5b 6b 5d 2e 66 69 72 73 74 ) && kv[k].first
0550: 3d 3d 6b 76 5b 6a 5d 2e 66 69 72 73 74 20 29 0a ==kv[j].first ).
0560: 09 09 09 09 7b 7d 0a 09 09 09 6b 76 5b 69 5d 20 ....{}....kv[i]
0570: 3d 20 6b 76 5b 6a 2d 31 5d 3b 0a 09 09 7d 0a 09 = kv[j-1];...}..
0580: 09 6b 76 2e 72 65 73 69 7a 65 28 69 29 3b 0a 09 .kv.resize(i);..
0590: 7d 0a 2a 2f 0a 7d 3b 0a }.*/.};.