Original link: https://www.shuizilong.com/house/archives/atl-%E9%A3%8E-splay-%E6%A8%A1%E6%9D%BF/
It’s okay to finish a version
https://github.com/lychees/last-weapon/commit/58976a70bc0948c2073091c6cf2966a16e352127
The current example uses the GSS series. . .
However, GSS3 has the same code length as GSS1. . Need to delete something. .
GSS6 is a good fit. . .
#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 lc[0] #define rc[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)); } } }
This article is reproduced from: https://www.shuizilong.com/house/archives/atl-%E9%A3%8E-splay-%E6%A8%A1%E6%9D%BF/
This site is for inclusion only, and the copyright belongs to the original author.