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 36 39 - Codeforces 69
0090: 38 20 42 20 28 62 75 67 20 66 69 78 65 64 29 0a 8 B (bug fixed).
00a0: 2f 2f 20 20 20 2d 20 43 6f 64 65 66 6f 72 63 65 // - Codeforce
00b0: 73 20 32 30 30 20 44 0a 2f 2f 20 20 20 2d 20 43 s 200 D.// - C
00c0: 6f 64 65 66 6f 72 63 65 73 20 31 30 37 20 43 20 odeforces 107 C
00d0: 28 6f 6c 64 20 76 65 72 73 69 6f 6e 29 0a 2f 2f (old version).//
00e0: 20 20 20 2d 20 43 6f 64 65 66 6f 72 63 65 73 20 - Codeforces
00f0: 31 30 34 20 45 20 28 6f 6c 64 20 76 65 72 73 69 104 E (old versi
0100: 6f 6e 29 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d on).//----------
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 2d 2d 0a 0a 63 6c 61 73 73 20 53 65 67 6d 65 ---..class Segme
0150: 6e 74 54 72 65 65 0a 7b 0a 09 73 74 72 75 63 74 ntTree.{..struct
0160: 20 4e 6f 64 65 0a 09 7b 0a 09 09 69 6e 74 20 73 Node..{...int s
0170: 75 6d 3b 0a 0a 09 09 73 74 61 74 69 63 20 4e 6f um;....static No
0180: 64 65 20 5a 65 72 6f 28 29 0a 09 09 7b 0a 09 09 de Zero()...{...
0190: 09 4e 6f 64 65 20 63 20 3d 20 7b 30 7d 3b 0a 09 .Node c = {0};..
01a0: 09 09 72 65 74 75 72 6e 20 63 3b 0a 09 09 7d 0a ..return c;...}.
01b0: 09 09 73 74 61 74 69 63 20 4e 6f 64 65 20 4f 6e ..static Node On
01c0: 65 28 69 6e 74 20 76 29 0a 09 09 7b 0a 09 09 09 e(int v)...{....
01d0: 4e 6f 64 65 20 63 20 3d 20 7b 76 7d 3b 0a 09 09 Node c = {v};...
01e0: 09 72 65 74 75 72 6e 20 63 3b 0a 09 09 7d 0a 09 .return c;...}..
01f0: 09 73 74 61 74 69 63 20 4e 6f 64 65 20 43 6f 6e .static Node Con
0200: 63 61 74 28 63 6f 6e 73 74 20 4e 6f 64 65 26 20 cat(const Node&
0210: 6c 2c 20 63 6f 6e 73 74 20 4e 6f 64 65 26 20 72 l, const Node& r
0220: 29 0a 09 09 7b 0a 09 09 09 4e 6f 64 65 20 63 20 )...{....Node c
0230: 3d 20 7b 6c 2e 73 75 6d 20 2b 20 72 2e 73 75 6d = {l.sum + r.sum
0240: 7d 3b 0a 09 09 09 72 65 74 75 72 6e 20 63 3b 0a };....return c;.
0250: 09 09 7d 0a 09 09 73 74 61 74 69 63 20 4e 6f 64 ..}...static Nod
0260: 65 20 52 65 70 65 61 74 28 63 6f 6e 73 74 20 4e e Repeat(const N
0270: 6f 64 65 26 20 6e 2c 20 69 6e 74 20 6b 29 0a 09 ode& n, int k)..
0280: 09 7b 0a 09 09 09 4e 6f 64 65 20 63 20 3d 20 7b .{....Node c = {
0290: 6e 2e 73 75 6d 20 2a 20 6b 7d 3b 0a 09 09 09 72 n.sum * k};....r
02a0: 65 74 75 72 6e 20 63 3b 0a 09 09 7d 0a 0a 09 09 eturn c;...}....
02b0: 62 6f 6f 6c 20 6c 61 7a 79 3b 0a 09 7d 3b 0a 0a bool lazy;..};..
02c0: 70 75 62 6c 69 63 3a 0a 09 74 65 6d 70 6c 61 74 public:..templat
02d0: 65 3c 74 79 70 65 6e 61 6d 65 20 53 65 71 3e 0a e<typename Seq>.
02e0: 09 53 65 67 6d 65 6e 74 54 72 65 65 28 63 6f 6e .SegmentTree(con
02f0: 73 74 20 53 65 71 26 20 73 29 20 7b 0a 09 09 69 st Seq& s) {...i
0300: 6e 74 20 4e 20 3d 20 31 3b 0a 09 09 77 68 69 6c nt N = 1;...whil
0310: 65 28 20 4e 20 3c 20 73 2e 73 69 7a 65 28 29 20 e( N < s.size()
0320: 29 0a 09 09 09 4e 20 3c 3c 3d 20 31 3b 0a 0a 09 )....N <<= 1;...
0330: 09 74 72 65 65 2e 72 65 73 69 7a 65 28 74 72 65 .tree.resize(tre
0340: 65 2e 73 69 7a 65 28 29 2b 31 29 3b 20 74 72 65 e.size()+1); tre
0350: 65 2e 62 61 63 6b 28 29 2e 72 65 73 69 7a 65 28 e.back().resize(
0360: 4e 29 3b 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d N);...for(int i=
0370: 30 3b 20 69 3c 4e 3b 20 2b 2b 69 29 0a 09 09 09 0; i<N; ++i)....
0380: 74 72 65 65 2e 62 61 63 6b 28 29 5b 69 5d 20 3d tree.back()[i] =
0390: 20 69 3c 73 2e 73 69 7a 65 28 29 20 3f 20 4e 6f i<s.size() ? No
03a0: 64 65 3a 3a 4f 6e 65 28 73 5b 69 5d 29 20 3a 20 de::One(s[i]) :
03b0: 4e 6f 64 65 3a 3a 5a 65 72 6f 28 29 3b 0a 0a 09 Node::Zero();...
03c0: 09 77 68 69 6c 65 28 4e 3e 3e 3d 31 29 20 7b 0a .while(N>>=1) {.
03d0: 09 09 09 74 72 65 65 2e 72 65 73 69 7a 65 28 74 ...tree.resize(t
03e0: 72 65 65 2e 73 69 7a 65 28 29 2b 31 29 3b 20 74 ree.size()+1); t
03f0: 72 65 65 2e 62 61 63 6b 28 29 2e 72 65 73 69 7a ree.back().resiz
0400: 65 28 4e 29 3b 0a 09 09 09 66 6f 72 28 69 6e 74 e(N);....for(int
0410: 20 69 3d 30 3b 20 69 3c 4e 3b 20 2b 2b 69 29 0a i=0; i<N; ++i).
0420: 09 09 09 09 43 61 6c 63 4d 69 64 4e 6f 64 65 28 ....CalcMidNode(
0430: 74 72 65 65 2e 73 69 7a 65 28 29 2d 31 2c 20 69 tree.size()-1, i
0440: 29 3b 0a 09 09 7d 0a 09 7d 0a 0a 09 4e 6f 64 65 );...}..}...Node
0450: 20 51 75 65 72 79 28 69 6e 74 20 73 2c 20 69 6e Query(int s, in
0460: 74 20 65 29 20 7b 20 2f 2f 20 63 6f 6d 70 75 74 t e) { // comput
0470: 65 20 68 28 20 73 65 71 5b 73 2c 65 29 20 29 20 e h( seq[s,e) )
0480: 3a 20 20 4f 28 6c 6f 67 20 6e 29 0a 09 09 72 65 : O(log n)...re
0490: 74 75 72 6e 20 51 75 65 72 79 52 65 63 28 73 2c turn QueryRec(s,
04a0: 20 65 2c 20 74 72 65 65 2e 73 69 7a 65 28 29 2d e, tree.size()-
04b0: 31 2c 20 30 2c 20 74 72 65 65 5b 30 5d 2e 73 69 1, 0, tree[0].si
04c0: 7a 65 28 29 29 3b 0a 09 7d 0a 0a 09 74 65 6d 70 ze());..}...temp
04d0: 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 56 61 late<typename Va
04e0: 6c 75 65 3e 0a 09 76 6f 69 64 20 53 65 74 28 69 lue>..void Set(i
04f0: 6e 74 20 73 2c 20 69 6e 74 20 65 2c 20 56 61 6c nt s, int e, Val
0500: 75 65 20 76 29 20 7b 20 2f 2f 20 73 65 71 5b 73 ue v) { // seq[s
0510: 2c 65 29 3a 3d 76 20 3a 20 4f 28 6c 6f 67 20 6e ,e):=v : O(log n
0520: 29 0a 09 09 53 65 74 52 65 63 28 73 2c 20 65 2c )...SetRec(s, e,
0530: 20 4e 6f 64 65 3a 3a 4f 6e 65 28 76 29 2c 20 74 Node::One(v), t
0540: 72 65 65 2e 73 69 7a 65 28 29 2d 31 2c 20 30 2c ree.size()-1, 0,
0550: 20 74 72 65 65 5b 30 5d 2e 73 69 7a 65 28 29 29 tree[0].size())
0560: 3b 0a 09 7d 0a 0a 70 72 69 76 61 74 65 3a 0a 09 ;..}..private:..
0570: 4e 6f 64 65 20 51 75 65 72 79 52 65 63 28 69 6e Node QueryRec(in
0580: 74 20 73 2c 20 69 6e 74 20 65 2c 20 69 6e 74 20 t s, int e, int
0590: 6c 76 2c 20 69 6e 74 20 69 64 78 2c 20 69 6e 74 lv, int idx, int
05a0: 20 73 74 72 69 64 65 29 0a 09 7b 0a 09 09 63 6f stride)..{...co
05b0: 6e 73 74 20 69 6e 74 20 6d 79 4c 20 3d 20 73 74 nst int myL = st
05c0: 72 69 64 65 2a 69 64 78 3b 0a 09 09 63 6f 6e 73 ride*idx;...cons
05d0: 74 20 69 6e 74 20 6d 79 52 20 3d 20 73 74 72 69 t int myR = stri
05e0: 64 65 2a 28 69 64 78 2b 31 29 3b 0a 09 09 69 66 de*(idx+1);...if
05f0: 28 20 65 3c 3d 6d 79 4c 20 7c 7c 20 6d 79 52 3c ( e<=myL || myR<
0600: 3d 73 20 29 0a 09 09 09 72 65 74 75 72 6e 20 4e =s )....return N
0610: 6f 64 65 3a 3a 5a 65 72 6f 28 29 3b 0a 09 09 52 ode::Zero();...R
0620: 65 73 6f 6c 76 65 4c 61 7a 79 28 6c 76 2c 20 69 esolveLazy(lv, i
0630: 64 78 29 3b 0a 0a 09 09 69 66 28 20 73 3c 3d 6d dx);....if( s<=m
0640: 79 4c 20 26 26 20 6d 79 52 3c 3d 65 20 29 0a 09 yL && myR<=e )..
0650: 09 09 72 65 74 75 72 6e 20 74 72 65 65 5b 6c 76 ..return tree[lv
0660: 5d 5b 69 64 78 5d 3b 0a 09 09 72 65 74 75 72 6e ][idx];...return
0670: 20 4e 6f 64 65 3a 3a 43 6f 6e 63 61 74 28 51 75 Node::Concat(Qu
0680: 65 72 79 52 65 63 28 73 2c 65 2c 6c 76 2d 31 2c eryRec(s,e,lv-1,
0690: 69 64 78 2a 32 2c 73 74 72 69 64 65 2f 32 29 2c idx*2,stride/2),
06a0: 0a 09 09 20 20 20 20 20 20 20 20 20 20 20 20 20 ...
06b0: 20 20 20 20 20 20 20 51 75 65 72 79 52 65 63 28 QueryRec(
06c0: 73 2c 65 2c 6c 76 2d 31 2c 69 64 78 2a 32 2b 31 s,e,lv-1,idx*2+1
06d0: 2c 73 74 72 69 64 65 2f 32 29 29 3b 0a 09 7d 0a ,stride/2));..}.
06e0: 0a 09 76 6f 69 64 20 53 65 74 52 65 63 28 69 6e ..void SetRec(in
06f0: 74 20 73 2c 20 69 6e 74 20 65 2c 20 63 6f 6e 73 t s, int e, cons
0700: 74 20 4e 6f 64 65 26 20 6e 2c 20 69 6e 74 20 6c t Node& n, int l
0710: 76 2c 20 69 6e 74 20 69 64 78 2c 20 69 6e 74 20 v, int idx, int
0720: 73 74 72 69 64 65 29 0a 09 7b 0a 09 09 63 6f 6e stride)..{...con
0730: 73 74 20 69 6e 74 20 6d 79 4c 20 3d 20 73 74 72 st int myL = str
0740: 69 64 65 2a 69 64 78 3b 0a 09 09 63 6f 6e 73 74 ide*idx;...const
0750: 20 69 6e 74 20 6d 79 52 20 3d 20 73 74 72 69 64 int myR = strid
0760: 65 2a 28 69 64 78 2b 31 29 3b 0a 09 09 69 66 28 e*(idx+1);...if(
0770: 20 65 3c 3d 6d 79 4c 20 7c 7c 20 6d 79 52 3c 3d e<=myL || myR<=
0780: 73 20 29 0a 09 09 09 72 65 74 75 72 6e 3b 0a 09 s )....return;..
0790: 09 52 65 73 6f 6c 76 65 4c 61 7a 79 28 6c 76 2c .ResolveLazy(lv,
07a0: 20 69 64 78 29 3b 0a 0a 09 09 69 66 28 20 73 74 idx);....if( st
07b0: 72 69 64 65 20 3d 3d 20 31 20 29 20 7b 0a 09 09 ride == 1 ) {...
07c0: 09 74 72 65 65 5b 6c 76 5d 5b 69 64 78 5d 20 3d .tree[lv][idx] =
07d0: 20 6e 3b 0a 09 09 7d 20 65 6c 73 65 20 7b 0a 09 n;...} else {..
07e0: 09 09 69 66 28 20 73 3c 3d 6d 79 4c 20 26 26 20 ..if( s<=myL &&
07f0: 6d 79 52 3c 3d 65 20 29 20 7b 0a 09 09 09 09 74 myR<=e ) {.....t
0800: 72 65 65 5b 6c 76 5d 5b 69 64 78 5d 20 3d 20 6e ree[lv][idx] = n
0810: 3b 0a 09 09 09 09 74 72 65 65 5b 6c 76 5d 5b 69 ;.....tree[lv][i
0820: 64 78 5d 2e 6c 61 7a 79 20 3d 20 74 72 75 65 3b dx].lazy = true;
0830: 0a 09 09 09 09 52 65 73 6f 6c 76 65 4c 61 7a 79 .....ResolveLazy
0840: 28 6c 76 2c 20 69 64 78 29 3b 0a 09 09 09 09 72 (lv, idx);.....r
0850: 65 74 75 72 6e 3b 0a 09 09 09 7d 0a 09 09 09 53 eturn;....}....S
0860: 65 74 52 65 63 28 73 2c 65 2c 6e 2c 6c 76 2d 31 etRec(s,e,n,lv-1
0870: 2c 69 64 78 2a 32 2c 73 74 72 69 64 65 2f 32 29 ,idx*2,stride/2)
0880: 3b 0a 09 09 09 53 65 74 52 65 63 28 73 2c 65 2c ;....SetRec(s,e,
0890: 6e 2c 6c 76 2d 31 2c 69 64 78 2a 32 2b 31 2c 73 n,lv-1,idx*2+1,s
08a0: 74 72 69 64 65 2f 32 29 3b 0a 09 09 09 43 61 6c tride/2);....Cal
08b0: 63 4d 69 64 4e 6f 64 65 28 6c 76 2c 20 69 64 78 cMidNode(lv, idx
08c0: 29 3b 0a 09 09 7d 0a 09 7d 0a 0a 09 76 6f 69 64 );...}..}...void
08d0: 20 43 61 6c 63 4d 69 64 4e 6f 64 65 28 69 6e 74 CalcMidNode(int
08e0: 20 6c 76 2c 20 69 6e 74 20 69 64 78 29 0a 09 7b lv, int idx)..{
08f0: 0a 09 09 52 65 73 6f 6c 76 65 4c 61 7a 79 28 6c ...ResolveLazy(l
0900: 76 2d 31 2c 20 69 64 78 2a 32 29 3b 0a 09 09 52 v-1, idx*2);...R
0910: 65 73 6f 6c 76 65 4c 61 7a 79 28 6c 76 2d 31 2c esolveLazy(lv-1,
0920: 20 69 64 78 2a 32 2b 31 29 3b 0a 09 09 74 72 65 idx*2+1);...tre
0930: 65 5b 6c 76 5d 5b 69 64 78 5d 20 3d 20 4e 6f 64 e[lv][idx] = Nod
0940: 65 3a 3a 43 6f 6e 63 61 74 28 74 72 65 65 5b 6c e::Concat(tree[l
0950: 76 2d 31 5d 5b 69 64 78 2a 32 5d 2c 20 74 72 65 v-1][idx*2], tre
0960: 65 5b 6c 76 2d 31 5d 5b 69 64 78 2a 32 2b 31 5d e[lv-1][idx*2+1]
0970: 29 3b 0a 09 7d 0a 0a 09 76 6f 69 64 20 52 65 73 );..}...void Res
0980: 6f 6c 76 65 4c 61 7a 79 28 69 6e 74 20 6c 76 2c olveLazy(int lv,
0990: 20 69 6e 74 20 69 64 78 29 0a 09 7b 0a 09 09 69 int idx)..{...i
09a0: 66 28 74 72 65 65 5b 6c 76 5d 5b 69 64 78 5d 2e f(tree[lv][idx].
09b0: 6c 61 7a 79 29 20 7b 0a 09 09 09 69 66 28 6c 76 lazy) {....if(lv
09c0: 20 3e 20 30 29 20 7b 0a 09 09 09 09 74 72 65 65 > 0) {.....tree
09d0: 5b 6c 76 2d 31 5d 5b 69 64 78 2a 32 5d 20 20 20 [lv-1][idx*2]
09e0: 3d 20 74 72 65 65 5b 6c 76 5d 5b 69 64 78 5d 3b = tree[lv][idx];
09f0: 0a 09 09 09 09 74 72 65 65 5b 6c 76 2d 31 5d 5b .....tree[lv-1][
0a00: 69 64 78 2a 32 2b 31 5d 20 3d 20 74 72 65 65 5b idx*2+1] = tree[
0a10: 6c 76 5d 5b 69 64 78 5d 3b 0a 09 09 09 7d 0a 09 lv][idx];....}..
0a20: 09 09 74 72 65 65 5b 6c 76 5d 5b 69 64 78 5d 20 ..tree[lv][idx]
0a30: 3d 20 4e 6f 64 65 3a 3a 52 65 70 65 61 74 28 74 = Node::Repeat(t
0a40: 72 65 65 5b 6c 76 5d 5b 69 64 78 5d 2c 20 31 3c ree[lv][idx], 1<
0a50: 3c 6c 76 29 3b 0a 09 09 7d 0a 09 7d 0a 0a 09 76 <lv);...}..}...v
0a60: 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 4e 6f ector< vector<No
0a70: 64 65 3e 20 3e 20 74 72 65 65 3b 0a 7d 3b 0a de> > tree;.};.