{"id":1996,"date":"2022-07-21T01:06:53","date_gmt":"2022-07-20T17:06:53","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=1996"},"modified":"2022-07-21T02:35:16","modified_gmt":"2022-07-20T18:35:16","slug":"atl-%e9%a3%8e-splay-%e6%a8%a1%e6%9d%bf","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/atl-%e9%a3%8e-splay-%e6%a8%a1%e6%9d%bf\/","title":{"rendered":"atl \u98ce splay \u6a21\u677f"},"content":{"rendered":"

\u5f04\u5b8c\u4e86\u4e00\u4e2a\u7248\u672c\u611f\u89c9\u8fd8\u884c
\nhttps:\/\/github.com\/lychees\/last-weapon\/commit\/58976a70bc0948c2073091c6cf2966a16e352127<\/a><\/p>\n

\u76ee\u524d\u4f8b\u9898\u7528\u7684\u662f GSS \u7cfb\u5217\u3002\u3002\u3002<\/p>\n

\u4e0d\u8fc7 GSS3 \u8fd9\u4e2a\u9898\u548c GSS1 \u4e00\u6837\u90fd\u5361\u4ee3\u7801\u957f\u5ea6\u3002\u3002\u9700\u8981\u5220\u70b9\u4e1c\u897f\u3002\u3002
\nGSS6 \u5012\u662f\u5f88\u9002\u5408\u3002\u3002\u3002<\/p>\n

\r\n#include <lastweapon\/segtree>\r\nusing namespace lastweapon;\r\n\r\nstruct rec{\r\n    int ss, ls, rs, ms;\r\n    rec(int s = 0) {\r\n        ss = ls = rs = ms = s;\r\n    }\r\n};\r\n\r\nrec e() {\r\n    rec z = rec(-INF);\r\n    z.ss = 0;\r\n    return z;\r\n}\r\n\r\nrec op(const rec l, const rec r) {\r\n    rec z;\r\n    z.ss = l.ss + r.ss;\r\n    z.ls = max(l.ls, l.ss + r.ls);\r\n    z.rs = max(r.rs, l.rs + r.ss);\r\n    z.ms = max({l.ms, r.ms, l.rs + r.ls});\r\n    return z;\r\n}\r\n\r\nint main() {\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n#endif\r\n    int n; RD(n); vector<rec> a(n); REP(i, n) a[i] = rec(RD());\r\n    segtree<rec, op, e> T(a);\r\n\r\n    Rush {\r\n        if (RD()) { \/\/ query\r\n            int l, r; RD(l, r); --l;\r\n            cout << T.prod(l, r).ms << endl;\r\n        } else { \/\/ modify\r\n            int x, y; RD(x, y); --x;\r\n            T.set(x, rec(y));\r\n        }\r\n    }\r\n}\r\n<\/pre>\n
\r\n#include <lastweapon\/splay>\r\n\r\nstruct rec{\r\n    int ky, ss, ls, rs, ms;\r\n    rec(int s = 0) {\r\n        ky = ss = ls = rs = ms = s;\r\n    }\r\n};\r\n\r\nrec e() {\r\n    rec z = rec(-INF);\r\n    z.ss = 0;\r\n    return z;\r\n}\r\n\r\nvoid op(rec& x, const rec l, const rec r) {\r\n    x.ss = l.ss + x.ky + r.ss;\r\n    x.ls = max(l.ls, l.ss + x.ky + max(0, r.ls));\r\n    x.rs = max(r.rs, max(0, l.rs) + x.ky + r.ss);\r\n    x.ms = max({l.ms, max(l.rs, 0) + x.ky + max(0, r.ls), r.ms});\r\n}\r\n\r\nint main() {\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n#endif\r\n    int n; RD(n); vector<rec> a(n); REP(i, n) a[i] = rec(RD());\r\n    lastweapon::splay::splay<rec, op, e> T(a);\r\n\r\n    Rush {\r\n        if (RD()) { \/\/ query\r\n            int l, r; RD(l, r); ++r;\r\n            cout << T.prod(l, r).ms << endl;\r\n        } else { \/\/ modify\r\n            int x, y; RD(x, y);\r\n            T.set(x, rec(y));\r\n        }\r\n    }\r\n}\r\n<\/pre>\n
\r\n#include <algorithm>\r\n#include <iostream>\r\n#include <iomanip>\r\n#include <sstream>\r\n#include <cstring>\r\n#include <cstdio>\r\n#include <string>\r\n#include <vector>\r\n#include <bitset>\r\n#include <queue>\r\n#include <cmath>\r\n#include <ctime>\r\n#include <list>\r\n#include <set>\r\n#include <map>\r\n\r\nusing namespace std;\r\n\r\n#define REP(i, n) for (int i=0;i<int(n);++i)\r\n#define Rush for(int ____T=RD(); ____T--;)\r\n\r\nconst int INF = 0x3f3f3f3f;\r\n\r\ntemplate<class T> inline void RD(T &);\r\ntemplate<class T> inline void OT(const T &);\r\ninline int RD(){ int x; RD(x); return x;}\r\ntemplate<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}\r\n\r\ntemplate<class T> inline void RD(T &x){\r\n    scanf("%d", &x);\r\n}\r\n\r\ntemplate<class T> inline void OT(const T &x){\r\n    printf("%d\\n", x);\r\n}\r\n\r\n\/* .................................................................................................................................. *\/\r\n\r\n\r\nnamespace lastweapon {\r\n\r\nnamespace splay {\r\n\r\ntemplate <class S, void (*op)(S&, const S, const S), S (*e)()>\r\nstruct node {\r\n\r\n    static node *NIL; node *c[2], *p;\r\n    int sz; S d;\r\n\r\n#define NIL node::NIL\r\n#define l c[0]\r\n#define r c[1]\r\n#define lx x->l\r\n#define rx x->r\r\n#define px x->p\r\n#define ly y->l\r\n#define ry y->r\r\n#define py y->p\r\n\r\n    node() {\r\n        d=e();\r\n    }\r\n\r\n    inline void reset(S s){l=r=p=NIL,d=s;sz=1;}\r\n\r\n    inline void upd(){\r\n        sz = l->sz + 1 + r->sz;\r\n        op(d, l->d, r->d);\r\n    }\r\n    inline int sgn(){return p->r==this;}\r\n    inline void setc(int d,node*x){c[d]=x,px=this;}\r\n    inline void setl(node*x){setc(0,x);}\r\n    inline void setr(node*x){setc(1,x);}\r\n\r\n    inline void rot(int d){\r\n        node*y=p,*z=py;z->setc(y->sgn(),this);\r\n        y->setc(d,c[!d]),setc(!d,y),y->upd();\r\n    }\r\n    inline void rot(){rot(sgn());}\r\n    inline node*splay(node*t){\r\n        int a,b;while(p!=t){\r\n            if (p->p==t){rot();break;}\r\n            else a=sgn(),b=p->sgn(),(a^b?this:p)->rot(a),rot(b);\r\n        }\r\n        upd();\r\n        return this;\r\n    }\r\n};\r\n\r\n\r\n#undef NIL\r\n\r\ntemplate <class S, void (*op)(S&, const S, const S), S (*e)()>\r\nnode<S, op, e> *node<S, op, e>::NIL = new node<S, op, e>;\r\n\r\n\r\ntemplate <class S, void (*op)(S&, const S, const S), S (*e)()> struct splay {\r\n\r\n    using nod = node<S, op, e>;\r\n\r\n    std::vector<nod> d;\r\n    int n; nod* rt;\r\n\r\n    splay() : splay(0) {}\r\n    explicit splay(int n) : splay(std::vector<S>(n, e())) {}\r\n    explicit splay(const std::vector<S>& a) : n(int(a.size())) {\r\n        rt = new nod(); rt->reset(0);\r\n        REP(i, n) {\r\n            nod* t = new nod();\r\n            t->reset(a[i]);\r\n            t->setl(rt); t->upd();\r\n            rt = t;\r\n        }\r\n        nod* t = new nod();\r\n        t->reset(0);\r\n        t->setl(rt); t->upd();\r\n        rt = t;\r\n    }\r\n\r\n    nod *select(int k, nod*t=nod::NIL){\r\n        nod *x = rt; while (lx->sz != k){\r\n            if (k < lx->sz) x = lx;\r\n            else k -= lx->sz+1, x = rx;\r\n        }\r\n\r\n        if (t == nod::NIL) rt = x;\r\n        return x->splay(t);\r\n    }\r\n\r\n    nod *select(int a, int b){\r\n        return select(a-1, select(b))->r;\r\n    }\r\n\r\n    S prod(int a, int b) {\r\n        return select(a, b)->d;\r\n    }\r\n\r\n    void set(int p, S s) {\r\n        nod* x = select(p, p+1); x->d = s;\r\n\r\n        while (x->p != nod::NIL) {\r\n            x = x->p;\r\n            x->upd();\r\n        }\r\n    }\r\n};\r\n\r\n#undef l\r\n#undef rgu\r\n\r\n\r\n}  \/\/ namespace splay\r\n\r\n}  \/\/ namespace lastweapon\r\n\r\n\r\nstruct rec{\r\n    int ky, ss, ls, rs, ms;\r\n    rec(int s = 0) {\r\n        ky = ss = ls = rs = ms = s;\r\n    }\r\n};\r\n\r\nrec e() {\r\n    rec z = rec(-INF);\r\n    z.ss = 0;\r\n    return z;\r\n}\r\n\r\nvoid op(rec& x, const rec l, const rec r) {\r\n    x.ss = l.ss + x.ky + r.ss;\r\n    x.ls = max(l.ls, l.ss + x.ky + max(0, r.ls));\r\n    x.rs = max(r.rs, max(0, l.rs) + x.ky + r.ss);\r\n    x.ms = max({l.ms, max(l.rs, 0) + x.ky + max(0, r.ls), r.ms});\r\n}\r\n\r\nint main() {\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n#endif\r\n    int n; RD(n); vector<rec> a(n); REP(i, n) a[i] = rec(RD());\r\n    lastweapon::splay::splay<rec, op, e> T(a);\r\n\r\n    Rush {\r\n        if (RD()) { \/\/ query\r\n            int l, r; RD(l, r); ++r;\r\n            cout << T.prod(l, r).ms << endl;\r\n        } else { \/\/ modify\r\n            int x, y; RD(x, y);\r\n            T.set(x, rec(y));\r\n        }\r\n    }\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
\u5f04\u5b8c\u4e86\u4e00\u4e2a\u7248\u672c\u611f\u89c9\u8fd8\u884c https:\/\/github.com\/lychees\/last-weapon\/commit\/58976a70bc0948c2073091c6cf2966a16e352127 \u76ee\u524d\u4f8b\u9898\u7528\u7684\u662f GSS \u7cfb\u5217\u3002\u3002\u3002 \u4e0d\u8fc7 GSS3 \u8fd9\u4e2a\u9898\u548c GSS1 \u4e00\u6837\u90fd\u5361\u4ee3\u7801\u957f\u5ea6\u3002\u3002\u9700\u8981\u5220\u70b9\u4e1c\u897f\u3002\u3002 GSS6 \u5012\u662f\u5f88\u9002\u5408\u3002\u3002\u3002 #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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-1996","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-wc","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1996","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1996"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1996\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1996"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1996"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1996"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}