split_example_spoj_horrible.cpp

#include"segment_tree.cpp"
#include"stdio.h"
#include"algorithm"
struct node{
  long long add,sum;
	int numleaves;
	void merge(node& l, node& r){
		add=0;
		sum = l.sum + r.sum;
		numleaves = l.numleaves + r.numleaves;
	}
	void split(node& l, node& r){
		l.add+=add,r.add+=add;
		l.sum+=add*l.numleaves;
		r.sum+=add*r.numleaves;
		add=0;
	}
};
int v;
void inc_by_v(node& n){
	n.add+=v;
	n.sum+=v*(long long)n.numleaves;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int N,q;
		scanf("%d%d",&N,&q);
		node array[N];
		for(int i=0;i<N;i++)
			array[i].add=array[i].sum=0,
			array[i].numleaves=1;
		node identity;
		identity.add=identity.sum=identity.numleaves=0;
		segtree<node> s;
		s.init(N,array,identity);
		while(q--){
			int t,a,b;
			scanf("%d%d%d",&t,&a,&b);
			if(a>b)std::swap(a,b);
			a--,b--;
			if(t==0)
				scanf("%d",&v),
				s.update<&inc_by_v>(a,b);
			else
				printf("%Ld\n",s.query(a,b).sum);
		}
	}
}