luchobazz / icpc-notebook Goto Github PK

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;
const int N = 6e5+20;
const int oo = 1e9;

struct st{ /// informacion de cada nodo
  st *left, *right;
  int sum, l, r, m, lazy;
  st(int l, int r) : l(l), r(r), sum(0), lazy(0) {
    if(l != r) {
      m = (l+r)/2;
      left = new st(l, m);
      right = new st(m+1, r);
    }
  }
  
  /// (l, l+1, l+2 .... r-1, r)
  /// x   x     x     x  x x x 
  /// (cuantos tengo) * x
  /// r-l+1
  /// 1 1   => 
  void propagate() {
    if(lazy != 0) {
      /// voy a actualizar el nodo
      sum += (r-l+1) * lazy;
      if(l != r) {
        left->lazy += lazy;
        right->lazy += lazy;
      }
      /// voy a propagar a mis hijos
      lazy = 0;
    }
  }
//  void update(int pos, int v) {
//    if(l == r) {
//      sum = v;
//    } else {
//      if(pos <= m) left->update(pos, v);
//      else right->update(pos, v);
//      sum = left->sum + right->sum;
//    }
//  }
  void update(int a, int b, int v) {
    propagate();
    if(a > r || b < l) return;
    if(a <= l && r <= b) {
      lazy = v;
      propagate();
      return;
    }
    left->update(a, b, v);
    right->update(a, b, v);
    sum = left->sum + right->sum;
  }
  int get(int a, int b) {
    propagate();
    if(a > r || b < l) return 0;
    if(a <= l && r <= b) return sum;
    return left->get(a, b) + right->get(a, b);
  }
};

int main(){

  st tree(0, 7);
  for(int i = 0; i < 7; i++) {
    int x; cin >> x;
    tree.update(i, i, x);
  }
  cout << tree.get(0, 7) << endl;
  tree.update(0, 7, 1);
  cout << tree.get(0, 7) << endl;

}

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;
const int N = 6e5+20;
const int oo = 1e9;

struct st{ /// informacion de cada nodo
  st *left, *right;
  int sum, l, r, m;
  st(int l, int r) : l(l), r(r), sum(0) {
    if(l != r) {
      m = (l+r)/2;
      left = new st(l, m);
      right = new st(m+1, r);
    }
  }
  void update(int pos, int v) {
    if(l == r) {
      sum = v;
    } else {
      if(pos <= m) left->update(pos, v);
      else right->update(pos, v);
      sum = left->sum + right->sum;
    }
  }
  int get(int a, int b) {
    if(a > r || b < l) return 0;
    if(a <= l && r <= b) return sum;
    return left->get(a, b) + right->get(a, b);
  }
};

int main(){

  st tree(0, 7);
  for(int i = 0; i < 7; i++) {
    int x; cin >> x;
    tree.update(i, x);
  }

  cout << tree.get(1, 6) << endl;

}

const int N = 102;
const int M = 102;
const int inf = 1e9;

int n;
int a[N][M];
int sum[N][M];

int query(int x1, int z1, int x2, int z2){
    return sum[x2][z2] + sum[x1-1][z1-1] - sum[x1-1][z2] - sum[x2][z1-1];
}

// at main()

for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= m; ++j) {
        cin >> a[i-1][j-1]; // 0-Indexed
        sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i-1][j-1];
    }
}

// query(x1, z1, x2, z2)

#define forn(i, n) for (int i = 0; i < int(n); ++i)
int n, m;

vector<vector<int>> grid, st;

#define NEUTRO 1e9

int op(int x, int y) {
    return min(x, y);
}

void build() {
    forn(i, n) forn(j, m) st[i+n][j+m] = grid[i][j];
    forn(i, n) for(int j = m-1 ;j; --j) st[i+n][j] = op(st[i+n][j << 1], st[i+n][j << 1 | 1]);
    for(int i=n-1;i;--i) forn(j, 2*m) st[i][j] = op(st[i<<1][j], st[i<<1|1][j]);
}
void update(int x, int y, int v) {
    st[x+n][y+m] = v;
    for(int j = y+m; j>1 ; j>>=1) st[x+n][j>>1] = op(st[x+n][j], st[x+n][j^1]);
    for(int i = x+n; i>1 ; i>>=1) for(int j = y+m; j ; j>>=1) st[i>>1][j] = op(st[i][j], st[i^1][j]);
}
int query(int x1, int x2, int y1, int y2) {
    int ans = NEUTRO;
    for(int i0 = x1+n, i1 = x2+n ; i0<i1 ; i0>>=1, i1>>=1){
        int t[4], q=0;
        if(i0 & 1) t[q++] = i0++;
        if(i1 & 1) t[q++] = --i1;
        forn(k, q) for(int j0 = y1+m, j1 = y2+m; j0<j1 ; j0>>=1, j1>>=1) {
            if(j0 & 1) ans = op(ans, st[t[k]][j0++]);
            if(j1 & 1) ans = op(ans, st[t[k]][--j1]);
        }
    }
    return ans;
}

// usage:
// cin >> n >> m;
// grid = vector<vector<int>>(n, vector<int>(m));
// forn(i, n) forn(j, m) cin >> grid[i][j];

// st = vector<vector<int>>(2*n, vector<int>(2*m));
// build();