题目链接：http://poj.org/problem?id=3468
这题是线段树的题，拿来学习treap。
不旋转的treap。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <numeric>
#include <iterator>
#include <iostream>
#include <cstdlib>
#include <functional>
#include <queue>
#include <stack>
#include <list>
#include <ctime>
using namespace std; const int inf = ~0U >> ; typedef long long LL; struct TreapNode{
int id,sz,key;
LL val,sum,delta;
TreapNode* ch[];
TreapNode(): key(rand()),sz(),id(),val(),sum(),delta() {ch[]=ch[]=NULL;}
void rz(){
sz = ;
sum = val;
if(ch[]) { sz+=ch[]->sz; sum+=ch[]->sum; }
if(ch[]) { sz+=ch[]->sz; sum+=ch[]->sum; }
}
void pd(){
if(delta){
if(ch[]) {
ch[]->delta+=delta;
ch[]->val+=delta;
ch[]->sum+=delta*ch[]->sz;
}
if(ch[]) {
ch[]->delta+=delta;
ch[]->val+=delta;
ch[]->sum+=delta*ch[]->sz;
}
delta = ;
}
}
~TreapNode(){
if(ch[]) delete ch[];
if(ch[]) delete ch[];
}
}; typedef pair<TreapNode*,TreapNode*> DTreap; TreapNode* Merge(TreapNode* A,TreapNode* B) {
if(!A) return B;
if(!B) return A;
A->pd();B->pd();
if(A->key<B->key) {
A->ch[] = Merge(A->ch[],B);
A->rz();
return A;
} else {
B->ch[] = Merge(A,B->ch[]);
B->rz();
return B;
}
} DTreap Split(TreapNode* rt,int id) {
if(!rt) return DTreap(NULL,NULL);
DTreap ret;
rt->pd();
if(rt->id>id) {
ret = Split(rt->ch[],id);
rt->ch[] = ret.second;
ret.second = rt;
rt->rz();
return ret;
} else {
ret = Split(rt->ch[],id);
rt->ch[] = ret.first;
ret.first = rt;
rt->rz();
return ret;
}
} void Insert(TreapNode*& rt,int id,LL val) {
DTreap dt = Split(rt,id-);
TreapNode* lch = dt.first;
TreapNode* rch = dt.second;
TreapNode* nd = new TreapNode;
nd->id = id;
nd->val = val;
nd->sum = val;
lch = Merge(lch,nd);
rt = Merge(lch,rch);
} void AddInterval(TreapNode*& rt,int l,int r,LL val) {
if(!rt) return;
DTreap dt = Split(rt,l-);
TreapNode* lch = dt.first;
dt = Split(dt.second,r);
TreapNode* mid = dt.first;
TreapNode* rch = dt.second;
if(mid){
mid->val += val;
mid->sum += val*mid->sz;
mid->delta += val;
}
lch = Merge(lch,mid);
rt = Merge(lch,rch);
} LL QueryInterval(TreapNode*& rt,int l,int r) {
if(!rt) return ;
LL ret = ;
DTreap dt = Split(rt,l-);
TreapNode* lch = dt.first;
dt = Split(dt.second,r);
TreapNode* mid = dt.first;
TreapNode* rch = dt.second;
if(mid) ret = mid->sum;
lch = Merge(lch,mid);
rt = Merge(lch,rch);
return ret;
} int n,m;
LL val;
char cmd[]; int main() {
srand(time(NULL));
while(~scanf("%d%d",&n,&m)) {
TreapNode* root = NULL;
for(int i = ; i < n ; i++ ) {
scanf("%lld",&val);
Insert(root,i+,val);
}
for(int i = ; i < m ; i++ ) {
scanf("%s",cmd);
if(cmd[] == 'Q' ) {
int l,r;
scanf("%d%d",&l,&r);
printf("%lld\n",QueryInterval(root,l,r));
} else {
int l,r;
LL val;
scanf("%d%d%lld",&l,&r,&val);
AddInterval(root,l,r,val);
}
}
if(root) delete root;
}
return ;
}