Segment Tree + Lazy Propagation

Правка en1, от trainingtmp, 2015-10-07 02:13:56

I am trying to solve the following problem: http://www.spoj.com/problems/HORRIBLE/

I have tried many possible test cases and my code works fine.

Below is my code, any hint?

#include <iostream>
using namespace std;

typedef long long ll;

const int N = 1e5;  // limit for array size
ll n, h;  // array size
ll t[2 * N];
ll d[N];


void apply(int p, int value, int k) {
    t[p] += value * k;
    if (p < n) d[p] += value;
}


void build(int p) {
    int k = 1;
    while (p > 1) {
        p >>= 1;
        k <<= 1;
        t[p] = t[p<<1] + t[p<<1|1] + k * d[p];
    }
}

void push(int p) {
    for (int s = h; s > 0; --s) {
        int i = p >> s;
        if (d[i] != 0) {
            apply(i<<1, d[i], s);
            apply(i<<1|1, d[i], s);
            d[i] = 0;
        }
    }
}


void inc(int l, int r, int value) {
    l += n, r += n;
    int l0 = l, r0 = r;
    int k = 1;
    for (; l <= r; l >>= 1, r >>= 1, k <<= 1) {
        if (l & 1)      apply(l++, value, k);
        if (r % 2 == 0) apply(r--, value, k);
    }
    build(l0);
    build(r0);
}

ll query(int l, int r) {
    l += n, r += n;
    push(l);
    push(r);
    ll res = 0;
    for (; l <= r; l >>= 1, r >>= 1) {
        if (l & 1)      res += t[l++];
        if (r % 2 == 0) res += t[r--];
    }
    return res;
}



int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll T, C, p, q, v, o;
    
    cin >> T;
    
    for(int i = 0; i < T; i++) {

        cin >> n >> C;
        
        h = sizeof(int) * 8 - __builtin_clz(n);
        
        for(int j = 0; j < n; j++) {
            t[j + n] = 0;
            d[j] = 0;
        }
        
        for(int j = 0; j < C; j++) {
            cin >> o >> p >> q;
            if(o == 0) {
                cin >> v;
                inc(p - 1, q - 1, v);
            } else {
                cout << query(p - 1, q - 1) << '\n';
            }
        }
    }
    return 0;
}

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский trainingtmp 2015-11-25 11:19:20 2153
en3 Английский trainingtmp 2015-10-07 02:33:20 225
en2 Английский trainingtmp 2015-10-07 02:15:35 86
en1 Английский trainingtmp 2015-10-07 02:13:56 2110 Initial revision (published)