splay版本

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 500010, INF = 1e9;
int root, w[N], idx;
struct Node{
    int s[2], v, p;
    int ms, ls, rs, sum;
    int siz;
    void init(int _v,int _p)
    {
        v = _v, p = _p;
        s[0] = s[1] = 0;
        ms = sum = v;
        siz = 1;
        ls = rs = max(v, 0);
    }
}t[N << 4];
void pushup(int x)
{
    auto &u = t[x], &l = t[u.s[0]], &r = t[u.s[1]];
    u.siz = l.siz + r.siz + 1;
    u.sum = l.sum + r.sum + u.v;
    u.ls = max(l.ls, l.sum + u.v + r.ls);
    u.rs = max(r.rs, r.sum + u.v + l.rs);
    u.ms = max(max(l.ms, r.ms), l.rs + u.v + r.ls);
}
int build(int l,int r,int p)
{
    int mid = l + r >> 1;
    int u = ++ idx;
    t[u].init(w[mid], p);
    if(l < mid) t[u].s[0] = build(l, mid - 1, u);
    if(r > mid) t[u].s[1] = build(mid + 1, r, u);
    pushup(u);
    return u;
}
void rotate(int x)
{
    int y = t[x].p, z = t[y].p, k = t[y].s[1] == x;
    t[z].s[t[z].s[1] == y] = x, t[x].p = z;
    t[y].s[k] = t[x].s[k ^ 1], t[t[x].s[k ^ 1]].p = y;
    t[x].s[k ^ 1] = y, t[y].p = x;
    pushup(y), pushup(x);
}
void splay(int x,int k)
{
    while(t[x].p != k)
    {
        int y = t[x].p, z = t[y].p;
        if(z != k)
            if((t[z].s[1] == y) ^ (t[y].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if(!k) root = x;
}
int get_k(int siz)
{
    int u = root;
    while(u)
    {
        if(t[t[u].s[0]].siz >= siz) u = t[u].s[0];
        else if(t[t[u].s[0]].siz + 1 == siz) return u;
        else siz -= t[t[u].s[0]].siz + 1, u = t[u].s[1];
    }
    return -1;
}
int main()
{
    int n, m; scanf("%d%d", &n, &m);
    t[0].ms = -1e4;
    w[0] = w[n + 1] = -INF;
    for(int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
    root = build(0, n + 1, 0);
    while(m --)
    {
        int op, l, r; scanf("%d%d%d", &op, &l, &r);
        if(op == 1)
        {
            if(l > r) swap(l, r);
            l = get_k(l), r = get_k(r + 2);
            splay(l, 0); splay(r, l);
            printf("%d\n", t[t[r].s[0]].ms);
        }
        else{
            l = get_k(l + 1);
            t[l].v = r;
            while(l != 0)
            {
                pushup(l);
                l = t[l].p;
            }
        }

    }
    return 0;
}