• 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  };