{"id":500,"date":"2018-12-21T15:42:47","date_gmt":"2018-12-21T07:42:47","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=500"},"modified":"2018-12-21T15:50:01","modified_gmt":"2018-12-21T07:50:01","slug":"lp2042-noi2005-%e7%bb%b4%e6%8a%a4%e6%95%b0%e5%88%97","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2018\/12\/21\/lp2042-noi2005-%e7%bb%b4%e6%8a%a4%e6%95%b0%e5%88%97\/","title":{"rendered":"lp2042 NOI2005 \u7ef4\u62a4\u6570\u5217"},"content":{"rendered":"\n<p> Splay\u88f8\u9898\u3002<br> \u5177\u4f53\u6765\u8bf4\uff0c\u7ef4\u62a4\u4e24\u4e2a\u5ef6\u8fdf\u6807\u8bb0\uff0c\u7ffb\u8f6c\u6807\u8bb0\u548c\u6539\u53d8\u6807\u8bb0\u3002\u7136\u540e\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u6807\u8bb0\u8003\u8651\u4e0b\u4f20\u3002<br> \u5bf9\u4e8e\u4e24\u79cd\u8be2\u95ee\u5404\u81ea\u66f4\u65b0\u533a\u95f4\u548c\u4e0e\u533a\u95f4\u6700\u5927\u5b50\u6bb5\u548c\u3002<br> \u4e00\u4e2a\u533a\u95f4\u7684\u6700\u5927\u5b50\u6bb5\u548c\u6709\u53ef\u80fd\u6709\u4e09\u79cd\u60c5\u51b5\uff1a\u5de6\u5b50\u533a\u95f4\u7684\u6700\u5927\u5b50\u6bb5\u548c\uff0c\u53f3\u5b50\u533a\u95f4\u7684\u6700\u5927\u5b50\u6bb5\u548c\uff0c\u4ee5\u53ca\u8de8\u8fc7\u4e24\u4e2a\u533a\u95f4\u7684\u5b50\u6bb5\u548c\u3002<br> \u6545\u800c\u6211\u4eec\u5bf9\u6bcf\u4e2a\u533a\u95f4\u5173\u4e8e\u5b50\u6bb5\u548c\u7ef4\u62a4\u4e09\u4e2a\u4fe1\u606f\uff0c\u5de6\u8d77\u6700\u5927\u5b50\u6bb5\u548c\u3001\u53f3\u8d77\u6700\u5927\u5b50\u6bb5\u548c\u4ee5\u53ca\u603b\u6700\u5927\u5b50\u6bb5\u548c\u3002<br> \u800c\u5bf9\u4e8e\u5de6\u8d77\u6700\u5927\u5b50\u6bb5\u548c\u7684\u66f4\u65b0\uff0c\u5219\u8003\u8651\u4e24\u79cd\u60c5\u51b5\uff1a\u5de6\u5b50\u533a\u95f4\u7684\u6700\u5927\u5b50\u6bb5\u548c\uff0c\u4ee5\u53ca\u6574\u4e2a\u5de6\u5b50\u533a\u95f4\u52a0\u4e0a\u6839\u8282\u70b9\u518d\u52a0\u4e0a\u53f3\u5b50\u533a\u95f4\u7684\u5de6\u8d77\u6700\u5927\u5b50\u6bb5\u548c\u3002<br> \u53f3\u8d77\u540c\u7406\u3002 <br><\/p>\n\n\n\n<p> <em>\u6ce8\u610f\uff1a <\/em><\/p>\n\n\n\n<ul><li>1.updt\u65f6\u5e94\u5f53\u5148updt(tr[X].sn[D^1])\u518dupdt(X)<\/li><li>2.\u6dfb\u52a0\u8282\u70b9\u548c\u5404\u79cd\u4fee\u6539\u4e4b\u540e\u5e94\u5f53\u79d1\u5b66\u5730rnw <\/li><li>3.\u6dfb\u52a0\u8282\u70b9\u65f6\u5e94\u5f53\u6ce8\u610f\u662f\u4eceposi~posi+1\u4e4b\u95f4\u7684\u533a\u95f4\u3002 <\/li><li>4.\u4e00\u4e2a\u8282\u70b9\u88ab\u5220\u9664\u4ee5\u540e\uff0crnw\u5b83\u7684\u7236\u4eb2\u662f\u6ca1\u6709\u610f\u4e49\u7684\uff0c\u5e94\u5f53\u4ece\u6839\u5f00\u59cbrnw<\/li><li>5.\u5185\u5b58\u56de\u6536\u673a\u5236\u4e2d\uff0c\u6dfb\u52a0\u5165\u6808\u5e94\u5f53\u662f++tp,\u51fa\u6808\u5e94\u5f53\u662ftp&#8211; <\/li><li>6.\u8003\u8651updt\u548cpshd\u7684\u65b9\u5f0f\uff1a\u5bf9\u4e8e\u6bcf\u4e00\u6b21pshd\uff0c\u6211\u4eec\u5e94\u8be5\u7edf\u4e00\u4fee\u6539\u5b83\u7684\u5b50\u8282\u70b9\u7684\u6807\u8bb0\uff0c\u5e76\u5bf9\u5b83\u7684\u5b50\u8282\u70b9\u8ba1\u7b97\u8d21\u732e\uff0c\u7136\u540e\u53d6\u6d88\u5b83\u672c\u8eab\u7684\u6807\u8bb0\uff1b\u6253\u6807\u8bb0\u7684\u65f6\u5019\u5bf9\u5b83\u672c\u8eab\u8ba1\u7b97\u597d\u8d21\u732e\u3002<\/li><li> \u6362\u53e5\u8bdd\u8bf4\uff0c\u4e0d\u8981\u5728\u7edf\u8ba1\u4e00\u4e2a\u8282\u70b9\u7684\u8d21\u732e\u4e4b\u524d\uff0cupdt\u5b83\u7684\u7236\u4eb2\u3002 <\/li><li>7.\u52a0\u5165\u8282\u70b9\u5e94\u5f53\u52a0\u5165\u6210\u4e00\u68f5\u4e8c\u53c9\u6811\uff0c\u800c\u4e0d\u662f\u4e00\u6761\u94fe\u3002\u6839\u636e\u6211\u6839\u672c\u4e0d\u61c2\u7684\u52bf\u80fd\u5206\u6790\u6cd5\uff0c\u52a0\u5165\u4e00\u68f5\u4e8c\u53c9\u6811\u5e26\u6765\u7684\u52bf\u80fd\u6539\u53d8\u662f\u5e38\u6570\u4e58\u5927\u5c0f\u7ea7\u7684\uff0c\u800c\u4e00\u6761\u94fe\u5219\u662f\u5bf9\u6570\u4e58\u5927\u5c0f\u7ea7\u7684\u3002  <\/li><li>8.\u5bf9\u4e8eMAX-SUM\u64cd\u4f5c\uff0c\u5fc5\u987b\u8981\u81f3\u5c11\u9009\u4e2d\u4e00\u4e2a\u8282\u70b9\uff0c\u6240\u4ee5\u5e94\u5f53\u989d\u5916\u7ef4\u62a4\u4e00\u4e2a\u6700\u5927\u503c\u3002 <\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;iostream>\n#include&lt;cstdio>\n#define R register\n#define MAGIC 19260817\n#define MID ((L+R_R)>>1)\n\/*\n\n*\/\ninline int Max(int A,int B){\n    return A>B?A:B;\n}\ninline int Chck(int X){\n    return X>0?X:0;\n}\ninline void Swap(int &amp;A,int &amp;B){\n    A^=B^=A^=B;\n}\n\/\/\u8868\u793a\u7279\u6b8a\u72b6\u6001 \nclass Splay{\n    private:\n        class Node{\n            public:\n    \t\t\tint fa;\n    \t\t\tint sn[2];\n    \t\t\tint sz;\n    \t\t\tint sm;\n    \t\t\tint lmxsm;\n    \t\t\tint rmxsm;\n    \t\t\tint mxsm;\n    \t\t\tint mx;\n    \t\t\tint v;\n    \t\t\tint lzy_flp;\n    \t\t\tint lzy_chng;\n    \t\t\tinline void set(int FA,int V){\n    \t\t\t    fa=FA,sz=1,sm=v=mxsm=mx=V,lmxsm=rmxsm=Chck(V);\n    \t\t\t    sn[0]=sn[1]=lzy_flp=0,lzy_chng=MAGIC;\n                }\n                inline void init(){\n                    fa=sz=sm=lmxsm=rmxsm=v=sn[0]=sn[1]=lzy_flp=0;\n                    mxsm=mx=-MAGIC;\n                    lzy_chng=MAGIC;\n                }\n        };\n        Node tr[500005];\n        int st[500005],tp,cnt,rt;\n        inline int fndD(int X){\n            return tr[tr[X].fa].sn[0]==X?0:1;\n        }\n        inline void chng(int X){\n            tr[X].sm=tr[X].lzy_chng*tr[X].sz,tr[X].mxsm=Max(tr[X].lzy_chng,tr[X].lzy_chng*tr[X].sz);tr[X].lmxsm=tr[X].rmxsm=Chck(tr[X].lzy_chng*tr[X].sz);\n            tr[X].v=tr[X].mx=tr[X].lzy_chng;\n        }\n        inline void flp(int X){\n            Swap(tr[X].sn[0],tr[X].sn[1]);\n            Swap(tr[X].lmxsm,tr[X].rmxsm);\n        }\n        inline void pshd(int X){\n            if(!X){\n                return;\n            }\n            if(tr[X].lzy_chng!=MAGIC){\n            \ttr[tr[X].sn[0]].lzy_chng=tr[tr[X].sn[1]].lzy_chng=tr[X].lzy_chng;\n                chng(tr[X].sn[0]),chng(tr[X].sn[1]);\n                tr[X].lzy_chng=MAGIC;\n            }\n            if(tr[X].lzy_flp){\n            \ttr[tr[X].sn[0]].lzy_flp^=1,tr[tr[X].sn[1]].lzy_flp^=1;\n                flp(tr[X].sn[0]),flp(tr[X].sn[1]);\n                tr[X].lzy_flp=0;\n            }\n        }\n        inline void updt(int X){\n            if(!X){\n                return;\n            }\n            tr[X].sm=tr[tr[X].sn[0]].sm+tr[tr[X].sn[1]].sm+tr[X].v;\n            tr[X].mx=Max(Max(tr[tr[X].sn[0]].mx,tr[tr[X].sn[1]].mx),tr[X].v);\n            tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+1;\n            tr[X].lmxsm=Max(tr[tr[X].sn[0]].sm+tr[X].v+tr[tr[X].sn[1]].lmxsm,tr[tr[X].sn[0]].lmxsm);\n            tr[X].rmxsm=Max(tr[tr[X].sn[1]].sm+tr[X].v+tr[tr[X].sn[0]].rmxsm,tr[tr[X].sn[1]].rmxsm);\n            tr[X].mxsm=Max(Max(tr[tr[X].sn[0]].mxsm,tr[tr[X].sn[1]].mxsm),tr[tr[X].sn[0]].rmxsm+tr[X].v+tr[tr[X].sn[1]].lmxsm);\n        }\n        inline void splayOne(int X){\n            int D=fndD(X),D2=fndD(tr[X].fa);\n            tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];\n            tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].fa].fa;\n            tr[tr[X].sn[D^1]].fa=X,tr[tr[X].fa].sn[D2]=X;\n            updt(tr[X].sn[D^1]),updt(X);\n        }\n        inline void splayTwo(int X){\n            int D=fndD(X),D2=fndD(tr[X].fa);\n            tr[X].fa?(tr[tr[X].fa].fa?(D==D2?(splayOne(tr[X].fa),splayOne(X),0):(splayOne(X),splayOne(X),0)):(splayOne(X),0)):0;\n        }\n        inline void splayRnw(int X){\n            if(!X){\n                return;\n            }\n            \/\/printf(\"%d->\",X);\n            while(tr[X].fa){\n                splayTwo(X);\n                \/\/printf(\"[%d,%d,%d[%d,%d](%d)] \",X,tr[X].fa,tr[tr[X].fa].fa,tr[X].sn[0],tr[X].sn[1],fndD(X));\n            }\n            \/\/puts(\"\");\n            rt=X;\n        }\n        \/\/\u6ce8\u610f\uff0c\u6743\u503csplay\u4e2d\u7684fnd\u51fd\u6570\u5b9e\u8d28\u4e0a\u6c42\u7684\u662f\u6392\u540d\u4e3aK\u7684\u8282\u70b9\u3002 \n        inline int fnd(int K){\n            R int P=rt,FP=0;\n            while(P){\n                pshd(P);\n                FP=P;\n                if(tr[tr[P].sn[0]].sz+1&lt;K){\n                    K-=(tr[tr[P].sn[0]].sz+1);\n                    P=tr[P].sn[1];\n                }else if(tr[tr[P].sn[0]].sz&lt;K){\n                    return P;\n                }else{\n                    P=tr[P].sn[0];\n                }\n            }\n            return FP;\n        }\n        inline int nwlc(int FA,int D,int V){\n            if(!cnt){\n                rt=1;\n            }\n            int P=tp?st[tp--]:++cnt;\n            tr[FA].sn[D]=P;\n            tr[P].set(FA,V);\n            return P;\n        }\n        inline int preSplay(int L,int LEN){\n            int __L__=fnd(L),__R__=fnd(L+LEN+1);\n            splayRnw(tr[__L__].fa),splayRnw(tr[__R__].fa);\n            splayRnw(__L__);\n            splayRnw(__R__);\n            \/\/printf(\"%d,%d,%d\\n\",rt,tr[rt].sn[0],tr[rt].sn[1]);\n            if(tr[__L__].fa!=__R__&amp;&amp;__L__!=__R__){\n                splayOne(__L__);\n            }\n            pshd(tr[tr[rt].sn[0]].sn[1]);\n            return tr[rt].sn[0];\n        }\n        inline void rmv(int X){\n            if(!X){\n                return;\n            }\n            rmv(tr[X].sn[0]);\n            rmv(tr[X].sn[1]);\n            tr[tr[X].fa].sn[fndD(X)]=0;\n            tr[tr[X].sn[0]].fa=tr[tr[X].sn[1]].fa=0;\n            st[++tp]=X;\n        }\n        inline void prnt(int X, int dep=0){\n            if(!X){\n                return;\n            }\n            \/\/pshd(X);\n            prnt(tr[X].sn[0], dep+1);\n            \/\/printf(\"{%d}[%d](%d,%d)[%d][%d,%d] \",X,tr[X].v,tr[X].sn[0],tr[X].sn[1],tr[X].mxsm,tr[X].lmxsm,tr[X].rmxsm);\n            for(int i = 1; i &lt;= dep; ++i) printf(\"\u53e3\");\n        \t\/\/printf(\"ID:%d    VAL:%d    SM:%d   CHANGE_TAG:%d \\n\",X,tr[X].v,tr[X].sm,tr[X].lzy_chng);\n        \tprintf(\"%d %d\\n\",tr[X].v,tr[X].mxsm);\n            prnt(tr[X].sn[1], dep+1);\n        }\n        inline void build(int L,int R_R,int *IN,int D,int FA){\n        \tif(L>R_R){\n        \t\treturn;\n\t\t\t}\n        \tint P=nwlc(FA,D,IN[MID]);\n        \tbuild(L,MID-1,IN,0,P);\n        \tbuild(MID+1,R_R,IN,1,P);\n        \tupdt(P);\n\t\t}\n    public:\n        inline void INSERT(int L,int TOT,int *IN){\n            int X=preSplay(L+1,0);\n            build(1,TOT,IN,1,X);\n            updt(X),updt(tr[X].fa),updt(tr[tr[X].fa].fa);\n       }\n        inline void DELETE(int L,int LEN){\n            int X=tr[preSplay(L,LEN)].sn[1];\n            rmv(X);\n            updt(tr[rt].sn[0]),updt(rt);\n        }\n        inline void MAKE_SAME(int L,int LEN,int V){\n            int X=tr[preSplay(L,LEN)].sn[1];\n            tr[X].lzy_chng=V;\n            chng(X);\n            updt(tr[X].fa),updt(tr[tr[X].fa].fa);\n        }\n        inline void REVERSE(int L,int LEN){\n            int X=tr[preSplay(L,LEN)].sn[1];\n            tr[X].lzy_flp^=1;\n            if(tr[X].lzy_flp){\n            \tflp(X);\n            }\n            updt(tr[X].fa),updt(tr[tr[X].fa].fa);\n        }\n        inline void GET_SUM(int L,int LEN){\n            int X=tr[preSplay(L,LEN)].sn[1];\n            printf(\"%d\\n\",tr[X].sm);\n        }\n        inline void MAX_SUM(){\n            printf(\"%d\\n\",(tr[rt].mxsm)?tr[rt].mxsm:tr[rt].mx);\n        }\n        inline void INIT(int N,int *IN){\n            tr[0].init();\n            rt=tp=cnt=0;\n            int X=0;\n            for(int i=1;i&lt;=N;++i){\n                X=nwlc(X,1,IN[i]);\n            }\n            nwlc(1,0,-MAGIC),nwlc(X,1,-MAGIC);\n            splayRnw(N+1),splayRnw(N+2);\n        }\n        inline void PRINT(){\n            printf(\"%d ->\\n\",rt);\n            prnt(rt);\n            puts(\"\");\n        }\n};\nint n,m;\nint a[4000005];\nSplay T;\nvoid init(){\n    scanf(\"%d%d\",&amp;n,&amp;m);\n    int posi,tot,c;\n    char op[10];\n    for(int i=1;i&lt;=n;++i){\n        scanf(\"%d\",a+i);\n    }\n    T.INIT(n,a);\n    for(int i=1;i&lt;=m;++i){\n        std::cin>>op;\n        switch(op[2]){\n            case 'S':{\n                scanf(\"%d%d\",&amp;posi,&amp;tot);\n                for(int j=1;j&lt;=tot;++j){\n                    scanf(\"%d\",a+j);\n                }\n                T.INSERT(posi,tot,a);\n                break;\n            }\n            case 'L':{\n                scanf(\"%d%d\",&amp;posi,&amp;tot);\n                T.DELETE(posi,tot);\n                break;\n            }\n            case 'K':{\n                scanf(\"%d%d%d\",&amp;posi,&amp;tot,&amp;c);\n                T.MAKE_SAME(posi,tot,c);\n                break;\n            }\n            case 'V':{\n                scanf(\"%d%d\",&amp;posi,&amp;tot);\n                T.REVERSE(posi,tot);\n                break;\n            }\n            case 'T':{\n                scanf(\"%d%d\",&amp;posi,&amp;tot);\n                T.GET_SUM(posi,tot);\n                break;\n            }\n            case 'X':{\n                T.MAX_SUM();\n                break;\n            }\n        }\n    }\n}\n\nint main(){\n    init();\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Splay\u88f8\u9898\u3002 \u5177\u4f53\u6765\u8bf4\uff0c\u7ef4\u62a4\u4e24\u4e2a\u5ef6\u8fdf\u6807\u8bb0\uff0c\u7ffb\u8f6c\u6807\u8bb0\u548c\u6539\u53d8\u6807\u8bb0\u3002\u7136\u540e\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u6807\u8bb0\u8003\u8651\u4e0b\u4f20\u3002 \u5bf9\u4e8e\u4e24\u79cd\u8be2\u95ee\u5404 &hellip; <\/p>\n<p class=\"link-more\"><a href=\"http:\/\/SmokeyDays.top\/wordpress\/2018\/12\/21\/lp2042-noi2005-%e7%bb%b4%e6%8a%a4%e6%95%b0%e5%88%97\/\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">\u201clp2042 NOI2005 \u7ef4\u62a4\u6570\u5217\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[50,66,62,63,43,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/500"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=500"}],"version-history":[{"count":3,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/500\/revisions"}],"predecessor-version":[{"id":503,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/500\/revisions\/503"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=500"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=500"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=500"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}