Treap 模板(lazy tag)

http://poj.org/problem?id=3468

http://judge.ioicamp.org/problems/23

要小心的push部分XDDD

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

typedef long long LL;

struct Treap {
Treap *lc;
Treap *rc;
LL val,pri,key;
LL tag;
LL sum;
int son;  //include 自己
Treap(LL _val,LL _key) {
val=_val;
key=_key;
sum=_val;
pri=rand();
tag=0;
son=1;
lc = rc = NULL;
}
};

LL sm(Treap* t) {
return t? t->sum : 0;
}

int sn(Treap* t) {
return t? t->son : 0;
}

void pull(Treap* t) {
t->sum = sm(t->lc) + sm(t->rc) + t->val;
t->son = sn(t->lc) + sn(t->rc) + 1;
}

void push(Treap* t) {
if (t->tag==0) return;
t->val += t->tag;
t->sum += t->tag;
if (t->lc) {
t->lc->tag += t->tag;
t->lc->sum += t->tag * (sn(t->lc));
}
if (t->rc) {
t->rc->tag += t->tag;
t->rc->sum += t->tag * (sn(t->rc));
}
t->tag = 0;
}

Treap* merge(Treap *a,Treap *b) {
if (!a || !b) return a?a:b;
if (a->pri > b->pri) {
push(a);
a->rc=merge(a->rc,b);
pull(a);
return a;
}
else {
push(b);
b->lc=merge(a,b->lc);
pull(b);
return b;
}
}

void split(Treap* t, int x,Treap* &a, Treap* &b) {
if (!t) a = b = NULL;
else if (t->key<=x) {
a=t;
push(a);
split(t->rc,x,a->rc,b);
pull(a);
}
else {
b=t;
push(b);
split(t->lc,x,a,b->lc);
pull(b);
}
}

LL query(Treap *t,int l,int r) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
LL ret=sm(t);
t=merge(merge(tl,t),tr);
return ret;
}

void modify(Treap* t,int l,int r,LL v) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
t->tag += v;
t->sum += v * sn(t); //沒加自己!!!
t=merge(merge(tl,t),tr);
}

int main () {
srand(time(NULL));
int T;
scanf("%d",&T);
while (T--) {
Treap* root;
root=NULL;
int n,q,i;
scanf("%d %d",&n,&q);
for (int x=1;n>=x;x++) {
scanf("%d",&i);
root=merge(root,new Treap(i,x));
// cout<<"sum = "<<root->sum<<endl;
// cout<<"val = "<<root->val<<endl;
}
while (q--) {
string d;
cin >> d;
if (d=="query") {
int i,j;
scanf("%d %d",&i,&j);
printf("%lld\n",query(root,i,j));
}
else if (d=="add"){
int i,j,k;
scanf("%d %d %d",&i,&j,&k);
modify(root,i,j,k);
}
}
// cout<<"List : ";
// for (int x=1;n>=x;x++) cout<<query(root,x,x)<<' ';
// cout<<endl;
}
}