Simple Treap

build.cpp

	function<void(shared_ptr<node>&&)> dfs=[&](shared_ptr<node>&& p) {
		if(p->l) p->push(p->l), dfs(move(p->l));
		A[M++]=p->x;
		if(p->r) p->push(p->r), dfs(move(p->r));
	};
	function<shared_ptr<node>(int, int)> build=[&](int l, int r) {
		int m=(l+r)>>1;
		auto p=node::New(A[m]);
		if(l<m) p->l=build(l, m-1);
		if(m<r) p->r=build(m+1, r);
		p->up();
		return p;
	};

treap.cpp

#include <bits/stdc++.h>
#define r(N) for(int i=0; i<N; i++)
using namespace std;
using ll=long long;
using u32=uint32_t;
using u64=uint64_t;

u32 rng() {
	static u64 g=random_device{}();
	u32 x=(g>>18^g)>>27, r=g>>59;
	g=g*0x5851F42D4C957F2D+0x14057B7EF767814F;
	return x>>r|x<<(-r&31);
}
inline u32 random(u32 const n) {
	u64 m=u64(rng())*n;
	if(u32(m)<n) while(u32(m)<u32(-n)%n) m=u64(rng())*n;
	return m>>32;
}

template<class T>
struct TreapNode {
	#define self (*static_cast<T*>(this))
	shared_ptr<T> l, r;
	void down() {
		if(l) self.push(l);
		if(r) self.push(r);
		self.refresh();
	}
	void up() {
		self.init();
		if(l) self.pull(*l, self);
		if(r) self.pull(self, *r);
	}
	#undef self
};
template<class T, class V, size_t n>
auto split(shared_ptr<T>& v, const V(&K)[n]) {
	array<shared_ptr<T>, n+1> P;
	array<shared_ptr<T>*, n+1> Q;
	for(int i=0; i<=n; i++) Q[i]=&P[i];
	function<void(int, int, V)> f=[&](int l, int r, V k) {
		if(l==r) { *Q[l]=v; return; }
#if 1
		int m=l;
		while(m<r && K[m]<=k+v->key()) m++;
#else
		int m=upper_bound(K+l, K+r, k+v->key())-K;
#endif
		auto&u=*Q[m];
		u=move(v);
		u->down();
		if((v=move(u->r))) Q[m]=&u->r, f(m, r, k+u->key());
		if((v=move(u->l))) Q[m]=&u->l, f(l, m, k);
		u->up();
	};
	f(0, n, V{});
	return P;
}
template<class T, size_t n>
auto concat(array<shared_ptr<T>, n>& P) {
	function<shared_ptr<T>(int, int)> f=[&](int l, int r) {
		int m=l, sz=0;
		#pragma unroll 5
		for(int i=l; i<=r; i++) if(P[i]) sz+=P[i]->size();
		shared_ptr<T> v;
		if(!sz) return v;
		int k=random(sz);
		#pragma unroll 5
		while(!P[m] || (k-=P[m]->size())>=0) m++;
		v=move(P[m]);
		if(sz==v->size()) return v;
		v->down();
		if(m!=r) P[m]=move(v->r), v->r=f(m, r);
		if(l!=m) P[m]=move(v->l), v->l=f(l, m);
		v->up();
		return v;
	};
	return f(0, n-1);
}

struct node : TreapNode<node> {
	static inline shared_ptr<node> New(int x=0) {
		auto v=make_shared<node>();
		v->x=x; v->init(); v->refresh();
		return v;
	}

	int sz, cp;
	ll lz, x, sum;
	inline auto key() const { return l ? l->sz+1 : 1; }
	inline auto size() const { return sz; }
	inline void init() { sz=1, sum=x; }
	inline void pull(node& a, node& b) {
		sz=a.sz+b.sz;
		sum=a.sum+b.sum;
	}
	inline void push(shared_ptr<node>& p) {
		if(cp) {
			if(p.use_count()>1) p=make_shared<node>(*p);
			p->cp=1;
		}
		if(lz) {
			p->lz+=lz;
			p->x+=lz;
			p->sum+=p->sz*lz;
		}
	}
	inline void refresh() { cp=lz=0; }
	inline void copyTo(shared_ptr<node>& p) {
		cp=1;
		p=make_shared<node>(*this);
	}
};
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N;
	cin>>N;
	shared_ptr<node> root;
{
	array<shared_ptr<node>, 2> P;
	P[0]=move(root);
	r(N) {
		int x;
		cin>>x;
		P[1]=node::New(x);
		P[0]=concat(P);
	}
	root=move(P[0]);
}
	int Q;
	cin>>Q;
	r(Q) {
		char type;
		int l, r;
		cin>>type>>l>>r;
		shared_ptr<node> root2;
		if(type=='2') root->copyTo(root2);
		auto t=split(root, {l, r+1});
		if(type=='1') {
			int x;
			cin>>x;
			if(t[1]) {
				t[1]->sum+=x*ll(t[1]->sz);
				t[1]->x+=x;
				t[1]->lz+=x;
			}
		} else if(type=='2') {
			int s, e;
			cin>>s>>e;
			auto t2=split(root2, {s, e+1});
			t[1]=t2[1];
		} else if(type=='3') {
			cout<<(t[1] ? t[1]->sum : 0)<<'\n';
		}
		root=concat(t);
	}
}