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 53 65 67 6d 65 6e 74 20 74 72 65 65 0a // Segment tree.
0050: 2f 2f 20 20 20 69 6e 20 73 6f 6d 65 20 67 65 6e // in some gen
0060: 65 72 61 6c 20 66 6f 72 6d 0a 2f 2f 0a 2f 2f 20 eral form.//.//
0070: 56 65 72 69 66 69 65 64 20 62 79 0a 2f 2f 20 20 Verified by.//
0080: 20 2d 20 43 6f 64 65 66 6f 72 63 65 73 20 32 30 - Codeforces 20
0090: 30 20 44 0a 2f 2f 20 20 20 2d 20 43 6f 64 65 66 0 D.// - Codef
00a0: 6f 72 63 65 73 20 31 30 37 20 43 20 28 6f 6c 64 orces 107 C (old
00b0: 20 76 65 72 73 69 6f 6e 29 0a 2f 2f 20 20 20 2d version).// -
00c0: 20 43 6f 64 65 66 6f 72 63 65 73 20 31 30 34 20 Codeforces 104
00d0: 45 20 28 6f 6c 64 20 76 65 72 73 69 6f 6e 29 0a E (old version).
00e0: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d //--------------
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 0a ---------------.
0120: 0a 63 6c 61 73 73 20 53 65 67 6d 65 6e 74 54 72 .class SegmentTr
0130: 65 65 0a 7b 0a 09 73 74 72 75 63 74 20 4e 6f 64 ee.{..struct Nod
0140: 65 0a 09 7b 0a 09 09 69 6e 74 20 73 75 6d 3b 0a e..{...int sum;.
0150: 0a 09 09 73 74 61 74 69 63 20 4e 6f 64 65 20 5a ...static Node Z
0160: 65 72 6f 28 29 0a 09 09 7b 0a 09 09 09 4e 6f 64 ero()...{....Nod
0170: 65 20 63 20 3d 20 7b 30 7d 3b 0a 09 09 09 72 65 e c = {0};....re
0180: 74 75 72 6e 20 63 3b 0a 09 09 7d 0a 09 09 73 74 turn c;...}...st
0190: 61 74 69 63 20 4e 6f 64 65 20 4f 6e 65 28 69 6e atic Node One(in
01a0: 74 20 76 29 0a 09 09 7b 0a 09 09 09 4e 6f 64 65 t v)...{....Node
01b0: 20 63 20 3d 20 7b 76 7d 3b 0a 09 09 09 72 65 74 c = {v};....ret
01c0: 75 72 6e 20 63 3b 0a 09 09 7d 0a 09 09 73 74 61 urn c;...}...sta
01d0: 74 69 63 20 4e 6f 64 65 20 43 6f 6e 63 61 74 28 tic Node Concat(
01e0: 63 6f 6e 73 74 20 4e 6f 64 65 26 20 6c 2c 20 63 const Node& l, c
01f0: 6f 6e 73 74 20 4e 6f 64 65 26 20 72 29 0a 09 09 onst Node& r)...
0200: 7b 0a 09 09 09 4e 6f 64 65 20 63 20 3d 20 7b 6c {....Node c = {l
0210: 2e 73 75 6d 20 2b 20 72 2e 73 75 6d 7d 3b 0a 09 .sum + r.sum};..
0220: 09 09 72 65 74 75 72 6e 20 63 3b 0a 09 09 7d 0a ..return c;...}.
0230: 09 09 73 74 61 74 69 63 20 4e 6f 64 65 20 52 65 ..static Node Re
0240: 70 65 61 74 28 63 6f 6e 73 74 20 4e 6f 64 65 26 peat(const Node&
0250: 20 6e 2c 20 69 6e 74 20 6b 29 0a 09 09 7b 0a 09 n, int k)...{..
0260: 09 09 4e 6f 64 65 20 63 20 3d 20 7b 6e 2e 73 75 ..Node c = {n.su
0270: 6d 20 2a 20 6b 7d 3b 0a 09 09 09 72 65 74 75 72 m * k};....retur
0280: 6e 20 63 3b 0a 09 09 7d 0a 0a 09 09 62 6f 6f 6c n c;...}....bool
0290: 20 6c 61 7a 79 3b 0a 09 7d 3b 0a 0a 70 75 62 6c lazy;..};..publ
02a0: 69 63 3a 0a 09 74 65 6d 70 6c 61 74 65 3c 74 79 ic:..template<ty
02b0: 70 65 6e 61 6d 65 20 53 65 71 3e 0a 09 53 65 67 pename Seq>..Seg
02c0: 6d 65 6e 74 54 72 65 65 28 63 6f 6e 73 74 20 53 mentTree(const S
02d0: 65 71 26 20 73 29 20 7b 0a 09 09 69 6e 74 20 4e eq& s) {...int N
02e0: 20 3d 20 31 3b 0a 09 09 77 68 69 6c 65 28 20 4e = 1;...while( N
02f0: 20 3c 20 73 2e 73 69 7a 65 28 29 20 29 0a 09 09 < s.size() )...
0300: 09 4e 20 3c 3c 3d 20 31 3b 0a 0a 09 09 74 72 65 .N <<= 1;....tre
0310: 65 2e 72 65 73 69 7a 65 28 74 72 65 65 2e 73 69 e.resize(tree.si
0320: 7a 65 28 29 2b 31 29 3b 20 74 72 65 65 2e 62 61 ze()+1); tree.ba
0330: 63 6b 28 29 2e 72 65 73 69 7a 65 28 4e 29 3b 0a ck().resize(N);.
0340: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
0350: 3c 4e 3b 20 2b 2b 69 29 0a 09 09 09 74 72 65 65 <N; ++i)....tree
0360: 2e 62 61 63 6b 28 29 5b 69 5d 20 3d 20 69 3c 73 .back()[i] = i<s
0370: 2e 73 69 7a 65 28 29 20 3f 20 4e 6f 64 65 3a 3a .size() ? Node::
0380: 4f 6e 65 28 73 5b 69 5d 29 20 3a 20 4e 6f 64 65 One(s[i]) : Node
0390: 3a 3a 5a 65 72 6f 28 29 3b 0a 0a 09 09 77 68 69 ::Zero();....whi
03a0: 6c 65 28 4e 3e 3e 3d 31 29 20 7b 0a 09 09 09 74 le(N>>=1) {....t
03b0: 72 65 65 2e 72 65 73 69 7a 65 28 74 72 65 65 2e ree.resize(tree.
03c0: 73 69 7a 65 28 29 2b 31 29 3b 20 74 72 65 65 2e size()+1); tree.
03d0: 62 61 63 6b 28 29 2e 72 65 73 69 7a 65 28 4e 29 back().resize(N)
03e0: 3b 0a 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 ;....for(int i=0
03f0: 3b 20 69 3c 4e 3b 20 2b 2b 69 29 0a 09 09 09 09 ; i<N; ++i).....
0400: 43 61 6c 63 4d 69 64 4e 6f 64 65 28 74 72 65 65 CalcMidNode(tree
0410: 2e 73 69 7a 65 28 29 2d 31 2c 20 69 29 3b 0a 09 .size()-1, i);..
0420: 09 7d 0a 09 7d 0a 0a 09 4e 6f 64 65 20 51 75 65 .}..}...Node Que
0430: 72 79 28 69 6e 74 20 73 2c 20 69 6e 74 20 65 29 ry(int s, int e)
0440: 20 7b 20 2f 2f 20 63 6f 6d 70 75 74 65 20 68 28 { // compute h(
0450: 20 73 65 71 5b 73 2c 65 29 20 29 20 3a 20 20 4f seq[s,e) ) : O
0460: 28 6c 6f 67 20 6e 29 0a 09 09 72 65 74 75 72 6e (log n)...return
0470: 20 51 75 65 72 79 52 65 63 28 73 2c 20 65 2c 20 QueryRec(s, e,
0480: 74 72 65 65 2e 73 69 7a 65 28 29 2d 31 2c 20 30 tree.size()-1, 0
0490: 2c 20 74 72 65 65 5b 30 5d 2e 73 69 7a 65 28 29 , tree[0].size()
04a0: 29 3b 0a 09 7d 0a 0a 09 74 65 6d 70 6c 61 74 65 );..}...template
04b0: 3c 74 79 70 65 6e 61 6d 65 20 56 61 6c 75 65 3e <typename Value>
04c0: 0a 09 76 6f 69 64 20 53 65 74 28 69 6e 74 20 73 ..void Set(int s
04d0: 2c 20 69 6e 74 20 65 2c 20 56 61 6c 75 65 20 76 , int e, Value v
04e0: 29 20 7b 20 2f 2f 20 73 65 71 5b 73 2c 65 29 3a ) { // seq[s,e):
04f0: 3d 76 20 3a 20 4f 28 6c 6f 67 20 6e 29 0a 09 09 =v : O(log n)...
0500: 53 65 74 52 65 63 28 73 2c 20 65 2c 20 4e 6f 64 SetRec(s, e, Nod
0510: 65 3a 3a 4f 6e 65 28 76 29 2c 20 74 72 65 65 2e e::One(v), tree.
0520: 73 69 7a 65 28 29 2d 31 2c 20 30 2c 20 74 72 65 size()-1, 0, tre
0530: 65 5b 30 5d 2e 73 69 7a 65 28 29 29 3b 0a 09 7d e[0].size());..}
0540: 0a 0a 70 72 69 76 61 74 65 3a 0a 09 4e 6f 64 65 ..private:..Node
0550: 20 51 75 65 72 79 52 65 63 28 69 6e 74 20 73 2c QueryRec(int s,
0560: 20 69 6e 74 20 65 2c 20 69 6e 74 20 6c 76 2c 20 int e, int lv,
0570: 69 6e 74 20 69 64 78 2c 20 69 6e 74 20 73 74 72 int idx, int str
0580: 69 64 65 29 0a 09 7b 0a 09 09 63 6f 6e 73 74 20 ide)..{...const
0590: 69 6e 74 20 6d 79 4c 20 3d 20 73 74 72 69 64 65 int myL = stride
05a0: 2a 69 64 78 3b 0a 09 09 63 6f 6e 73 74 20 69 6e *idx;...const in
05b0: 74 20 6d 79 52 20 3d 20 73 74 72 69 64 65 2a 28 t myR = stride*(
05c0: 69 64 78 2b 31 29 3b 0a 09 09 69 66 28 20 65 3c idx+1);...if( e<
05d0: 3d 6d 79 4c 20 7c 7c 20 6d 79 52 3c 3d 73 20 29 =myL || myR<=s )
05e0: 0a 09 09 09 72 65 74 75 72 6e 20 4e 6f 64 65 3a ....return Node:
05f0: 3a 5a 65 72 6f 28 29 3b 0a 09 09 52 65 73 6f 6c :Zero();...Resol
0600: 76 65 4c 61 7a 79 28 6c 76 2c 20 69 64 78 29 3b veLazy(lv, idx);
0610: 0a 0a 09 09 69 66 28 20 73 3c 3d 6d 79 4c 20 26 ....if( s<=myL &
0620: 26 20 6d 79 52 3c 3d 65 20 29 0a 09 09 09 72 65 & myR<=e )....re
0630: 74 75 72 6e 20 74 72 65 65 5b 6c 76 5d 5b 69 64 turn tree[lv][id
0640: 78 5d 3b 0a 09 09 72 65 74 75 72 6e 20 4e 6f 64 x];...return Nod
0650: 65 3a 3a 43 6f 6e 63 61 74 28 51 75 65 72 79 52 e::Concat(QueryR
0660: 65 63 28 73 2c 65 2c 6c 76 2d 31 2c 69 64 78 2a ec(s,e,lv-1,idx*
0670: 32 2c 73 74 72 69 64 65 2f 32 29 2c 0a 09 09 20 2,stride/2),...
0680: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0690: 20 20 20 51 75 65 72 79 52 65 63 28 73 2c 65 2c QueryRec(s,e,
06a0: 6c 76 2d 31 2c 69 64 78 2a 32 2b 31 2c 73 74 72 lv-1,idx*2+1,str
06b0: 69 64 65 2f 32 29 29 3b 0a 09 7d 0a 0a 09 76 6f ide/2));..}...vo
06c0: 69 64 20 53 65 74 52 65 63 28 69 6e 74 20 73 2c id SetRec(int s,
06d0: 20 69 6e 74 20 65 2c 20 63 6f 6e 73 74 20 4e 6f int e, const No
06e0: 64 65 26 20 6e 2c 20 69 6e 74 20 6c 76 2c 20 69 de& n, int lv, i
06f0: 6e 74 20 69 64 78 2c 20 69 6e 74 20 73 74 72 69 nt idx, int stri
0700: 64 65 29 0a 09 7b 0a 09 09 63 6f 6e 73 74 20 69 de)..{...const i
0710: 6e 74 20 6d 79 4c 20 3d 20 73 74 72 69 64 65 2a nt myL = stride*
0720: 69 64 78 3b 0a 09 09 63 6f 6e 73 74 20 69 6e 74 idx;...const int
0730: 20 6d 79 52 20 3d 20 73 74 72 69 64 65 2a 28 69 myR = stride*(i
0740: 64 78 2b 31 29 3b 0a 09 09 69 66 28 20 65 3c 3d dx+1);...if( e<=
0750: 6d 79 4c 20 7c 7c 20 6d 79 52 3c 3d 73 20 29 0a myL || myR<=s ).
0760: 09 09 09 72 65 74 75 72 6e 3b 0a 09 09 52 65 73 ...return;...Res
0770: 6f 6c 76 65 4c 61 7a 79 28 6c 76 2c 20 69 64 78 olveLazy(lv, idx
0780: 29 3b 0a 0a 09 09 69 66 28 20 73 74 72 69 64 65 );....if( stride
0790: 20 3d 3d 20 31 20 29 20 7b 0a 09 09 09 74 72 65 == 1 ) {....tre
07a0: 65 5b 6c 76 5d 5b 69 64 78 5d 20 3d 20 6e 3b 0a e[lv][idx] = n;.
07b0: 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 09 69 66 ..} else {....if
07c0: 28 20 73 3c 3d 6d 79 4c 20 26 26 20 6d 79 52 3c ( s<=myL && myR<
07d0: 3d 65 20 29 20 7b 0a 09 09 09 09 74 72 65 65 5b =e ) {.....tree[
07e0: 6c 76 5d 5b 69 64 78 5d 20 3d 20 6e 3b 0a 09 09 lv][idx] = n;...
07f0: 09 09 74 72 65 65 5b 6c 76 5d 5b 69 64 78 5d 2e ..tree[lv][idx].
0800: 6c 61 7a 79 20 3d 20 74 72 75 65 3b 0a 09 09 09 lazy = true;....
0810: 09 52 65 73 6f 6c 76 65 4c 61 7a 79 28 6c 76 2c .ResolveLazy(lv,
0820: 20 69 64 78 29 3b 0a 09 09 09 09 72 65 74 75 72 idx);.....retur
0830: 6e 3b 0a 09 09 09 7d 0a 09 09 09 53 65 74 52 65 n;....}....SetRe
0840: 63 28 73 2c 65 2c 6e 2c 6c 76 2d 31 2c 69 64 78 c(s,e,n,lv-1,idx
0850: 2a 32 2c 73 74 72 69 64 65 2f 32 29 3b 0a 09 09 *2,stride/2);...
0860: 09 53 65 74 52 65 63 28 73 2c 65 2c 6e 2c 6c 76 .SetRec(s,e,n,lv
0870: 2d 31 2c 69 64 78 2a 32 2b 31 2c 73 74 72 69 64 -1,idx*2+1,strid
0880: 65 2f 32 29 3b 0a 09 09 09 43 61 6c 63 4d 69 64 e/2);....CalcMid
0890: 4e 6f 64 65 28 6c 76 2c 20 69 64 78 29 3b 0a 09 Node(lv, idx);..
08a0: 09 7d 0a 09 7d 0a 0a 09 76 6f 69 64 20 43 61 6c .}..}...void Cal
08b0: 63 4d 69 64 4e 6f 64 65 28 69 6e 74 20 6c 76 2c cMidNode(int lv,
08c0: 20 69 6e 74 20 69 64 78 29 0a 09 7b 0a 09 09 74 int idx)..{...t
08d0: 72 65 65 5b 6c 76 5d 5b 69 64 78 5d 20 3d 20 4e ree[lv][idx] = N
08e0: 6f 64 65 3a 3a 43 6f 6e 63 61 74 28 74 72 65 65 ode::Concat(tree
08f0: 5b 6c 76 2d 31 5d 5b 69 64 78 2a 32 5d 2c 20 74 [lv-1][idx*2], t
0900: 72 65 65 5b 6c 76 2d 31 5d 5b 69 64 78 2a 32 2b ree[lv-1][idx*2+
0910: 31 5d 29 3b 0a 09 7d 0a 0a 09 76 6f 69 64 20 52 1]);..}...void R
0920: 65 73 6f 6c 76 65 4c 61 7a 79 28 69 6e 74 20 6c esolveLazy(int l
0930: 76 2c 20 69 6e 74 20 69 64 78 29 0a 09 7b 0a 09 v, int idx)..{..
0940: 09 69 66 28 74 72 65 65 5b 6c 76 5d 5b 69 64 78 .if(tree[lv][idx
0950: 5d 2e 6c 61 7a 79 29 20 7b 0a 09 09 09 69 66 28 ].lazy) {....if(
0960: 6c 76 20 3e 20 30 29 20 7b 0a 09 09 09 09 74 72 lv > 0) {.....tr
0970: 65 65 5b 6c 76 2d 31 5d 5b 69 64 78 2a 32 5d 20 ee[lv-1][idx*2]
0980: 20 20 3d 20 74 72 65 65 5b 6c 76 5d 5b 69 64 78 = tree[lv][idx
0990: 5d 3b 0a 09 09 09 09 74 72 65 65 5b 6c 76 2d 31 ];.....tree[lv-1
09a0: 5d 5b 69 64 78 2a 32 2b 31 5d 20 3d 20 74 72 65 ][idx*2+1] = tre
09b0: 65 5b 6c 76 5d 5b 69 64 78 5d 3b 0a 09 09 09 7d e[lv][idx];....}
09c0: 0a 09 09 09 74 72 65 65 5b 6c 76 5d 5b 69 64 78 ....tree[lv][idx
09d0: 5d 20 3d 20 4e 6f 64 65 3a 3a 52 65 70 65 61 74 ] = Node::Repeat
09e0: 28 74 72 65 65 5b 6c 76 5d 5b 69 64 78 5d 2c 20 (tree[lv][idx],
09f0: 31 3c 3c 6c 76 29 3b 0a 09 09 7d 0a 09 7d 0a 0a 1<<lv);...}..}..
0a00: 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c .vector< vector<
0a10: 4e 6f 64 65 3e 20 3e 20 74 72 65 65 3b 0a 7d 3b Node> > tree;.};
0a20: 0a .