keymasterviriya1150

Untitled

Mar 15th, 2016
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.22 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. class FenwickTree
  9. {
  10. private:
  11.   vector<int> ft;
  12.  
  13.   inline int LSOne(int s)
  14.   {
  15.     return s & (-s);
  16.   }
  17.  
  18. public:
  19.   FenwickTree() {}
  20.  
  21.   FenwickTree(int n)
  22.   {
  23.     ft.assign(n + 1, 0);
  24.   }
  25.  
  26.   int rsq(int b)
  27.   {
  28.     int sum = 0;
  29.    
  30.     for (; b; b -= LSOne(b))
  31.       sum += ft[b];
  32.    
  33.     return sum;
  34.   }
  35.  
  36.   int rsq(int a, int b)
  37.   {
  38.     return rsq(b) - (a == 1 ? 0 : rsq(a - 1));
  39.   }
  40.  
  41.   void adjust(int k, int v)
  42.   {
  43.     for (; k < (int)ft.size(); k += LSOne(k))
  44.       ft[k] += v;
  45.   }
  46.  
  47.   void set(int k, int v)
  48.   {
  49.     int diff = v - rsq(k, k);
  50.    
  51.     adjust(k, diff);
  52.   }
  53. };
  54.  
  55. int main()
  56. {   int count=1;
  57.     int fuck=0;
  58.     stament:  
  59.     int N;
  60.     cin>>N;
  61.     if(N==0)
  62.         return 0;
  63.     cout<<"Case "<<count<<":"<<endl;  
  64.     if(fuck++)
  65.         cout<<"\n"              
  66.     FenwickTree ft(N);
  67.     int value;
  68.     for(int i=1;i<=N;i++)
  69.     {
  70.         cin>>value;
  71.         ft.adjust(i,value);
  72.     }
  73.     string c;
  74.     int x,y;
  75.     while(1)
  76.     {
  77.         cin>>c;
  78.         if(c=="M")
  79.         {
  80.             cin>>x>>y;
  81.             cout<<ft.rsq(x,y);
  82.         }
  83.         else if (c=="S")
  84.         {
  85.             cin>>x>>y;
  86.             ft.set(x,y);
  87.         }
  88.         else if(c=="END")
  89.         {
  90.             count++;
  91.             goto stament;
  92.         }
  93.     }
  94.     return 0;
  95.    
  96. }
Advertisement
Add Comment
Please, Sign In to add comment