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;
}
}
}
}
post this with your original handle, then we will help
You don't need segment trees you can do this just by using map.
How to solve with map?
It is intuitive enough.
Could you give the overview of the idea?
You can also solve it with Prefix Sums over the array and SQRT Decomp. on the queries.
I thought about using sqrt decomposition, but the thing is it might tle.