uva 12086 - Potentiometers

 1  /*
 2  Problem link
 3  Type: Data structure - BIT
 4  Algorithm:
 5      Another BIT problem, the solution is obvious.
 6      See UVA 12532 - Interval Product for reference.
 7      We can also use Segment Tree to solve this problem.
 8  */
 9  #include <iostream>
10  #include <cstdio>
11  #include <cstring>
12  #include <cmath>
13  #include <vector>
14  
15  #define LSOne(X) (X & (-X))
16  
17  using namespace std;
18  const int maxn = 200010;
19  
20  class BIT {
21  private:
22      vector<int> ft;
23  public:
24      BIT(int n) { ft.assign(n+1, 0); }
25      int sum(int k) {
26          int result = 0;
27          for (; k > 0; k -= LSOne(k))result += ft[k];
28          return result;
29      }
30      int sum(int l, int r) {
31          return (sum(r) - (l > 1? sum(l-1): 0));
32      }
33      void adjust(unsigned int k, int v) {
34          for (; k < ft.size(); k += LSOne(k)) ft[k] += v;
35      }
36      ~BIT() { ft.clear(); }
37  };
38  
39  struct Query {
40      char type;
41      int a, b;
42      Query(char t, int aa, int bb): type(t), a(aa), b(bb) {}
43  };
44  
45  int a[maxn];
46  vector<Query> q;
47  int n, k;
48  
49  bool readFile();
50  
51  int main()
52  {
53      int nTest = 0;
54      while (readFile()) {
55          BIT tree(n);
56          if (nTest == 1) cout << endl;
57          printf("Case %d:\n", ++nTest);
58          for (int i = 1; i <= n; i++) tree.adjust(i, a[i]);
59          for (unsigned int i = 0; i < q.size(); i++) {
60              if (q[i].type == 'M') cout << tree.sum(q[i].a, q[i].b) << endl;
61              else {
62                  int tmp = q[i].b - a[q[i].a];
63                  tree.adjust(q[i].a, tmp);
64                  a[q[i].a] = q[i].b;
65              }
66          }
67          q.clear();
68      }
69      return 0;
70  }
71  
72  bool readFile() {
73      k = 0;
74      string type;
75      int l, r;
76      cin >> n;
77      if (n == 0) return false;
78      for (int i = 1; i <= n; i++) cin >> a[i];
79      while (true) {
80          cin >> type;
81          if (type == "END") break;
82          cin >> l >> r;
83          q.push_back(Query(type[0], l, r));
84      }
85      return true;
86  }