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 31 30 - Codeforces 10
0090: 37 20 43 0a 2f 2f 20 20 20 2d 20 43 6f 64 65 66 7 C.// - Codef
00a0: 6f 72 63 65 73 20 31 30 34 20 45 0a 2f 2f 2d 2d orces 104 E.//--
00b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 74 65 6d -----------..tem
00f0: 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 4e plate<typename N
0100: 6f 64 65 3e 0a 63 6c 61 73 73 20 53 65 67 6d 65 ode>.class Segme
0110: 6e 74 54 72 65 65 0a 7b 0a 70 75 62 6c 69 63 3a ntTree.{.public:
0120: 0a 09 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e ..template<typen
0130: 61 6d 65 20 53 65 71 3e 0a 09 53 65 67 6d 65 6e ame Seq>..Segmen
0140: 74 54 72 65 65 28 63 6f 6e 73 74 20 53 65 71 26 tTree(const Seq&
0150: 20 73 29 20 7b 0a 09 09 69 6e 74 20 4e 20 3d 20 s) {...int N =
0160: 31 3b 0a 09 09 77 68 69 6c 65 28 20 4e 20 3c 20 1;...while( N <
0170: 73 2e 73 69 7a 65 28 29 20 29 0a 09 09 09 4e 20 s.size() )....N
0180: 3c 3c 3d 20 31 3b 0a 0a 09 09 74 72 65 65 2e 72 <<= 1;....tree.r
0190: 65 73 69 7a 65 28 74 72 65 65 2e 73 69 7a 65 28 esize(tree.size(
01a0: 29 2b 31 29 3b 20 74 72 65 65 2e 62 61 63 6b 28 )+1); tree.back(
01b0: 29 2e 72 65 73 69 7a 65 28 4e 29 3b 0a 09 09 66 ).resize(N);...f
01c0: 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 4e 3b or(int i=0; i<N;
01d0: 20 2b 2b 69 29 0a 09 09 09 74 72 65 65 2e 62 61 ++i)....tree.ba
01e0: 63 6b 28 29 5b 69 5d 20 3d 20 69 3c 73 2e 73 69 ck()[i] = i<s.si
01f0: 7a 65 28 29 20 3f 20 4e 6f 64 65 3a 3a 4f 6e 65 ze() ? Node::One
0200: 28 73 5b 69 5d 29 20 3a 20 4e 6f 64 65 3a 3a 5a (s[i]) : Node::Z
0210: 65 72 6f 28 29 3b 0a 0a 09 09 77 68 69 6c 65 28 ero();....while(
0220: 4e 3e 3e 3d 31 29 20 7b 0a 09 09 09 74 72 65 65 N>>=1) {....tree
0230: 2e 72 65 73 69 7a 65 28 74 72 65 65 2e 73 69 7a .resize(tree.siz
0240: 65 28 29 2b 31 29 3b 20 74 72 65 65 2e 62 61 63 e()+1); tree.bac
0250: 6b 28 29 2e 72 65 73 69 7a 65 28 4e 29 3b 0a 09 k().resize(N);..
0260: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
0270: 3c 4e 3b 20 2b 2b 69 29 0a 09 09 09 09 43 61 6c <N; ++i).....Cal
0280: 63 4d 69 64 4e 6f 64 65 28 74 72 65 65 2e 73 69 cMidNode(tree.si
0290: 7a 65 28 29 2d 31 2c 20 69 29 3b 0a 09 09 7d 0a ze()-1, i);...}.
02a0: 09 7d 0a 0a 09 4e 6f 64 65 20 51 75 65 72 79 28 .}...Node Query(
02b0: 69 6e 74 20 73 2c 20 69 6e 74 20 65 29 20 7b 20 int s, int e) {
02c0: 2f 2f 20 63 6f 6d 70 75 74 65 20 68 28 20 73 65 // compute h( se
02d0: 71 5b 73 2c 65 29 20 29 20 3a 20 20 4f 28 6c 6f q[s,e) ) : O(lo
02e0: 67 20 6e 29 0a 09 09 72 65 74 75 72 6e 20 51 75 g n)...return Qu
02f0: 65 72 79 52 65 63 28 73 2c 20 65 2c 20 74 72 65 eryRec(s, e, tre
0300: 65 2e 73 69 7a 65 28 29 2d 31 2c 20 30 2c 20 74 e.size()-1, 0, t
0310: 72 65 65 5b 30 5d 2e 73 69 7a 65 28 29 29 3b 0a ree[0].size());.
0320: 09 7d 0a 0a 09 74 65 6d 70 6c 61 74 65 3c 74 79 .}...template<ty
0330: 70 65 6e 61 6d 65 20 56 61 6c 75 65 3e 0a 09 76 pename Value>..v
0340: 6f 69 64 20 53 65 74 28 69 6e 74 20 73 2c 20 69 oid Set(int s, i
0350: 6e 74 20 65 2c 20 56 61 6c 75 65 20 76 29 20 7b nt e, Value v) {
0360: 20 2f 2f 20 73 65 71 5b 73 2c 65 29 3a 3d 76 20 // seq[s,e):=v
0370: 3a 20 4f 28 6c 6f 67 20 6e 20 7c 65 2d 73 7c 29 : O(log n |e-s|)
0380: 0a 09 09 53 65 74 52 65 63 28 73 2c 20 65 2c 20 ...SetRec(s, e,
0390: 4e 6f 64 65 3a 3a 4f 6e 65 28 76 29 2c 20 74 72 Node::One(v), tr
03a0: 65 65 2e 73 69 7a 65 28 29 2d 31 2c 20 30 2c 20 ee.size()-1, 0,
03b0: 74 72 65 65 5b 30 5d 2e 73 69 7a 65 28 29 29 3b tree[0].size());
03c0: 0a 09 7d 0a 0a 70 72 69 76 61 74 65 3a 0a 09 76 ..}..private:..v
03d0: 6f 69 64 20 43 61 6c 63 4d 69 64 4e 6f 64 65 28 oid CalcMidNode(
03e0: 69 6e 74 20 6c 76 2c 20 69 6e 74 20 69 64 78 29 int lv, int idx)
03f0: 0a 09 7b 0a 09 09 74 72 65 65 5b 6c 76 5d 5b 69 ..{...tree[lv][i
0400: 64 78 5d 20 3d 20 4e 6f 64 65 3a 3a 43 6f 6e 63 dx] = Node::Conc
0410: 61 74 28 74 72 65 65 5b 6c 76 2d 31 5d 5b 69 64 at(tree[lv-1][id
0420: 78 2a 32 5d 2c 20 74 72 65 65 5b 6c 76 2d 31 5d x*2], tree[lv-1]
0430: 5b 69 64 78 2a 32 2b 31 5d 29 3b 0a 09 7d 0a 0a [idx*2+1]);..}..
0440: 09 4e 6f 64 65 20 51 75 65 72 79 52 65 63 28 69 .Node QueryRec(i
0450: 6e 74 20 73 2c 20 69 6e 74 20 65 2c 20 69 6e 74 nt s, int e, int
0460: 20 6c 76 2c 20 69 6e 74 20 69 64 78 2c 20 69 6e lv, int idx, in
0470: 74 20 73 74 72 69 64 65 29 0a 09 7b 0a 09 09 63 t stride)..{...c
0480: 6f 6e 73 74 20 69 6e 74 20 6d 79 4c 20 3d 20 73 onst int myL = s
0490: 74 72 69 64 65 2a 69 64 78 3b 0a 09 09 63 6f 6e tride*idx;...con
04a0: 73 74 20 69 6e 74 20 6d 79 52 20 3d 20 73 74 72 st int myR = str
04b0: 69 64 65 2a 28 69 64 78 2b 31 29 3b 0a 09 09 69 ide*(idx+1);...i
04c0: 66 28 20 65 3c 3d 6d 79 4c 20 7c 7c 20 6d 79 52 f( e<=myL || myR
04d0: 3c 3d 73 20 29 0a 09 09 09 72 65 74 75 72 6e 20 <=s )....return
04e0: 4e 6f 64 65 3a 3a 5a 65 72 6f 28 29 3b 0a 09 09 Node::Zero();...
04f0: 69 66 28 20 73 3c 3d 6d 79 4c 20 26 26 20 6d 79 if( s<=myL && my
0500: 52 3c 3d 65 20 29 0a 09 09 09 72 65 74 75 72 6e R<=e )....return
0510: 20 74 72 65 65 5b 6c 76 5d 5b 69 64 78 5d 3b 0a tree[lv][idx];.
0520: 09 09 72 65 74 75 72 6e 20 4e 6f 64 65 3a 3a 43 ..return Node::C
0530: 6f 6e 63 61 74 28 51 75 65 72 79 52 65 63 28 73 oncat(QueryRec(s
0540: 2c 65 2c 6c 76 2d 31 2c 69 64 78 2a 32 2c 73 74 ,e,lv-1,idx*2,st
0550: 72 69 64 65 2f 32 29 2c 0a 09 09 20 20 20 20 20 ride/2),...
0560: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 51 Q
0570: 75 65 72 79 52 65 63 28 73 2c 65 2c 6c 76 2d 31 ueryRec(s,e,lv-1
0580: 2c 69 64 78 2a 32 2b 31 2c 73 74 72 69 64 65 2f ,idx*2+1,stride/
0590: 32 29 29 3b 0a 09 7d 0a 0a 09 76 6f 69 64 20 53 2));..}...void S
05a0: 65 74 52 65 63 28 69 6e 74 20 73 2c 20 69 6e 74 etRec(int s, int
05b0: 20 65 2c 20 63 6f 6e 73 74 20 4e 6f 64 65 26 20 e, const Node&
05c0: 6e 2c 20 69 6e 74 20 6c 76 2c 20 69 6e 74 20 69 n, int lv, int i
05d0: 64 78 2c 20 69 6e 74 20 73 74 72 69 64 65 29 0a dx, int stride).
05e0: 09 7b 0a 09 09 63 6f 6e 73 74 20 69 6e 74 20 6d .{...const int m
05f0: 79 4c 20 3d 20 73 74 72 69 64 65 2a 69 64 78 3b yL = stride*idx;
0600: 0a 09 09 63 6f 6e 73 74 20 69 6e 74 20 6d 79 52 ...const int myR
0610: 20 3d 20 73 74 72 69 64 65 2a 28 69 64 78 2b 31 = stride*(idx+1
0620: 29 3b 0a 09 09 69 66 28 20 65 3c 3d 6d 79 4c 20 );...if( e<=myL
0630: 7c 7c 20 6d 79 52 3c 3d 73 20 29 0a 09 09 09 72 || myR<=s )....r
0640: 65 74 75 72 6e 3b 0a 09 09 69 66 28 20 73 74 72 eturn;...if( str
0650: 69 64 65 20 3d 3d 20 31 20 29 20 7b 0a 09 09 09 ide == 1 ) {....
0660: 74 72 65 65 5b 6c 76 5d 5b 69 64 78 5d 20 3d 20 tree[lv][idx] =
0670: 6e 3b 0a 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 n;...} else {...
0680: 09 53 65 74 52 65 63 28 73 2c 65 2c 6e 2c 6c 76 .SetRec(s,e,n,lv
0690: 2d 31 2c 69 64 78 2a 32 2c 73 74 72 69 64 65 2f -1,idx*2,stride/
06a0: 32 29 3b 0a 09 09 09 53 65 74 52 65 63 28 73 2c 2);....SetRec(s,
06b0: 65 2c 6e 2c 6c 76 2d 31 2c 69 64 78 2a 32 2b 31 e,n,lv-1,idx*2+1
06c0: 2c 73 74 72 69 64 65 2f 32 29 3b 0a 09 09 09 43 ,stride/2);....C
06d0: 61 6c 63 4d 69 64 4e 6f 64 65 28 6c 76 2c 20 69 alcMidNode(lv, i
06e0: 64 78 29 3b 0a 09 09 7d 0a 09 7d 0a 0a 09 76 65 dx);...}..}...ve
06f0: 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 4e 6f 64 ctor< vector<Nod
0700: 65 3e 20 3e 20 74 72 65 65 3b 0a 7d 3b 0a 0a 73 e> > tree;.};..s
0710: 74 72 75 63 74 20 4e 6f 64 65 0a 7b 0a 09 64 6f truct Node.{..do
0720: 75 62 6c 65 20 73 75 6d 3b 0a 09 64 6f 75 62 6c uble sum;..doubl
0730: 65 20 6d 61 78 4c 65 66 74 3b 0a 09 64 6f 75 62 e maxLeft;..doub
0740: 6c 65 20 6d 61 78 52 69 67 68 74 3b 0a 09 64 6f le maxRight;..do
0750: 75 62 6c 65 20 6d 61 78 53 75 6d 3b 0a 09 73 74 uble maxSum;..st
0760: 61 74 69 63 20 4e 6f 64 65 20 5a 65 72 6f 28 29 atic Node Zero()
0770: 0a 09 7b 0a 09 09 4e 6f 64 65 20 63 20 3d 20 7b ..{...Node c = {
0780: 30 2c 20 30 2c 20 30 2c 20 30 7d 3b 0a 09 09 72 0, 0, 0, 0};...r
0790: 65 74 75 72 6e 20 63 3b 0a 09 7d 0a 09 73 74 61 eturn c;..}..sta
07a0: 74 69 63 20 4e 6f 64 65 20 4f 6e 65 28 64 6f 75 tic Node One(dou
07b0: 62 6c 65 20 76 29 0a 09 7b 0a 09 09 4e 6f 64 65 ble v)..{...Node
07c0: 20 63 20 3d 20 7b 76 2c 20 6d 61 78 28 30 2e 30 c = {v, max(0.0
07d0: 2c 76 29 2c 20 6d 61 78 28 30 2e 30 2c 76 29 2c ,v), max(0.0,v),
07e0: 20 6d 61 78 28 30 2e 30 2c 76 29 7d 3b 0a 09 09 max(0.0,v)};...
07f0: 72 65 74 75 72 6e 20 63 3b 0a 09 7d 0a 09 73 74 return c;..}..st
0800: 61 74 69 63 20 4e 6f 64 65 20 43 6f 6e 63 61 74 atic Node Concat
0810: 28 63 6f 6e 73 74 20 4e 6f 64 65 26 20 6c 2c 20 (const Node& l,
0820: 63 6f 6e 73 74 20 4e 6f 64 65 26 20 72 29 0a 09 const Node& r)..
0830: 7b 0a 09 09 4e 6f 64 65 20 63 20 3d 20 7b 0a 09 {...Node c = {..
0840: 09 09 6c 2e 73 75 6d 20 2b 20 72 2e 73 75 6d 2c ..l.sum + r.sum,
0850: 0a 09 09 09 6d 61 78 28 6c 2e 6d 61 78 4c 65 66 ....max(l.maxLef
0860: 74 2c 20 6c 2e 73 75 6d 2b 72 2e 6d 61 78 4c 65 t, l.sum+r.maxLe
0870: 66 74 29 2c 0a 09 09 09 6d 61 78 28 6c 2e 6d 61 ft),....max(l.ma
0880: 78 52 69 67 68 74 2b 72 2e 73 75 6d 2c 20 72 2e xRight+r.sum, r.
0890: 6d 61 78 52 69 67 68 74 29 2c 0a 09 09 09 6d 61 maxRight),....ma
08a0: 78 28 6d 61 78 28 6c 2e 6d 61 78 53 75 6d 2c 20 x(max(l.maxSum,
08b0: 72 2e 6d 61 78 53 75 6d 29 2c 20 6c 2e 6d 61 78 r.maxSum), l.max
08c0: 52 69 67 68 74 2b 72 2e 6d 61 78 4c 65 66 74 29 Right+r.maxLeft)
08d0: 2c 0a 09 09 7d 3b 0a 09 09 72 65 74 75 72 6e 20 ,...};...return
08e0: 63 3b 0a 09 7d 0a 7d 3b 0a 0a 2f 2a 0a 63 6c 61 c;..}.};../*.cla
08f0: 73 73 20 53 65 67 6d 65 6e 74 54 72 65 65 0a 7b ss SegmentTree.{
0900: 0a 09 2f 2f 20 2d 2d 2d 20 44 41 54 41 20 46 4f ..// --- DATA FO
0910: 52 20 45 41 43 48 20 4e 4f 44 45 20 2d 2d 2d 0a R EACH NODE ---.
0920: 09 73 74 72 75 63 74 20 4e 6f 64 65 0a 09 7b 0a .struct Node..{.
0930: 09 09 69 6e 74 20 73 75 6d 3b 0a 09 09 69 6e 74 ..int sum;...int
0940: 20 6d 61 78 4c 65 66 74 3b 0a 09 09 69 6e 74 20 maxLeft;...int
0950: 6d 69 6e 4c 65 66 74 3b 0a 09 09 69 6e 74 20 6e minLeft;...int n
0960: 34 3b 0a 09 09 69 6e 74 20 6e 37 3b 0a 09 09 62 4;...int n7;...b
0970: 6f 6f 6c 20 73 77 69 74 63 68 65 64 3b 0a 09 7d ool switched;..}
0980: 3b 0a 09 2f 2f 20 2d 2d 2d 20 44 41 54 41 20 46 ;..// --- DATA F
0990: 4f 52 20 45 41 43 48 20 4e 4f 44 45 20 2d 2d 2d OR EACH NODE ---
09a0: 0a 0a 09 4e 6f 64 65 20 43 61 6e 6f 6e 69 63 61 ...Node Canonica
09b0: 6c 28 69 6e 74 20 6c 76 2c 20 69 6e 74 20 69 64 l(int lv, int id
09c0: 78 29 0a 09 7b 0a 09 09 4e 6f 64 65 26 20 78 20 x)..{...Node& x
09d0: 3d 20 74 72 65 65 5b 6c 76 5d 5b 69 64 78 5d 3b = tree[lv][idx];
09e0: 0a 09 09 2f 2f 20 2d 2d 2d 20 44 4f 20 53 4f 4d ...// --- DO SOM
09f0: 45 54 48 49 4e 47 20 49 46 20 59 4f 55 20 4e 45 ETHING IF YOU NE
0a00: 45 44 20 43 41 4e 4f 4e 49 43 41 4c 49 5a 41 54 ED CANONICALIZAT
0a10: 49 4f 4e 20 2d 2d 2d 0a 09 09 69 66 28 20 21 78 ION ---...if( !x
0a20: 2e 73 77 69 74 63 68 65 64 20 29 0a 09 09 09 72 .switched )....r
0a30: 65 74 75 72 6e 20 78 3b 0a 09 09 4e 6f 64 65 20 eturn x;...Node
0a40: 6e 20 3d 20 7b 2d 78 2e 73 75 6d 2c 20 2d 78 2e n = {-x.sum, -x.
0a50: 6d 69 6e 4c 65 66 74 2c 20 2d 78 2e 6d 61 78 4c minLeft, -x.maxL
0a60: 65 66 74 2c 20 78 2e 6e 37 2c 20 78 2e 6e 34 2c eft, x.n7, x.n4,
0a70: 20 66 61 6c 73 65 7d 3b 0a 09 09 72 65 74 75 72 false};...retur
0a80: 6e 20 6e 3b 0a 09 09 2f 2f 20 2d 2d 2d 20 44 4f n n;...// --- DO
0a90: 20 53 4f 4d 45 54 48 49 4e 47 20 49 46 20 59 4f SOMETHING IF YO
0aa0: 55 20 4e 45 45 44 20 43 41 4e 4f 4e 49 43 41 4c U NEED CANONICAL
0ab0: 49 5a 41 54 49 4f 4e 20 2d 2d 2d 0a 09 7d 0a 0a IZATION ---..}..
0ac0: 09 76 6f 69 64 20 55 70 64 61 74 65 4d 69 64 4e .void UpdateMidN
0ad0: 6f 64 65 28 69 6e 74 20 6c 76 2c 20 69 6e 74 20 ode(int lv, int
0ae0: 69 64 78 29 0a 09 7b 0a 09 09 4e 6f 64 65 20 6c idx)..{...Node l
0af0: 20 3d 20 43 61 6e 6f 6e 69 63 61 6c 28 6c 76 2d = Canonical(lv-
0b00: 31 2c 20 69 64 78 2a 32 29 3b 0a 09 09 4e 6f 64 1, idx*2);...Nod
0b10: 65 20 72 20 3d 20 43 61 6e 6f 6e 69 63 61 6c 28 e r = Canonical(
0b20: 6c 76 2d 31 2c 20 69 64 78 2a 32 2b 31 29 3b 0a lv-1, idx*2+1);.
0b30: 09 09 2f 2f 20 2d 2d 2d 20 42 4f 54 54 4f 4d 20 ..// --- BOTTOM
0b40: 55 50 20 43 4f 4d 50 55 54 41 54 49 4f 4e 20 2d UP COMPUTATION -
0b50: 2d 2d 0a 09 09 4e 6f 64 65 20 6d 65 20 3d 20 7b --...Node me = {
0b60: 0a 09 09 09 6c 2e 73 75 6d 20 2b 20 72 2e 73 75 ....l.sum + r.su
0b70: 6d 2c 0a 09 09 09 6d 61 78 28 6c 2e 6d 61 78 4c m,....max(l.maxL
0b80: 65 66 74 2c 20 6c 2e 73 75 6d 2b 72 2e 6d 61 78 eft, l.sum+r.max
0b90: 4c 65 66 74 29 2c 0a 09 09 09 6d 69 6e 28 6c 2e Left),....min(l.
0ba0: 6d 69 6e 4c 65 66 74 2c 20 6c 2e 73 75 6d 2b 72 minLeft, l.sum+r
0bb0: 2e 6d 69 6e 4c 65 66 74 29 2c 0a 09 09 09 6c 2e .minLeft),....l.
0bc0: 6e 34 20 2b 20 72 2e 6e 34 2c 0a 09 09 09 6c 2e n4 + r.n4,....l.
0bd0: 6e 37 20 2b 20 72 2e 6e 37 2c 0a 09 09 09 66 61 n7 + r.n7,....fa
0be0: 6c 73 65 0a 09 09 7d 3b 0a 09 09 2f 2f 20 2d 2d lse...};...// --
0bf0: 2d 20 42 4f 54 54 4f 4d 20 55 50 20 43 4f 4d 50 - BOTTOM UP COMP
0c00: 55 54 41 54 49 4f 4e 20 2d 2d 2d 0a 09 09 74 72 UTATION ---...tr
0c10: 65 65 5b 6c 76 5d 5b 69 64 78 5d 20 3d 20 6d 65 ee[lv][idx] = me
0c20: 3b 0a 09 7d 0a 0a 09 76 65 63 74 6f 72 3c 20 76 ;..}...vector< v
0c30: 65 63 74 6f 72 3c 4e 6f 64 65 3e 20 3e 20 74 72 ector<Node> > tr
0c40: 65 65 3b 0a 0a 70 75 62 6c 69 63 3a 0a 09 53 65 ee;..public:..Se
0c50: 67 6d 65 6e 74 54 72 65 65 28 63 6f 6e 73 74 20 gmentTree(const
0c60: 73 74 72 69 6e 67 26 20 73 29 0a 09 7b 0a 09 09 string& s)..{...
0c70: 69 6e 74 20 4e 20 3d 20 31 3b 0a 09 09 77 68 69 int N = 1;...whi
0c80: 6c 65 28 20 4e 20 3c 20 73 2e 73 69 7a 65 28 29 le( N < s.size()
0c90: 20 29 0a 09 09 09 4e 20 3c 3c 3d 20 31 3b 0a 0a )....N <<= 1;..
0ca0: 09 09 74 72 65 65 2e 72 65 73 69 7a 65 28 74 72 ..tree.resize(tr
0cb0: 65 65 2e 73 69 7a 65 28 29 2b 31 29 3b 20 74 72 ee.size()+1); tr
0cc0: 65 65 2e 62 61 63 6b 28 29 2e 72 65 73 69 7a 65 ee.back().resize
0cd0: 28 4e 29 3b 0a 09 09 66 6f 72 28 69 6e 74 20 69 (N);...for(int i
0ce0: 3d 30 3b 20 69 3c 4e 3b 20 2b 2b 69 29 0a 09 09 =0; i<N; ++i)...
0cf0: 7b 0a 09 09 09 2f 2f 20 2d 2d 2d 20 49 4e 49 54 {....// --- INIT
0d00: 49 41 4c 49 5a 45 20 42 41 53 45 20 31 2d 45 4c IALIZE BASE 1-EL
0d10: 45 4d 45 4e 54 20 4e 4f 44 45 53 20 2d 2d 2d 0a EMENT NODES ---.
0d20: 09 09 09 69 6e 74 20 76 20 3d 20 69 3c 73 2e 73 ...int v = i<s.s
0d30: 69 7a 65 28 29 20 3f 20 28 73 5b 69 5d 3d 3d 27 ize() ? (s[i]=='
0d40: 34 27 20 3f 20 2b 31 20 3a 20 2d 31 29 20 3a 20 4' ? +1 : -1) :
0d50: 30 3b 0a 09 09 09 4e 6f 64 65 20 6d 65 20 3d 20 0;....Node me =
0d60: 7b 76 2c 20 6d 61 78 28 30 2c 76 29 2c 20 6d 69 {v, max(0,v), mi
0d70: 6e 28 30 2c 76 29 2c 20 76 3d 3d 2b 31 2c 20 76 n(0,v), v==+1, v
0d80: 3d 3d 2d 31 2c 20 66 61 6c 73 65 7d 3b 0a 09 09 ==-1, false};...
0d90: 09 2f 2f 20 2d 2d 2d 20 49 4e 49 54 49 41 4c 49 .// --- INITIALI
0da0: 5a 45 20 42 41 53 45 20 31 2d 45 4c 45 4d 45 4e ZE BASE 1-ELEMEN
0db0: 54 20 4e 4f 44 45 53 20 2d 2d 2d 0a 09 09 09 74 T NODES ---....t
0dc0: 72 65 65 2e 62 61 63 6b 28 29 5b 69 5d 20 3d 20 ree.back()[i] =
0dd0: 6d 65 3b 0a 09 09 7d 0a 0a 09 09 77 68 69 6c 65 me;...}....while
0de0: 28 4e 3e 3e 3d 31 29 0a 09 09 7b 0a 09 09 09 74 (N>>=1)...{....t
0df0: 72 65 65 2e 72 65 73 69 7a 65 28 74 72 65 65 2e ree.resize(tree.
0e00: 73 69 7a 65 28 29 2b 31 29 3b 20 74 72 65 65 2e size()+1); tree.
0e10: 62 61 63 6b 28 29 2e 72 65 73 69 7a 65 28 4e 29 back().resize(N)
0e20: 3b 0a 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 ;....for(int i=0
0e30: 3b 20 69 3c 4e 3b 20 2b 2b 69 29 0a 09 09 09 09 ; i<N; ++i).....
0e40: 55 70 64 61 74 65 4d 69 64 4e 6f 64 65 28 74 72 UpdateMidNode(tr
0e50: 65 65 2e 73 69 7a 65 28 29 2d 31 2c 20 69 29 3b ee.size()-1, i);
0e60: 0a 09 09 7d 0a 09 7d 0a 0a 09 69 6e 74 20 43 6f ...}..}...int Co
0e70: 75 6e 74 28 29 0a 09 7b 0a 09 09 4e 6f 64 65 20 unt()..{...Node
0e80: 78 20 3d 20 43 61 6e 6f 6e 69 63 61 6c 28 74 72 x = Canonical(tr
0e90: 65 65 2e 73 69 7a 65 28 29 2d 31 2c 20 30 29 3b ee.size()-1, 0);
0ea0: 0a 09 09 72 65 74 75 72 6e 20 78 2e 6d 61 78 4c ...return x.maxL
0eb0: 65 66 74 20 2b 20 78 2e 6e 37 3b 0a 09 7d 0a 0a eft + x.n7;..}..
0ec0: 09 76 6f 69 64 20 53 77 69 74 63 68 28 69 6e 74 .void Switch(int
0ed0: 20 4c 2c 20 69 6e 74 20 52 29 0a 09 7b 0a 09 09 L, int R)..{...
0ee0: 53 77 69 74 63 68 52 65 63 28 74 72 65 65 5b 30 SwitchRec(tree[0
0ef0: 5d 2e 73 69 7a 65 28 29 2c 20 74 72 65 65 2e 73 ].size(), tree.s
0f00: 69 7a 65 28 29 2d 31 2c 20 30 2c 20 4c 2c 20 52 ize()-1, 0, L, R
0f10: 29 3b 0a 09 7d 0a 0a 09 76 6f 69 64 20 53 77 69 );..}...void Swi
0f20: 74 63 68 52 65 63 28 69 6e 74 20 53 74 72 69 64 tchRec(int Strid
0f30: 65 2c 20 69 6e 74 20 6c 76 2c 20 69 6e 74 20 69 e, int lv, int i
0f40: 64 78 2c 20 69 6e 74 20 52 61 77 5f 4c 2c 20 69 dx, int Raw_L, i
0f50: 6e 74 20 52 61 77 5f 52 29 0a 09 7b 0a 09 09 2f nt Raw_R)..{.../
0f60: 2f 20 4f 75 74 73 69 64 65 0a 09 09 69 66 28 20 / Outside...if(
0f70: 52 61 77 5f 52 20 3c 3d 20 53 74 72 69 64 65 2a Raw_R <= Stride*
0f80: 69 64 78 20 7c 7c 20 53 74 72 69 64 65 2a 28 69 idx || Stride*(i
0f90: 64 78 2b 31 29 20 3c 3d 20 52 61 77 5f 4c 20 29 dx+1) <= Raw_L )
0fa0: 0a 09 09 09 72 65 74 75 72 6e 3b 0a 0a 09 09 2f ....return;..../
0fb0: 2f 20 49 6e 73 69 64 65 0a 09 09 62 6f 6f 6c 26 / Inside...bool&
0fc0: 20 6d 65 20 3d 20 74 72 65 65 5b 6c 76 5d 5b 69 me = tree[lv][i
0fd0: 64 78 5d 2e 73 77 69 74 63 68 65 64 3b 0a 09 09 dx].switched;...
0fe0: 69 66 28 20 52 61 77 5f 4c 20 3c 3d 20 53 74 72 if( Raw_L <= Str
0ff0: 69 64 65 2a 69 64 78 20 26 26 20 53 74 72 69 64 ide*idx && Strid
1000: 65 2a 28 69 64 78 2b 31 29 20 3c 3d 20 52 61 77 e*(idx+1) <= Raw
1010: 5f 52 20 29 0a 09 09 7b 0a 09 09 09 6d 65 20 5e _R )...{....me ^
1020: 3d 20 31 3b 0a 09 09 09 72 65 74 75 72 6e 3b 0a = 1;....return;.
1030: 09 09 7d 0a 0a 09 09 2f 2f 20 4f 76 65 72 6c 61 ..}....// Overla
1040: 70 0a 09 09 74 72 65 65 5b 6c 76 2d 31 5d 5b 69 p...tree[lv-1][i
1050: 64 78 2a 32 5d 2e 73 77 69 74 63 68 65 64 20 20 dx*2].switched
1060: 20 5e 3d 20 6d 65 3b 0a 09 09 74 72 65 65 5b 6c ^= me;...tree[l
1070: 76 2d 31 5d 5b 69 64 78 2a 32 2b 31 5d 2e 73 77 v-1][idx*2+1].sw
1080: 69 74 63 68 65 64 20 5e 3d 20 6d 65 3b 0a 09 09 itched ^= me;...
1090: 53 77 69 74 63 68 52 65 63 28 53 74 72 69 64 65 SwitchRec(Stride
10a0: 2f 32 2c 20 6c 76 2d 31 2c 20 69 64 78 2a 32 2c /2, lv-1, idx*2,
10b0: 20 20 20 52 61 77 5f 4c 2c 20 52 61 77 5f 52 29 Raw_L, Raw_R)
10c0: 3b 0a 09 09 53 77 69 74 63 68 52 65 63 28 53 74 ;...SwitchRec(St
10d0: 72 69 64 65 2f 32 2c 20 6c 76 2d 31 2c 20 69 64 ride/2, lv-1, id
10e0: 78 2a 32 2b 31 2c 20 52 61 77 5f 4c 2c 20 52 61 x*2+1, Raw_L, Ra
10f0: 77 5f 52 29 3b 0a 09 09 55 70 64 61 74 65 4d 69 w_R);...UpdateMi
1100: 64 4e 6f 64 65 28 6c 76 2c 20 69 64 78 29 3b 0a dNode(lv, idx);.
1110: 09 7d 0a 7d 3b 0a 2a 2f 0a .}.};.*/.