Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <string>
- #include <stack>
- #include <set>
- #include <map>
- #define pii pair <int,int>
- using namespace std;
- using ll = long long;
- using ld = long double;
- void cv(vector <ll> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n\n";
- }
- ld n;
- int N;
- vector <ll> a;
- int L,R;
- int inter(int l, int r){
- //cout<<"LR= "<<L<<' '<<R<<'\n';
- //cout<<"lr= "<<l<<' '<<r<<'\n';
- if (l >= L && r <= R) {//cout<<"ONE\n";
- return 2;
- }
- else if (l < L && r >= L) {//cout<<"TWO\n";
- return 1;
- }
- else if (r > R && l <= R){//cout<<"THREE\n";
- return 1;
- }
- else return 0;
- }
- ll inf = pow(2, 63) - 100;
- struct tree{
- vector <ll> tot;//sum
- vector <ll> MIN;
- void bld(){
- tot.assign(2*N-1,0);
- MIN.assign(2*N-1, inf);
- for (int i = 0; i < n; ++i){
- tot[N - 1 + i] = a[i];
- MIN[N - 1 + i] = a[i];
- }
- for (int i = N * 2 - 2; i >= 2; i-=2){
- int id = (i - 1) / 2;
- tot[id] = tot[i] + tot[i-1];
- MIN[id] = min(MIN[i], MIN[i-1]);
- }
- }
- void sh(){
- cv(tot);
- //cv(MIN);
- }
- ll getS(int l, int r, int id){
- //cout<<"id = "<<id<<"\n";
- int how = inter(l, r);
- //cout<<"how= "<<how<<'\n';
- if (how == 2) return tot[id];
- else if (how == 0) return 0;
- else{
- int m = (l + r) / 2;
- return getS(l, m, id*2+1) + getS(m+1, r, id*2+2);
- }
- }
- ll getMin(int l, int r, int id){
- int how = inter(l, r);
- if (how == 2) return MIN[id];
- else if (how == 0) return inf;
- else{
- int m = (l + r) / 2;
- return min(getMin(l, m, id*2+1) , getMin(m+1, r, id*2+2));
- }
- }
- void chg(int id){
- tot[id] = tot[id*2 + 1] + tot[id*2 + 2];
- MIN[id] = min(tot[id*2 + 1], tot[id*2 + 2]);
- if (id == 0) return;
- chg( (id - 1) / 2);
- }
- };
- tree wrk;
- int main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin>>n;
- N = pow(2, ceil(log2(n)));
- a.assign(n, 0);
- wrk.bld();
- //wrk.sh();
- ll wht, x, y, res;
- while (true){
- cin>>wht;
- if (wht == 0) break;
- else if (wht == 1){
- cin>>x>>y;
- x--;
- x += N - 1;
- //cout<<"start id= "<<x<<'\n';
- wrk.tot[x] += y;
- wrk.chg( (x-1) / 2);
- //wrk.sh();
- //cout<<"tot[0] = "<<wrk.tot[0]<<'\n';
- }else{
- cin>>L>>R;
- L--;
- R--;
- res = wrk.getS(0, N-1, 0);
- cout<<res<<'\n';
- }
- }
- }
- /*
- 2
- 1 1 4
- 2 1 1
- 2 1 1
- 0
- 10
- */
Add Comment
Please, Sign In to add comment