Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdlib>
- #include <vector>
- using namespace std;
- class FenwickTree
- {
- private:
- vector<int> ft;
- inline int LSOne(int s)
- {
- return s & (-s);
- }
- public:
- FenwickTree() {}
- FenwickTree(int n)
- {
- ft.assign(n + 1, 0);
- }
- int rsq(int b)
- {
- int sum = 0;
- for (; b; b -= LSOne(b))
- sum += ft[b];
- return sum;
- }
- int rsq(int a, int b)
- {
- return rsq(b) - (a == 1 ? 0 : rsq(a - 1));
- }
- void adjust(int k, int v)
- {
- for (; k < (int)ft.size(); k += LSOne(k))
- ft[k] += v;
- }
- void set(int k, int v)
- {
- int diff = v - rsq(k, k);
- adjust(k, diff);
- }
- };
- int main()
- { int count=1;
- int fuck=0;
- stament:
- int N;
- cin>>N;
- if(N==0)
- return 0;
- cout<<"Case "<<count<<":"<<endl;
- if(fuck++)
- cout<<"\n"
- FenwickTree ft(N);
- int value;
- for(int i=1;i<=N;i++)
- {
- cin>>value;
- ft.adjust(i,value);
- }
- string c;
- int x,y;
- while(1)
- {
- cin>>c;
- if(c=="M")
- {
- cin>>x>>y;
- cout<<ft.rsq(x,y);
- }
- else if (c=="S")
- {
- cin>>x>>y;
- ft.set(x,y);
- }
- else if(c=="END")
- {
- count++;
- goto stament;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment