弄完了一个版本感觉还行
https://github.com/lychees/last-weapon/commit/58976a70bc0948c2073091c6cf2966a16e352127

目前例题用的是 GSS 系列。。。

不过 GSS3 这个题和 GSS1 一样都卡代码长度。。需要删点东西。。
GSS6 倒是很适合。。。

#include <lastweapon/segtree>
using namespace lastweapon;

struct rec{
    int ss, ls, rs, ms;
    rec(int s = 0) {
        ss = ls = rs = ms = s;
    }
};

rec e() {
    rec z = rec(-INF);
    z.ss = 0;
    return z;
}

rec op(const rec l, const rec r) {
    rec z;
    z.ss = l.ss + r.ss;
    z.ls = max(l.ls, l.ss + r.ls);
    z.rs = max(r.rs, l.rs + r.ss);
    z.ms = max({l.ms, r.ms, l.rs + r.ls});
    return z;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int n; RD(n); vector<rec> a(n); REP(i, n) a[i] = rec(RD());
    segtree<rec, op, e> T(a);

    Rush {
        if (RD()) { // query
            int l, r; RD(l, r); --l;
            cout << T.prod(l, r).ms << endl;
        } else { // modify
            int x, y; RD(x, y); --x;
            T.set(x, rec(y));
        }
    }
}

#include <lastweapon/splay>

struct rec{
    int ky, ss, ls, rs, ms;
    rec(int s = 0) {
        ky = ss = ls = rs = ms = s;
    }
};

rec e() {
    rec z = rec(-INF);
    z.ss = 0;
    return z;
}

void op(rec& x, const rec l, const rec r) {
    x.ss = l.ss + x.ky + r.ss;
    x.ls = max(l.ls, l.ss + x.ky + max(0, r.ls));
    x.rs = max(r.rs, max(0, l.rs) + x.ky + r.ss);
    x.ms = max({l.ms, max(l.rs, 0) + x.ky + max(0, r.ls), r.ms});
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int n; RD(n); vector<rec> a(n); REP(i, n) a[i] = rec(RD());
    lastweapon::splay::splay<rec, op, e> T(a);

    Rush {
        if (RD()) { // query
            int l, r; RD(l, r); ++r;
            cout << T.prod(l, r).ms << endl;
        } else { // modify
            int x, y; RD(x, y);
            T.set(x, rec(y));
        }
    }
}

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

using namespace std;

#define REP(i, n) for (int i=0;i<int(n);++i)
#define Rush for(int ____T=RD(); ____T--;)

const int INF = 0x3f3f3f3f;

template<class T> inline void RD(T &);
template<class T> inline void OT(const T &);
inline int RD(){ int x; RD(x); return x;}
template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}

template<class T> inline void RD(T &x){
    scanf("%d", &x);
}

template<class T> inline void OT(const T &x){
    printf("%d\n", x);
}

/* .................................................................................................................................. */


namespace lastweapon {

namespace splay {

template <class S, void (*op)(S&, const S, const S), S (*e)()>
struct node {

    static node *NIL; node *c[2], *p;
    int sz; S d;

#define NIL node::NIL
#define l c[0]
#define r c[1]
#define lx x->l
#define rx x->r
#define px x->p
#define ly y->l
#define ry y->r
#define py y->p

    node() {
        d=e();
    }

    inline void reset(S s){l=r=p=NIL,d=s;sz=1;}

    inline void upd(){
        sz = l->sz + 1 + r->sz;
        op(d, l->d, r->d);
    }
    inline int sgn(){return p->r==this;}
    inline void setc(int d,node*x){c[d]=x,px=this;}
    inline void setl(node*x){setc(0,x);}
    inline void setr(node*x){setc(1,x);}

    inline void rot(int d){
        node*y=p,*z=py;z->setc(y->sgn(),this);
        y->setc(d,c[!d]),setc(!d,y),y->upd();
    }
    inline void rot(){rot(sgn());}
    inline node*splay(node*t){
        int a,b;while(p!=t){
            if (p->p==t){rot();break;}
            else a=sgn(),b=p->sgn(),(a^b?this:p)->rot(a),rot(b);
        }
        upd();
        return this;
    }
};


#undef NIL

template <class S, void (*op)(S&, const S, const S), S (*e)()>
node<S, op, e> *node<S, op, e>::NIL = new node<S, op, e>;


template <class S, void (*op)(S&, const S, const S), S (*e)()> struct splay {

    using nod = node<S, op, e>;

    std::vector<nod> d;
    int n; nod* rt;

    splay() : splay(0) {}
    explicit splay(int n) : splay(std::vector<S>(n, e())) {}
    explicit splay(const std::vector<S>& a) : n(int(a.size())) {
        rt = new nod(); rt->reset(0);
        REP(i, n) {
            nod* t = new nod();
            t->reset(a[i]);
            t->setl(rt); t->upd();
            rt = t;
        }
        nod* t = new nod();
        t->reset(0);
        t->setl(rt); t->upd();
        rt = t;
    }

    nod *select(int k, nod*t=nod::NIL){
        nod *x = rt; while (lx->sz != k){
            if (k < lx->sz) x = lx;
            else k -= lx->sz+1, x = rx;
        }

        if (t == nod::NIL) rt = x;
        return x->splay(t);
    }

    nod *select(int a, int b){
        return select(a-1, select(b))->r;
    }

    S prod(int a, int b) {
        return select(a, b)->d;
    }

    void set(int p, S s) {
        nod* x = select(p, p+1); x->d = s;

        while (x->p != nod::NIL) {
            x = x->p;
            x->upd();
        }
    }
};

#undef l
#undef rgu


}  // namespace splay

}  // namespace lastweapon


struct rec{
    int ky, ss, ls, rs, ms;
    rec(int s = 0) {
        ky = ss = ls = rs = ms = s;
    }
};

rec e() {
    rec z = rec(-INF);
    z.ss = 0;
    return z;
}

void op(rec& x, const rec l, const rec r) {
    x.ss = l.ss + x.ky + r.ss;
    x.ls = max(l.ls, l.ss + x.ky + max(0, r.ls));
    x.rs = max(r.rs, max(0, l.rs) + x.ky + r.ss);
    x.ms = max({l.ms, max(l.rs, 0) + x.ky + max(0, r.ls), r.ms});
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int n; RD(n); vector<rec> a(n); REP(i, n) a[i] = rec(RD());
    lastweapon::splay::splay<rec, op, e> T(a);

    Rush {
        if (RD()) { // query
            int l, r; RD(l, r); ++r;
            cout << T.prod(l, r).ms << endl;
        } else { // modify
            int x, y; RD(x, y);
            T.set(x, rec(y));
        }
    }
}

Posted by xiaodao
Category: 日常