Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Help Post on (MULTQ3 — Multiples of 3) [SPOJ]

Revision en2, by Muhammad_DinIslam, 2023-05-26 22:22:05
Where is the mistake? And where need to change? Please Help me.....

const int mxN = 1e5 + 10;
ll v[mxN], st[4 * mxN], lz[4 * mxN];
bool isMul(int x) {
return (x % 3 == 0);
}

void build(int s, int e, int i = 1) {
if (s == e) st[i] = isMul(v[s]);
else {
int mid = (s + e) / 2;
build(s, mid, i * 2);
build(mid + 1, e, i * 2 + 1);
st[i] = st[i * 2] + st[i * 2 + 1];
}
}

void lazy(int s, int e, int i) {
st[i] = isMul(lz[i]) * (e - s + 1);
if (s != e)
lz[i * 2] += lz[i], lz[i * 2 + 1] += lz[i];
lz[i] = 0;
}

ll query(int s, int e, int lb, int rb, int i = 1) {
if (lz[i]) lazy(s, e, i);
if (s > rb || e < lb) return 0ll;
if (s >= lb && e <= rb) return st[i];
int mid = (s + e) / 2;
ll a = query(s, mid, lb, rb, i * 2);
ll b = query(mid + 1, e, lb, rb, i * 2 + 1);
return a + b;
}

void update(int s, int e, int lb, int rb, ll val, int i = 1) {
if (lz[i]) lazy(s, e, i);
if (s > rb || e < lb) return;
if (s >= lb && e <= rb) {
st[i] += isMul(val * (e - s + 1));
// lz[i] = isMul(val * (e - s + 1));
if (s != e)
lz[i * 2] += val, lz[i * 2 + 1] += val;
}
else {
int mid = (s + e) / 2;
update(s, mid, lb, rb, val, i * 2);
update(mid + 1, e, lb, rb, val, i * 2 + 1);
st[i] = st[i * 2] + st[i * 2 + 1];
}
}


#### History

Revisions

Rev. Lang. By When Δ Comment
en2 Muhammad_DinIslam 2023-05-26 22:22:05 60
en1 Muhammad_DinIslam 2023-05-26 22:20:38 1592 Initial revision (published)