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 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);↵
↵
}↵
}↵
~~~~~↵
↵
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 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);↵
↵
}↵
}↵
~~~~~↵
↵
