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

Added lib/dataStructure/segmentTree.cpp version [d90f43e790c04822]

            1  +//-------------------------------------------------------------
            2  +// Segment tree
            3  +//   in some general form
            4  +//
            5  +// Verified by
            6  +//   - Codeforces 104 E
            7  +//-------------------------------------------------------------
            8  +
            9  +class SegmentTree
           10  +{
           11  + // --- DATA FOR EACH NODE ---
           12  + struct Node
           13  + {
           14  +  int sum;
           15  +  int maxLeft;
           16  +  int minLeft;
           17  +  int n4;
           18  +  int n7;
           19  +  bool switched;
           20  + };
           21  + // --- DATA FOR EACH NODE ---
           22  +
           23  + Node Canonical(int lv, int idx)
           24  + {
           25  +  Node& x = tree[lv][idx];
           26  +  // --- DO SOMETHING IF YOU NEED CANONICALIZATION ---
           27  +  if( !x.switched )
           28  +   return x;
           29  +  Node n = {-x.sum, -x.minLeft, -x.maxLeft, x.n7, x.n4, false};
           30  +  return n;
           31  +  // --- DO SOMETHING IF YOU NEED CANONICALIZATION ---
           32  + }
           33  +
           34  + void UpdateMidNode(int lv, int idx)
           35  + {
           36  +  Node l = Canonical(lv-1, idx*2);
           37  +  Node r = Canonical(lv-1, idx*2+1);
           38  +  // --- BOTTOM UP COMPUTATION ---
           39  +  Node me = {
           40  +   l.sum + r.sum,
           41  +   max(l.maxLeft, l.sum+r.maxLeft),
           42  +   min(l.minLeft, l.sum+r.minLeft),
           43  +   l.n4 + r.n4,
           44  +   l.n7 + r.n7,
           45  +   false
           46  +  };
           47  +  // --- BOTTOM UP COMPUTATION ---
           48  +  tree[lv][idx] = me;
           49  + }
           50  +
           51  + vector< vector<Node> > tree;
           52  +
           53  +public:
           54  + SegmentTree(const string& s)
           55  + {
           56  +  int N = 1;
           57  +  while( N < s.size() )
           58  +   N <<= 1;
           59  +
           60  +  tree.resize(tree.size()+1); tree.back().resize(N);
           61  +  for(int i=0; i<N; ++i)
           62  +  {
           63  +   // --- INITIALIZE BASE 1-ELEMENT NODES ---
           64  +   int v = i<s.size() ? (s[i]=='4' ? +1 : -1) : 0;
           65  +   Node me = {v, max(0,v), min(0,v), v==+1, v==-1, false};
           66  +   // --- INITIALIZE BASE 1-ELEMENT NODES ---
           67  +   tree.back()[i] = me;
           68  +  }
           69  +
           70  +  while(N>>=1)
           71  +  {
           72  +   tree.resize(tree.size()+1); tree.back().resize(N);
           73  +   for(int i=0; i<N; ++i)
           74  +    UpdateMidNode(tree.size()-1, i);
           75  +  }
           76  + }
           77  +
           78  + int Count()
           79  + {
           80  +  Node x = Canonical(tree.size()-1, 0);
           81  +  return x.maxLeft + x.n7;
           82  + }
           83  +
           84  + void Switch(int L, int R)
           85  + {
           86  +  SwitchRec(tree[0].size(), tree.size()-1, 0, L, R);
           87  + }
           88  +
           89  + void SwitchRec(int Stride, int lv, int idx, int Raw_L, int Raw_R)
           90  + {
           91  +  // Outside
           92  +  if( Raw_R <= Stride*idx || Stride*(idx+1) <= Raw_L )
           93  +   return;
           94  +
           95  +  // Inside
           96  +  bool& me = tree[lv][idx].switched;
           97  +  if( Raw_L <= Stride*idx && Stride*(idx+1) <= Raw_R )
           98  +  {
           99  +   me ^= 1;
          100  +   return;
          101  +  }
          102  +
          103  +  // Overlap
          104  +  tree[lv-1][idx*2].switched   ^= me;
          105  +  tree[lv-1][idx*2+1].switched ^= me;
          106  +  SwitchRec(Stride/2, lv-1, idx*2,   Raw_L, Raw_R);
          107  +  SwitchRec(Stride/2, lv-1, idx*2+1, Raw_L, Raw_R);
          108  +  UpdateMidNode(lv, idx);
          109  + }
          110  +};