Looks like you got WA because of the %lld modifier. It's very unreliable. I replaced it with %I64d and now you get TLE, which is the same I got when I tried to solve the problem...

Alright.

After learning about lazy propagation, which is new to me, re-coding most of my routines and extensively debugging my code, I managed to get AC with a total runtime of over 8 seconds. Yeah, terribly slow, though it's mainly because of the use of iostream (I couldn't get it accepted using stdio (it's terribly unreliable when it comes to 64-bit integers)).

The first error I see in your code is in the update routine. You have if(i==left && j==right){...}. If the case is that i < left, and then you go to the left child, you call update with parameters L, left, mid, i, mid, v. So i will still be < left, and that subroutine will be skipped. I would replace the logic behind that routine to always let static the values of i and j, and when left >= i && right <= j, update the values of the node and return. And if at any time, left > j || right < i, return.

The same applies to the query routine.

I also changed the update of T[Node].total. As I understood it, lazy propagation works as follows:

• When you reach the final node of the update routine, you add v to its children's add (T[L].add and T[R].add), and do nothing more.
• If when you run a query routine, you come across a node with a value of add > 0, you update its total value accordingly, mark its children as needed to be updated (you set T[L].add += T[Node].add, and the same for the right child) and finally set T[Node].add = 0.

I also changed the left and right values of the node. In your code, you dynamically assigned ranges to nodes, and built your tree with a random value of 10^5 * 3. It's always better to build a tree with size 2^x. That way, you'll know that every node has 2 children, and that the range of the first node will be 1 — size / 2.

With those modifications, and a little debugging, your code got accepted too.

Here's the modified version...

#include<iostream>

#define MAX 262145

using namespace std;

typedef long long LL;
LL n,m;
struct tree{
LL add;
LL total;
}T[MAX];

void update(LL Node,LL left,LL right,LL i,LL j,LL v){
    if(left > j || right < i) return;
	if(left >= i && right <= j){
	    if(left != right){
            LL L = Node<<1 , R = L+1;
            T[L].add += v;
            T[R].add += v;
	    }

		T[Node].total += (right-left+1)*v;
		return;
	}

	LL mid=(left + right)>>1, L = Node<<1 , R = L+1;
    update(L,left,mid,i,j,v);
    update(R,mid+1,right,i,j,v);
	T[Node].total += v*(min(right, j)-max(left, i)+1);
}

LL query(LL Node,LL left,LL right,LL i,LL j){
    if(left > j || right < i) return 0;

    if(T[Node].add > 0){
        if(left != right){
            LL L = Node<<1 , R = L+1;
            T[L].add += T[Node].add;
            T[R].add += T[Node].add;
	    }

        T[Node].total += T[Node].add*(right-left+1);
        T[Node].add = 0;
    }

    if(left >= i && right <= j)return T[Node].total;

    LL mid = (right+left)/2, L = Node<<1 , R = L+1;
    LL ret =0;
    ret+= query(L,left,mid,i,j);
    ret+= query(R,mid+1,right,i,j);
    return ret;
}

int main(){
LL t;
cin >> t;
while(t--){
cin >> n >> m;
	for(LL i=0;i<MAX;i++)
		T[i].total = T[i].add = 0;
while(m--){
	LL q,a,b,k;
	cin >> q >> a >> b;
		switch(q){
			case 0:cin >> k;
				update(1,1,MAX/2,a,b,k);break;
			case 1:cout << query(1,1,MAX/2,a,b) << endl;break;
		}
}
}
return 0;
}

Getting WA, anyone can help out?

#include <cstdio>
#include <cstring>

using namespace std;

long long st[400000];
long long lazy[400000];
int n;

void update(int i, int j, int value, int L=0, int R=n-1, int p=1)
{
    if(lazy[p])
    {
        if(L!=R)
        {
            lazy[p*2]+=lazy[p];
            lazy[p*2+1]+=lazy[p];
        }
        st[p]+=lazy[p]*(R-L+1);
        lazy[p]=0;
    }
    if(i>R || j<L)
        return;
    if(i<=L && j>=R)
    {
        st[p]+=(long long)(R-L+1)*value;
        if(L!=R)
        {
            lazy[p*2]+=value;
            lazy[p*2+1]+=value;
        }
    }
    else
    {
        update(i,j,value,L,(L+R)/2,p*2);
        update(i,j,value,(L+R)/2+1,R,p*2+1);
        st[p]=st[p*2]+st[p*2+1];
    }
}

long long query(int i, int j, int L=0, int R=n-1, int p=1)
{
    if(lazy[p])
    {
        if(L!=R)
        {
            lazy[p*2]+=lazy[p];
            lazy[p*2+1]+=lazy[p];
        }
        st[p]+=lazy[p]*(R-L+1);
        lazy[p]=0;
    }
    if(i>R || j<L)
        return 0;
    if(i<=L && j>=R)
        return st[p];
    return query(i,j,L,(L+R)/2,p*2)+query(i,j,(L+R)/2+1,R,p*2+1);
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int q,a,b,c;
        scanf("%d%d",&n,&q);
        memset(lazy,0,sizeof(lazy));
        memset(st,0,sizeof(st));
        while(q--)
        {
            scanf("%d",&a);
            if(a==1)
            {
                scanf("%d%d",&a,&b);
                printf("%I64d\n",query(--a,--b));
            }
            else
            {
                scanf("%d%d%d",&a,&b,&c);
                update(--a,--b,c);
            }
        }
    }
}

I am trying to solve the same problem, using optimized version of ST + LP.

I have tried so many test cases, with boundary cases, all are giving correct answer, I am still getting WA though:

Below is my code, any hint?

#include <cstring>
#include <iostream>
using namespace std;

typedef long long ll;

const int N = 1e5;  // limit for array size
ll n, h;  // array size
ll t[2 * N];
ll d[N];


void apply(int p, int value, int k) {
    t[p] += value * k;
    if (p < n) d[p] += value;
}


void build(int p) {
    int k = 1;
    while (p > 1) {
        p >>= 1;
        k <<= 1;
        t[p] = t[p<<1] + t[p<<1|1] + k * d[p];
    }
}

void push(int p) {
    for (int s = h; s > 0; --s) {
        int i = p >> s;
        if (d[i] != 0) {
            apply(i<<1, d[i], s);
            apply(i<<1|1, d[i], s);
            d[i] = 0;
        }
    }
}


void inc(int l, int r, int value) {
    l += n, r += n;
    int l0 = l, r0 = r;
    int k = 1;
    for (; l <= r; l >>= 1, r >>= 1, k <<= 1) {
        if (l & 1)      apply(l++, value, k);
        if (r % 2 == 0) apply(r--, value, k);
    }
    build(l0);
    build(r0);
}

ll query(int l, int r) {
    l += n, r += n;
    push(l);
    push(r);
    ll res = 0;
    for (; l <= r; l >>= 1, r >>= 1) {
        if (l & 1)      res += t[l++];
        if (r % 2 == 0) res += t[r--];
    }
    return res;
}



int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll T, C, p, q, v, o;
    
    cin >> T;
    
    for(int i = 0; i < T; i++) {

        cin >> n >> C;
        
        h = sizeof(int) * 8 - __builtin_clz(n);
        
        memset(t, 0, sizeof(t));
        memset(d, 0, sizeof(d));
        
        for(int j = 0; j < C; j++) {
            cin >> o >> p >> q;
            if(o == 0) {
                cin >> v;
                inc(p - 1, q - 1, v);
            } else {
                cout << query(p - 1, q - 1) << '\n';
            }
        }
    }
    return 0;
}