(SPOJ) GSS3 - Can you answer these queries III

http://www.spoj.com/problems/GSS3/

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

typedef long long LL;
const LL INF = 1e15 + 6;

struct Treap {
    Treap *lc,*rc;
    LL val;
    LL key;
    LL lmax,rmax,midmax,sum;
    int pri;
    Treap(LL _key,LL _val) {
        lc=rc=NULL;
        pri = rand();
        lmax=rmax=midmax=sum=val=_val;
        key = _key;
    }
};

LL Lmax(Treap* t) {
    return t?t->lmax:-INF;
}

LL Rmax(Treap* t) {
    return t?t->rmax:-INF;
}

LL Midmax(Treap* t) {
    return t?t->midmax:-INF;
}

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

void pull(Treap* t) {
    t->sum = Sum(t->lc) + Sum(t->rc) + t->val;
    t->lmax = max(max(Lmax(t->lc),Sum(t->lc)+t->val),Sum(t->lc)+t->val+Lmax(t->rc));
    t->rmax = max(max(Rmax(t->rc),Sum(t->rc)+t->val),Sum(t->rc)+t->val+Rmax(t->lc));
    t->midmax = max(max(max(Midmax(t->lc),Midmax(t->rc)),t->val),max(max(Rmax(t->lc)+t->val,Lmax(t->rc)+t->val),Lmax(t->rc)+Rmax(t->lc)+t->val));
}

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

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

const int MAX_N = 5e4 + 6;

LL a[MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        Treap* root;
        root=NULL;
        for (int i=1;n>=i;i++) {
            scanf("%lld",&a[i]);
            root = merge(root,new Treap(i,a[i]));
        }
        int m;
        scanf("%d",&m);
        while (m--) {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            if (a==0) {
                Treap *tl,*tr;
                split(root,b-1,tl,root);
                split(root,b,root,tr);
                root = merge(merge(tl,new Treap(b,c)),tr);
            }
            else {
                Treap *tl,*tr;
                split(root,b-1,tl,root);
                split(root,c,root,tr);
                printf("%lld\n",root->midmax);
                root=merge(merge(tl,root),tr);
            }
        }
    }
}