Can someone please help me debug my code or at least figure out a test case which gives a WA.
Link: SPOJ.com - Problem HORRIBLE
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct segment_tree{
// 0 indexing
ll n;
ll *lazy;
ll *tree;
ll op;
segment_tree(ll n,ll op,ll *array){
this->n=n;
ll size=4*n;
this->tree=new ll [size];
this->lazy=new ll [size];
this->op=op;
for(ll i=0;i<size;i++)
lazy[i]=0;
build_tree(array);
}
ll operation(ll a, ll b){
if(op==1){
return a+b;
}
if(op==2){
return a^b;
}
if(op==3){
return (a<b)?a:b;
}
}
void build_tree(ll array[],ll curr=0,ll rs=0,ll re=-1){
if(re==-1)
re=this->n-1;
if(rs==re){
tree[curr]=array[rs];
return;
}
ll mid=(rs+re)>>1;
build_tree(array,(curr<<1)+1,rs,mid);
build_tree(array,(curr<<1)+2,mid+1,re);
tree[curr]=operation(tree[(curr<<1)+1],tree[(curr<<1)+2]);
//cout<<curr<<" "<<tree[curr]<<endl;
return;
}
ll get(ll qs,ll qe,ll curr=0,ll ss=0,ll se=-1){
if(se==-1)
se=this->n-1;
if(lazy[curr]!=0){
tree[curr]=tree[curr]+lazy[curr]*(se-ss+1);
if(ss!=se){
lazy[(curr<<1)+1]=lazy[curr];
lazy[(curr<<1)+2]=lazy[curr];
}
lazy[curr]=0;
}
if(ss==qs && se==qe){
return tree[curr];
}
ll mid=(ss+se)>>1;
if(qe<=mid){
return get(qs,qe,(curr<<1)+1,ss,mid);
}
if(qs>mid){
return get(qs,qe,(curr<<1)+2,mid+1,se);
}
return operation(get(qs,mid,(curr<<1)+1,ss,mid),get(mid+1,qe,(curr<<1)+2,mid+1,se));
}
void update(ll us,ll ue,ll u,ll curr=0,ll ss=0,ll se=-1){
if(se==-1)
se=this->n-1;
if(ss>se)
return;
if(lazy[curr]!=0){
tree[curr]=tree[curr]+lazy[curr]*(se-ss+1);
if(ss!=se){
lazy[(curr<<1)+1]=lazy[curr];
lazy[(curr<<1)+2]=lazy[curr];
}
lazy[curr]=0;
}
if(us>se || ue<ss){
return;
}
if(us<=ss && se<=ue){
if(ss!=se){
lazy[(curr<<1)+1]+=u;
lazy[(curr<<1)+2]+=u;
}
tree[curr]=tree[curr]+u*(se-ss+1);
return;
}
ll mid=(ss+se)/2;
update(us,ue,u,(curr<<1)+1,ss,mid);
update(us,ue,u,(curr<<1)+2,mid+1,se);
tree[curr]=tree[(curr<<1)+1]+tree[(curr<<1)+2];
return;
}
};
typedef segment_tree segtree;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--){
ll n,c;
cin>>n>>c;
ll a[n];
for(ll i=0;i<n;i++){
a[i]=0;
}
segtree seg(n,1,a);
while(c--){
ll x;
cin>>x;
if(x==0){
ll p,q,v;
cin>>p>>q>>v;
seg.update(p-1,q-1,v);
}
else{
ll p,q;
cin>>p>>q;
cout<<seg.get(p-1,q-1)<<endl;
}
}
}
return 0;
}