Hex Artifact Content
Not logged in

Artifact 0226be12935bcdf471d13b7a32e02813068ec2b1:


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 4f 28 6c 6f 67  q[s,e) ) : O(log
02e0: 20 6e 29 0a 09 09 72 65 74 75 72 6e 20 51 75 65   n)...return Que
02f0: 72 79 52 65 63 28 73 2c 20 65 2c 20 74 72 65 65  ryRec(s, e, tree
0300: 2e 73 69 7a 65 28 29 2d 31 2c 20 30 2c 20 74 72  .size()-1, 0, tr
0310: 65 65 5b 30 5d 2e 73 69 7a 65 28 29 29 3b 0a 09  ee[0].size());..
0320: 7d 0a 0a 09 74 65 6d 70 6c 61 74 65 3c 74 79 70  }...template<typ
0330: 65 6e 61 6d 65 20 56 61 6c 75 65 3e 0a 09 76 6f  ename Value>..vo
0340: 69 64 20 53 65 74 28 69 6e 74 20 73 2c 20 69 6e  id Set(int s, in
0350: 74 20 65 2c 20 56 61 6c 75 65 20 76 29 20 7b 20  t e, Value v) { 
0360: 2f 2f 20 73 65 71 5b 73 2c 65 29 3a 3d 76 20 3a  // seq[s,e):=v :
0370: 20 4f 28 6c 6f 67 20 6e 81 45 7c 65 2d 73 7c 29   O(log n.E|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                       .}.};.*/.