Can somebody pls tell me where my code goes wrong i am using a flag variable to distinguish between add and set operation.This is segment tree edu section problem part 4-A it gives wrong answer on test 3.
Problem is Assignment, Addition, and Sum
My Code
template<typename Node, typename Update>
struct LazySGT {
vector<Node> tree;
vector<bool> lazy;
vector<Update> updates;
vector<ll> arr; // type may change
ll n;
ll s;
LazySGT(ll a_len, vector<ll> &a) { // change if type updated
arr = a;
n = a_len;
s = 1;
while(s < 2 * n){
s = s << 1;
}
tree.resize(s); fill(all(tree), Node());
lazy.resize(s); fill(all(lazy), false);
updates.resize(s); fill(all(updates), Update());
build(0, n - 1, 1);
}
void build(ll start, ll end, ll index) { // Never change this
if (start == end) {
tree[index] = Node(arr[start]);
return;
}
ll mid = (start + end) / 2;
build(start, mid, 2 * index);
build(mid + 1, end, 2 * index + 1);
tree[index].merge(tree[2 * index], tree[2 * index + 1]);
}
void pushdown(ll index, ll start, ll end){
if(lazy[index]){
ll mid = (start + end) / 2;
apply(2 * index, start, mid, updates[index]);
apply(2 * index + 1, mid + 1, end, updates[index]);
updates[index] = Update();
lazy[index] = 0;
}
}
void apply(ll index, ll start, ll end, Update& u){
if(start != end){
lazy[index] = 1;
updates[index].combine(u, start, end);
}
u.apply(tree[index], start, end);
}
void update(ll start, ll end, ll index, ll left, ll right, Update& u) { // Never Change this
if(start > right || end < left)
return;
if(start >= left && end <= right){
apply(index, start, end, u);
return;
}
pushdown(index, start, end);
ll mid = (start + end) / 2;
update(start, mid, 2 * index, left, right, u);
update(mid + 1, end, 2 * index + 1, left, right, u);
tree[index].merge(tree[2 * index], tree[2 * index + 1]);
}
Node query(ll start, ll end, ll index, ll left, ll right) { // Never change this
if (start > right || end < left)
return Node();
if (start >= left && end <= right){
pushdown(index, start, end);
return tree[index];
}
pushdown(index, start, end);
ll mid = (start + end) / 2;
Node l, r, ans;
l = query(start, mid, 2 * index, left, right);
r = query(mid + 1, end, 2 * index + 1, left, right);
ans.merge(l, r);
return ans;
}
void make_update(ll left, ll right, ll val, bool flag) { // pass in as many parameters as required
Update new_update = Update(val, flag); // may change
update(0, n - 1, 1, left, right, new_update);
}
Node make_query(ll left, ll right) {
return query(0, n - 1, 1, left, right);
}
};
struct Node1 {
ll val; // may change
Node1() { // Identity element
val = 0; // may change
}
Node1(ll p1) { // Actual Node
val = p1; // may change
}
void merge(Node1 &l, Node1 &r) { // Merge two child nodes
val = l.val + r.val; // may change
}
};
struct Update1 {
ll val; // may change
bool set;
Update1(){ // Identity update
val = 0;
set = false;
}
Update1(ll val1,bool flag) { // Actual Update
val = val1;
set = flag;
}
void apply(Node1 &a, ll start, ll end) { // apply update to given node
a.val = (set ? val * (end - start + 1) : a.val + val * (end - start + 1)); // may change
}
void combine(Update1& new_update, ll start, ll end){
val = (new_update.set ? new_update.val : val + new_update.val);
set = new_update.set;
}
};
void solve(){
ll n;cin>>n;ll q;cin>>q;
vector<ll> a(n,0);
LazySGT<Node1,Update1> seg=LazySGT<Node1,Update1> (n, a);
while(q--){
ll typ;cin>>typ;
if(typ==1){
ll l,r,v;cin>>l>>r>>v;r--;
seg.make_update(l,r,v,1);
}else if(typ==2){
ll l,r,v;cin>>l>>r>>v;r--;
seg.make_update(l,r,v,0);
}else{
ll l,r;cin>>l>>r;r--;
cout<<seg.make_query(l,r).val<<endl;
}
}
}