Question :- Range Updates and Sums on cses Link The 2nd test case is failing for 45 queries rest (65k queries) are correct. I am not able to find the logical mistake in lazy updates part. Please can you help to solve this
Update:- The Problem was in update part of lazy rest of the code is right.
Non-Working Code
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
#define Fast ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define endl '\n'
using namespace std;
void judge() {
#ifndef ONLINE_JUDGE
FILE_READ_IN
FILE_READ_OUT
#endif
}
const int N = 2e5 + 1;
int n, q;
// the input array
int a[N];
// the segment tree
int t[4 * N];
// for storing lazy set updates
int change[4 * N];
// for storing lazy increase
int inc[4 * N];
void build(int n, int s, int e) {
if (s == e) {
t[n] = a[s];
return;
}
int m = (s + e) / 2;
build(2 * n, s, m);
build(2 * n + 1, m + 1, e);
// normal merging sum
t[n] = t[2 * n] + t[2 * n + 1];
}
void lazy(int n, int s, int e) {
// if the lazy increase is having some value then it has not been updated
if (inc[n]) {
// changing the value in current node
t[n] += ((e - s + 1ll) * inc[n]);
// change child is having some value then the set updates haven't reached the child and so the lazy set update has to increased
if (change[2 * n])change[2 * n] += inc[n];
else
inc[2 * n] += inc[n]; // otherwise we increase the lazy increase update
if (change[2 * n + 1])change[2 * n + 1] += inc[n];
else
inc[2 * n + 1] += inc[n];
inc[n] = 0;
}
if (change[n]) {
// if change is having value then this will overwrite any other updates
t[n] = (e - s + 1ll) * change[n];
// passes the updates to the children
change[2 * n] = change[n];
change[2 * n + 1] = change[n];
change[n] = 0;
// inc[n] = 0;
}
}
int query(int n, int s, int e, int l, int r) {
lazy(n, s, e);
// out of range case
if (s > e || s > r || e < l)return 0;
// in range case
if (s >= l && e <= r) {
return t[n];
}
int m = (s + e) / 2;
int x = query(2 * n, s, m, l, r);
int y = query(2 * n + 1, m + 1, e, l, r);
t[n] = t[2 * n] + t[2 * n + 1];
return x + y;
}
void updatecha(int n, int s, int e, int l, int r, int val) {
lazy(n, s, e);
// out of range case
if (s > e || s > r || e < l)return;
// in range case
if (s >= l && e <= r) {
t[n] = (e - s + 1ll) * val;
change[2 * n] = val;
change[2 * n + 1] = val;
return;
}
int m = (s + e) / 2;
updatecha(2 * n, s, m, l, r, val);
updatecha(2 * n + 1, m + 1, e, l, r, val);
t[n] = t[2 * n] + t[2 * n + 1];
}
void updateinc(int n, int s, int e, int l, int r, int val) {
lazy(n, s, e);
// out of range case
if (s > e || s > r || e < l)return;
// in range case
if (s >= l && e <= r) {
t[n] += ((e - s + 1ll) * val);
if (change[2 * n])change[2 * n] += val;
else
inc[2 * n] += val;
if (change[2 * n + 1])change[2 * n + 1] += val;
else
inc[2 * n + 1] += val;
return;
}
int m = (s + e) / 2;
updateinc(2 * n, s, m, l, r, val);
updateinc(2 * n + 1, m + 1, e, l, r, val);
t[n] = t[2 * n] + t[2 * n + 1];
}
signed main() {
Fast;
int t = 1;
judge();
// cin >> t;
while (t--) {
cin >> n >> q;
for (int i = 1; i <= n; i++)cin >> a[i];
build(1, 1, n);
for (int i = 0; i < q; i++) {
int op, l, r;
cin >> op >> l >> r;
if (op <= 2) {
int x;
cin >> x;
if (op == 2) {
updatecha(1, 1, n, l, r, x);
}
else {
updateinc(1, 1, n, l, r, x);
}
}
else {
cout << query(1, 1, n, l, r) << endl;
}
}
}
}
Updated and working code
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
#define Fast ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define deb(x) cout<<#x<<" "<<x<<endl;
#define all(v) v.begin(),v.end()
#define endl '\n'
using namespace std;
void judge() {
#ifndef ONLINE_JUDGE
FILE_READ_IN
FILE_READ_OUT
#endif
}
const int N = 2e5 + 1;
int n, q;
int a[N];
int t[4 * N];
int change[4 * N];
int inc[4 * N];
void build(int n, int s, int e) {
if (s == e) {
t[n] = a[s];
return;
}
int m = (s + e) / 2;
build(2 * n, s, m);
build(2 * n + 1, m + 1, e);
t[n] = t[2 * n] + t[2 * n + 1];
}
void apply(int n, int s, int e, int ch, int i) {
t[n] += i * (e - s + 1);
if (ch) {
t[n] = (e - s + 1) * ch;
i = 0;
}
if (change[n])change[n] += i;
else
inc[n] += i;
if (ch)change[n] = ch;
}
void push(int n, int s, int e, int m) {
apply(2 * n, s, m, change[n], inc[n]);
apply(2 * n + 1, m + 1, e, change[n], inc[n]);
change[n] = 0;
inc[n] = 0;
}
int query(int n, int s, int e, int l, int r) {
if (s >= l && e <= r) {
return t[n];
}
int m = (s + e) / 2;
push(n, s, e, m);
int x = 0, y = 0;
if (l <= m)
x = query(2 * n, s, m, l, r);
if (r > m)
y = query(2 * n + 1, m + 1, e, l, r);
return x + y;
}
void updatecha(int n, int s, int e, int l, int r, int val) {
if (s >= l && e <= r) {
apply(n, s, e, val, 0);
return;
}
int m = (s + e) / 2;
push(n, s, e, m);
if (l <= m)
updatecha(2 * n, s, m, l, r, val);
if (r > m)
updatecha(2 * n + 1, m + 1, e, l, r, val);
t[n] = t[2 * n] + t[2 * n + 1];
}
void updateinc(int n, int s, int e, int l, int r, int val) {
if (s >= l && e <= r) {
apply(n, s, e, 0, val);
return;
}
int m = (s + e) / 2;
push(n, s, e, m);
if (l <= m)
updateinc(2 * n, s, m, l, r, val);
if (r > m)
updateinc(2 * n + 1, m + 1, e, l, r, val);
t[n] = t[2 * n] + t[2 * n + 1];
}
signed main() {
Fast;
int t = 1;
judge();
// cin >> t;
while (t--) {
cin >> n >> q;
for (int i = 1; i <= n; i++)cin >> a[i];
build(1, 1, n);
for (int i = 0; i < q; i++) {
int op, l, r;
cin >> op >> l >> r;
if (op <= 2) {
int x;
cin >> x;
if (op == 2) {
updatecha(1, 1, n, l, r, x);
}
else {
updateinc(1, 1, n, l, r, x);
}
}
else {
cout << query(1, 1, n, l, r) << endl;
}
}
}
}
