uva 12532 - Interval Product

  1  /*
  2  Problem link
  3  Type: Data structure - Binary index (Fenwick) tree
  4  Algorithm:
  5      Range Sum Query problem (RSQ):
  6      BIT is one good self-implement data structure that
  7      can efficiently answer Range Sum Query (RSQ) problem.
  8      RSQ are problems that require us to do the queries:
  9          - Calculate the sum of a[r..l].
 10          - Update a[k] to value v.
 11      on a given array.
 12      For example:
 13          a: 3 4 2 1 3 4 5 1 2 3 (index starts at 1)
 14      RSQ(1,6) = 17
 15      RSQ(3,5) = 6
 16  
 17      Binary index tree (BIT):
 18      For an array of n elements, the corresponding BIT
 19      will also have n elements as well. Element i of
 20      the BIT will control a range from a[i-LSOne(i)+1..i]
 21      (i.e the sum from a[i-LSOne(i)+1] to a[i])
 22      LSOne is the function that return the Least Significant
 23      One-bit.
 24      Example:
 25          LSOne(2) = 2: 2->10->LSOne(2) = 10 = 2;
 26          LSOne(6) = 2: 6->110->LSOne(6) = 10 = 2;
 27          LSOne(3) = 1: 3->11->LSOne(3) = 1 = 1;
 28          LSOne(8) = 8: 8->1000->LSOne(8) = 1000 = 8;
 29      Calculating sum(1..k) with BIT:
 30          sum[k] = tree[k] + tree[k'] + tree[k'']...
 31          with k(n) = k(n-1) - LSOne(k);
 32      -> Calculating the sum(l..r) = sum(1..r) - sum(1..l-1);
 33      Updating a[k] to v on BIT:
 34          tree[k]+=v; tree[k']+=v; tree[k'']+=v;
 35          with k(n) = k(n-1) + LSOne(k);
 36  
 37      Apply to problem:
 38          In this problem, all we care about is the number
 39          of negative values and the number of 0 value.
 40          For a range [l..r], P[l..r] = 0 if it contains
 41          any 0 value, or else P[l..r] = '-' when the number
 42          of negative values is odd and vice versa. Hence this is
 43          a RSQ problem of finding the number of negative values
 44          and 0 in a given range.
 45  */
 46  #include <iostream>
 47  #include <cstdio>
 48  #include <cstring>
 49  #include <cmath>
 50  #include <vector>
 51  
 52  #define LSOne(X) (X & (-X))
 53  
 54  using namespace std;
 55  const int maxn = 100010;
 56  
 57  // This class implementation is referenced
 58  // from Competitive Programming 3 book.
 59  class BIT {
 60  private:
 61      vector<int> ft;
 62  public:
 63      BIT(int n) { ft.assign(n+1, 0); }
 64  
 65      int sum(int k) {
 66          int result = 0;
 67          for (; k>0; k -= LSOne(k)) result += ft[k];
 68          return result;
 69      }
 70  
 71      int sum(int a, int b) {
 72          return (sum(b) - (a == 1? 0 : sum(a-1)));
 73      }
 74  
 75      void adjust(unsigned int k, int v) {
 76          for (; k < ft.size(); k += LSOne(k)) ft[k] += v;
 77      }
 78  
 79      ~BIT() { ft.clear(); }
 80  };
 81  
 82  struct Query {
 83      char type;
 84      int a;
 85      int b;
 86  };
 87  
 88  Query query[maxn];
 89  int a[maxn];
 90  int n, k;
 91  
 92  bool readFile();
 93  
 94  int main() {
 95      while (readFile()) {
 96          BIT tree1(n);
 97          BIT tree2(n);
 98          for (int i = 1; i <= n; i++) {
 99              if (a[i] < 0) tree1.adjust(i, 1);
100              if (a[i] == 0) tree2.adjust(i, 1);
101          }
102          for (int i = 1; i <= k; i++) {
103              if (query[i].type == 'P') {
104                  if (tree2.sum(query[i].a, query[i].b) > 0) cout << 0;
105                  else if (tree1.sum(query[i].a, query[i].b)%2 == 0) cout << "+";
106                  else cout << "-";
107              } else {
108                  if (query[i].b == 0 && a[query[i].a] != 0) {
109                      if (a[query[i].a] < 0) tree1.adjust(query[i].a, -1);
110                      tree2.adjust(query[i].a, 1);
111                  }
112                  if (query[i].b < 0 && a[query[i].a] >= 0) {
113                      if (a[query[i].a] == 0) tree2.adjust(query[i].a, -1);
114                      tree1.adjust(query[i].a, 1);
115                  }
116                  if (query[i].b > 0) {
117                      if (a[query[i].a] == 0) tree2.adjust(query[i].a, -1);
118                      else if (a[query[i].a] < 0) tree1.adjust(query[i].a, -1);
119                  }
120                  a[query[i].a] = query[i].b;
121              }
122          }
123          cout << endl;
124      }
125      return 0;
126  }
127  
128  bool readFile() {
129      cin >> n >> k;
130      if (cin.eof()) return false;
131      char type;
132      int aa, bb;
133  
134      for (int i = 1; i <=n; i++) cin >> a[i];
135      for (int i = 1; i <=k; i++) {
136          cin >> type >> aa >> bb;
137          query[i].type = type;
138          query[i].a = aa;
139          query[i].b = bb;
140      }
141      return true;
142  }