Finally Solved
Thanks to the testcase by DuongForeverAlone, I have solved the problem. I plan to Write a complete Step By Step Breakdown of the Problem Really Soon. Here is the Correct Code.
Correct Code (You Can Use it as a LazyProp Template as well)
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false);cin.tie(NULL)
#define int long long
int INF = 1e18;
int NINF = -1e18;
int MOD = 1000000000+7;
class LazyDS
{
public:
bool flag = false;
int a = 0;
int d = 0;
};
class SegDS
{
public:
int sum = 0;
};
class LazySegmentTree
{
private:
vector<SegDS> stree;
vector<LazyDS> ltree;
public:
int n;
vector<int> base;
LazySegmentTree(int _n)
{
n = _n;
base.assign(n, 0ll);
ltree.assign(4*n, LazyDS());
stree.assign(4*n, SegDS());
}
void init()
{
init(0, n-1, 1);
}
void init(int tl, int tr, int idx)
{
if(tl == tr)
{
stree[idx].sum = base[tl];
}
else
{
int tm = tl + (tr-tl)/2;
init(tl, tm, 2*idx);
init(tm+1, tr, 2*idx+1);
stree[idx] = merge_seg_ds(stree[2*idx], stree[2*idx+1]);
}
}
void print(int tl, int tr, int idx)
{
if(tl == tr)
{
cout << "{"<<tl <<", "<<tr<<","<<stree[idx].sum << ", " << ltree[idx].a << ", "<< ltree[idx].d <<", " << (ltree[idx].flag ? "true": "false") <<"}" << endl;
}
else
{
int tm = tl + (tr-tl)/2;
print(tl, tm, 2*idx);
print(tm+1, tr, 2*idx+1);
// cout << "{"<<tl <<", "<<tr<<","<<stree[idx].sum << ", " << ltree[idx].a << ", "<< ltree[idx].d <<", " << (ltree[idx].flag ? "true": "false") <<"}" << endl;
}
}
LazyDS merge_lazy_ds(LazyDS a, LazyDS b)
{
if(a.flag == false)
return b;
if(b.flag == false)
return a;
a.a += b.a;
a.d += b.d;
return a;
}
SegDS merge_seg_ds(SegDS a, SegDS b)
{
a.sum += b.sum;
return a;
}
void push(int tl, int tr, int idx)
{
if(!ltree[idx].flag)
return;
int a = ltree[idx].a;
int d = ltree[idx].d;
int n = tr - tl + 1;
stree[idx].sum += (n*(2*a + (n-1)*d))/2;
if(tl != tr)
{
LazyDS lds = ltree[idx];
ltree[2*idx] = merge_lazy_ds(ltree[2*idx], lds);
int tm = tl + (tr-tl)/2;
lds.a += (tm + 1 - tl)*d;
ltree[2*idx+1] = merge_lazy_ds(ltree[2*idx+1], lds);
// tm + 1 - tl = x - a
}
ltree[idx] = LazyDS();
}
void update(int l,int r)
{
update(0, n-1, 1, l, r);
}
void update(int tl, int tr, int idx, int l, int r)
{
push(tl, tr, idx);
if(l > tr || r < tl)
return;
if(l <= tl && tr <= r)
{
// do what ever you want
LazyDS lds = LazyDS();
lds.flag = true;
lds.a = tl - l + 1;
lds.d = 1;
// cout << "{"<< tl << ", " << tr << ", " << lds.a << ", " << tr-tl+1 << "}" << endl;
// l l+1 ...... tl
// 1 2 x
// tl - l = x - 1
ltree[idx] = merge_lazy_ds(ltree[idx], lds);
push(tl, tr, idx);
}
else
{
int tm = tl + (tr-tl)/2;
update(tl, tm, 2*idx, l, r);
update(tm+1, tr, 2*idx+1, l, r);
stree[idx] = merge_seg_ds(stree[2*idx], stree[2*idx+1]);
ltree[idx] = LazyDS();
}
}
SegDS query(int l, int r)
{
return query(0, n-1, 1, l, r);
}
SegDS query(int tl, int tr, int idx, int l, int r)
{
// return the appropriate base case
push(tl, tr, idx);
if(l > tr || r < tl)
return SegDS();
if(l <= tl && tr <= r)
{
return stree[idx];
}
int tm = tl + (tr-tl)/2;
SegDS left = query(tl, tm, 2*idx, l, r);
SegDS right = query(tm+1, tr, 2*idx+1, l, r);
return merge_seg_ds(left, right);
}
};
void solve();
void solve2();
int32_t main()
{
fastio;
int tests = 1;
// cin >> tests;
while(tests--)
{
solve();
}
return 0;
}
void solve()
{
int n, q;
cin >> n >> q;
LazySegmentTree lstree(n);
for(int i=0;i<n;i++)
{
cin >> lstree.base[i];
}
lstree.init();
// cout << "init finished" << endl;
// return ;
// cout << lstree.query(0, n-1).val << endl;
// lstree.update(0, 4);
// // cout << endl;
// lstree.update(0, 3);
// lstree.print(0, n-1, 1);
// cout << lstree.query(1, 4).sum << endl;
// cout << lstree.query(0, n-1).val << endl;
while(q--)
{
int type; cin >> type;
if(type == 1)
{
int l, r;
cin >> l >> r;
l--; r--;
// cout << "(" << l <<", " <<r <<")" << endl;
lstree.update(l, r);
// lstree.query(l, r);
}
else if(type == 2)
{
int l, r;
cin >> l >> r;
l--; r--;
// cout << "(" << l <<", " <<r <<")" << endl;
cout << lstree.query(l, r).sum << endl;
}
// for(int i=0;i<n;i++)
// lstree.query(i,i);
}
}
void solve2()
{
int n, q;
cin >> n >> q;
vector<int> v(n);
for(int i=0;i<n;i++)
cin >> v[i];
for(int i=0;i<q;i++)
{
// for(const int &num: v)
// cout << num << " ";
// cout << endl;
int type; cin >> type;
if(type == 1)
{
int l, r;
cin >> l >> r;
l--; r--;
int val = 1;
for(int j=l; j<=r;j++)
{
v[j] += val;
val++;
}
}
else if(type == 2)
{
int l, r;
cin >> l >> r;
l--; r--;
// cout << "(" << l <<", " <<r <<")" << endl;
// cout << lstree.query(l, r).sum << endl;
int val = 0;
for(int j=l; j<=r;j++)
{
val += v[j];
}
cout << val << endl;
}
}
}
/*
0 0 0 0 0
1 2 3 4 5
1 2 3 4
2 4 6 8 5
4+6+8+5 = 23
*/
I have been trying out the problem for a long time. the problem can be found here ( https://cses.fi/problemset/task/1736/ ). I hope someone can help me figure out my mistake. Thankyou in advance.
My Approach
I used a segment tree with lazy propagation. The Lazy Tree node contains if there is some addition in the corresponding interval and if there is what does it start with, the total can be calculated using simple arithmetic progression formula.
My Wrong Code
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false);cin.tie(NULL)
#define int long long
int INF = 1e18;
int NINF = -1e18;
int MOD = 1000000000+7;
class LazyDS
{
public:
bool flag = false;
int a = 0;
};
class SegDS
{
public:
int sum;
};
class LazySegmentTree
{
private:
vector<SegDS> stree;
vector<LazyDS> ltree;
public:
int n;
vector<int> base;
LazySegmentTree(int _n)
{
n = _n;
base.assign(n, 0ll);
ltree.assign(4*n, LazyDS());
stree.assign(4*n, SegDS());
}
void init()
{
init(0, n-1, 1);
}
void init(int tl, int tr, int idx)
{
if(tl == tr)
{
stree[idx].sum = base[tl];
}
else
{
int tm = tl + (tr-tl)/2;
init(tl, tm, 2*idx);
init(tm+1, tr, 2*idx+1);
stree[idx] = merge_seg_ds(stree[2*idx], stree[2*idx+1]);
}
}
LazyDS merge_lazy_ds(LazyDS a, LazyDS b)
{
if(a.flag == false)
return b;
if(b.flag == false)
return a;
a.a += b.a;
return a;
}
SegDS merge_seg_ds(SegDS a, SegDS b)
{
a.sum += b.sum;
return a;
}
void push(int tl, int tr, int idx)
{
if(!ltree[idx].flag)
return;
int a = ltree[idx].a;
int n = tr - tl + 1;
stree[idx].sum += (n*(2*a + (n-1)))/2;
if(tl != tr)
{
LazyDS lds = LazyDS();
lds.flag = true;
lds.a = a;
ltree[2*idx] = merge_lazy_ds(ltree[2*idx], lds);
int tm = tl + (tr-tl)/2;
lds.a = a + tm + 1 - tl;
ltree[2*idx+1] = merge_lazy_ds(ltree[2*idx+1], lds);
// tm + 1 - tl = x - a
}
ltree[idx] = LazyDS();
}
void update(int l,int r)
{
update(0, n-1, 1, l, r);
}
void update(int tl, int tr, int idx, int l, int r)
{
push(tl, tr, idx);
if(l > tr || r < tl)
return;
if(l <= tl && tr <= r)
{
// do what ever you want
LazyDS lds = LazyDS();
lds.flag = true;
lds.a = tl - l + 1;
// cout << "{"<< tl << ", " << tr << ", " << lds.a << ", " << tr-tl+1 << "}" << endl;
// l l+1 ...... tl
// 1 2 x
// tl - l = x - 1
ltree[idx] = merge_lazy_ds(ltree[idx], lds);
push(tl, tr, idx);
}
else
{
int tm = tl + (tr-tl)/2;
update(tl, tm, 2*idx, l, r);
update(tm+1, tr, 2*idx+1, l, r);
stree[idx] = merge_seg_ds(stree[2*idx], stree[2*idx+1]);
ltree[idx] = LazyDS();
}
}
SegDS query(int l, int r)
{
return query(0, n-1, 1, l, r);
}
SegDS query(int tl, int tr, int idx, int l, int r)
{
// return the appropriate base case
push(tl, tr, idx);
if(l > tr || r < tl)
return SegDS();
if(l <= tl && tr <= r)
{
return stree[idx];
}
int tm = tl + (tr-tl)/2;
SegDS left = query(tl, tm, 2*idx, l, r);
SegDS right = query(tm+1, tr, 2*idx+1, l, r);
return merge_seg_ds(left, right);
}
};
void solve();
int32_t main()
{
fastio;
int tests = 1;
// cin >> tests;
while(tests--)
{
solve();
}
return 0;
}
void solve()
{
int n, q;
cin >> n >> q;
LazySegmentTree lstree(n);
for(int i=0;i<n;i++)
{
cin >> lstree.base[i];
}
lstree.init();
// cout << "init finished" << endl;
// return ;
// cout << lstree.query(0, n-1).val << endl;
// cout << lstree.query(0, n-1).val << endl;
while(q--)
{
int type; cin >> type;
if(type == 1)
{
int l, r;
cin >> l >> r;
l--; r--;
// cout << "(" << l <<", " <<r <<")" << endl;
lstree.update(l, r);
// lstree.query(l, r);
}
else if(type == 2)
{
int l, r;
cin >> l >> r;
l--; r--;
// cout << "(" << l <<", " <<r <<")" << endl;
cout << lstree.query(l, r).sum << endl;
}
// for(int i=0;i<n;i++)
// lstree.query(i,i);
}
}
Auto comment: topic has been updated by SilverSurge (previous revision, new revision, compare).
Try this input and figure it out yourself :v
6 3
0 0 0 0 0 0
1 1 5
1 1 4
2 2 5
Auto comment: topic has been updated by SilverSurge (previous revision, new revision, compare).