学习了下Splay，发现原来学的都是错的（迷

学了下正确的姿势:http://wenku.baidu.com/link?url=scHbokjqF7nK8kca00Pxrm8uaUmm7HNkgXLGaq0tNU-9T2zOrc08oZ7YJkXagD-Q2FVpZ89uxjStXco_8zK5T83Bwx2XXhBjbtAK6dxGMoW

（发完链接就贴代码系列）

#include <stdio.h>
#include <iostream>
using namespace std;

#define Max 200010 
#define B ch[ch[root][1]][0] 
int ch[Max][2],fa[Max],root,o[Max],sz[Max],n;
long long sum[Max],tag[Max],val[Max],an;
void pushdown(int x) {
	if (!x || !tag[x]) return;
	val[x]+=tag[x];
	if(ch[x][0]) tag[ch[x][0]]+=tag[x],sum[ch[x][0]]+=tag[x]*sz[ch[x][0]];
	if(ch[x][1]) tag[ch[x][1]]+=tag[x],sum[ch[x][1]]+=tag[x]*sz[ch[x][1]];
	tag[x]=0;
}
void update(int x) {
    if(!x) return ;
	sz[x]=1+sz[ch[x][0]]+sz[ch[x][1]];
	sum[x]=val[x]+sum[ch[x][0]]+sum[ch[x][1]];
}
void rotate(int x) {
	if(!fa[x]) return;
	int y=fa[x],p=ch[y][0]==x;
	pushdown(y);
	pushdown(x);
	int b=ch[x][p];ch[y][p^1]=b;
	if(b) fa[b]=y;
	fa[x]=fa[y];
	if(fa[y]) ch[fa[y]][ch[fa[y]][1]==y]=x;
	ch[x][p]=y;fa[y]=x;
	update(y);
	if(y==root) root=x;
}

void splayy(int x,int f) {
	pushdown(x);
	while(fa[x]!=f) {
		if(fa[fa[x]]!=f) {
			int y=fa[x];
			if((ch[y][0]==x)^(ch[fa[y]][0]==y)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
	update(x);
	if(!f) root=x;
}
void splayk(int k,int f) {
	int x=root;pushdown(x);
	while(sz[ch[x][0]]!=k-1) {
		if(sz[ch[x][0]]<k) {
			k-=sz[ch[x][0]]+1;
			x=ch[x][1];
		} else x=ch[x][0];
		pushdown(x);
	}
	splayy(x,f);
}
void addnode(int &ad,int f,int x) {
	ad=++an;sz[ad]=1,fa[ad]=f,val[ad]=sum[ad]=x;
}
void build(int &ad,int f,int l,int r) {
	if(l>r) {ad=0;return;}
	int mid=l+r>>1;
	addnode(ad,f,o[mid]);
	build(ch[ad][0],ad,l,mid-1);
	build(ch[ad][1],ad,mid+1,r);
	update(ad);
}
void init() {
	an=0;
	addnode(root,0,0);
	addnode(ch[root][1],root,0);
	update(root);
	build(B,ch[root][1],1,n);
	update(ch[root][1]);
	update(root);
}
void getlr(int l,int r) {
	splayk(l,0);
	splayk(r+2,root);
}
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		scanf("%d",&o[i]);
	init();
	int Q;char buf[123];int a,b,c;scanf("%d",&Q);
	while(Q--) {
		scanf("%s",buf);
		if(buf[0]=='2') {
			scanf("%d%d",&a,&b);
			getlr(a,b);
			printf("%lld\n",sum[B]);
		} else {
			scanf("%d%d%d",&a,&b,&c);
			getlr(a,b);
			tag[B]+=c;
			sum[B]+=(long long)sz[B]*c;
		}
	}	
}