obi2017p1_seg.cpp

#include <bits/stdc++.h>


const int N = 1e5+7;
typedef long long ll;

struct node {
	ll s;
	int l, r;
	ll lazy;

	node () : s(0), l(-1), r(-1), lazy(0) {};
	node (ll x, int _l, int _r) : l(_l), r(_r), s(x), lazy(0) {};
};

node seg[4*N];
ll v[N];

void refresh (int u) {
	if (seg[u].l != seg[u].r) {
		seg[2*u].lazy += seg[u].lazy;
		seg[2*u+1].lazy += seg[u].lazy;
	}
	seg[u].s += seg[u].lazy*(seg[u].r-seg[u].l+1);
	seg[u].lazy = 0;
}

node join (node a, node b) {
	return node(a.s + b.s, a.l, b.r);
}

node build (int u, int l, int r) {
	if (l == r) return seg[u] = node(v[l], l, r);
	int m = (l+r)/2;
	return seg[u] = join(build(2*u, l, m), build(2*u+1, m+1, r));
}

node get (int u, int l, int r) {
	refresh(u);
	if (r < seg[u].l || seg[u].r < l) return node();
	if (seg[u].l <= l && seg[u].r <= r) return seg[u];
	return join(get(2*u, l, r), get(2*u+1, l, r));
}

node upd (int u, int l, int r, ll x) {
	refresh(u);
	if (r < seg[u].l || seg[u].r < l) return seg[u];
	if (seg[u].l <= l && seg[u].r <= r) {
		seg[u].lazy = x;
		refresh(u);
		return seg[u];
	}
	return seg[u] = join(upd(2*u, l, r, x), upd(2*u+1, l, r, x));
}

Na linha 41 e 48 os sinais <= e >= estão invertidos?