• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Modified lib/dataStructure/segmentTree.cpp from [d90f43e790c04822] to [0226be12935bcdf4].

     1      1   //-------------------------------------------------------------
     2      2   // Segment tree
     3      3   //   in some general form
     4      4   //
     5      5   // Verified by
            6  +//   - Codeforces 107 C
     6      7   //   - Codeforces 104 E
     7      8   //-------------------------------------------------------------
     8      9   
           10  +template<typename Node>
           11  +class SegmentTree
           12  +{
           13  +public:
           14  + template<typename Seq>
           15  + SegmentTree(const Seq& s) {
           16  +  int N = 1;
           17  +  while( N < s.size() )
           18  +   N <<= 1;
           19  +
           20  +  tree.resize(tree.size()+1); tree.back().resize(N);
           21  +  for(int i=0; i<N; ++i)
           22  +   tree.back()[i] = i<s.size() ? Node::One(s[i]) : Node::Zero();
           23  +
           24  +  while(N>>=1) {
           25  +   tree.resize(tree.size()+1); tree.back().resize(N);
           26  +   for(int i=0; i<N; ++i)
           27  +    CalcMidNode(tree.size()-1, i);
           28  +  }
           29  + }
           30  +
           31  + Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n)
           32  +  return QueryRec(s, e, tree.size()-1, 0, tree[0].size());
           33  + }
           34  +
           35  + template<typename Value>
           36  + void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n�E|e-s|)
           37  +  SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size());
           38  + }
           39  +
           40  +private:
           41  + void CalcMidNode(int lv, int idx)
           42  + {
           43  +  tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2+1]);
           44  + }
           45  +
           46  + Node QueryRec(int s, int e, int lv, int idx, int stride)
           47  + {
           48  +  const int myL = stride*idx;
           49  +  const int myR = stride*(idx+1);
           50  +  if( e<=myL || myR<=s )
           51  +   return Node::Zero();
           52  +  if( s<=myL && myR<=e )
           53  +   return tree[lv][idx];
           54  +  return Node::Concat(QueryRec(s,e,lv-1,idx*2,stride/2),
           55  +                      QueryRec(s,e,lv-1,idx*2+1,stride/2));
           56  + }
           57  +
           58  + void SetRec(int s, int e, const Node& n, int lv, int idx, int stride)
           59  + {
           60  +  const int myL = stride*idx;
           61  +  const int myR = stride*(idx+1);
           62  +  if( e<=myL || myR<=s )
           63  +   return;
           64  +  if( stride == 1 ) {
           65  +   tree[lv][idx] = n;
           66  +  } else {
           67  +   SetRec(s,e,n,lv-1,idx*2,stride/2);
           68  +   SetRec(s,e,n,lv-1,idx*2+1,stride/2);
           69  +   CalcMidNode(lv, idx);
           70  +  }
           71  + }
           72  +
           73  + vector< vector<Node> > tree;
           74  +};
           75  +
           76  +struct Node
           77  +{
           78  + double sum;
           79  + double maxLeft;
           80  + double maxRight;
           81  + double maxSum;
           82  + static Node Zero()
           83  + {
           84  +  Node c = {0, 0, 0, 0};
           85  +  return c;
           86  + }
           87  + static Node One(double v)
           88  + {
           89  +  Node c = {v, max(0.0,v), max(0.0,v), max(0.0,v)};
           90  +  return c;
           91  + }
           92  + static Node Concat(const Node& l, const Node& r)
           93  + {
           94  +  Node c = {
           95  +   l.sum + r.sum,
           96  +   max(l.maxLeft, l.sum+r.maxLeft),
           97  +   max(l.maxRight+r.sum, r.maxRight),
           98  +   max(max(l.maxSum, r.maxSum), l.maxRight+r.maxLeft),
           99  +  };
          100  +  return c;
          101  + }
          102  +};
          103  +
          104  +/*
     9    105   class SegmentTree
    10    106   {
    11    107    // --- DATA FOR EACH NODE ---
    12    108    struct Node
    13    109    {
    14    110     int sum;
    15    111     int maxLeft;
................................................................................

   104    200     tree[lv-1][idx*2].switched   ^= me;
   105    201     tree[lv-1][idx*2+1].switched ^= me;
   106    202     SwitchRec(Stride/2, lv-1, idx*2,   Raw_L, Raw_R);
   107    203     SwitchRec(Stride/2, lv-1, idx*2+1, Raw_L, Raw_R);
   108    204     UpdateMidNode(lv, idx);
   109    205    }
   110    206   };
          207  +*/