{"id":510,"date":"2018-12-23T21:06:24","date_gmt":"2018-12-23T13:06:24","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=510"},"modified":"2018-12-23T21:06:24","modified_gmt":"2018-12-23T13:06:24","slug":"lp2596-zjoi2006-%e4%b9%a6%e6%9e%b6","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2018\/12\/23\/lp2596-zjoi2006-%e4%b9%a6%e6%9e%b6\/","title":{"rendered":"lp2596 ZJOI2006 \u4e66\u67b6"},"content":{"rendered":"\n<p><br> \u770b\u5230\u8fd9\u4e00\u9898\u6211\u4eec\u5c31\u53ef\u4ee5\u60f3\u5230Splay\u3002<br> \u5177\u4f53\u6765\u8bf4\uff0c\u8fd9\u4e00\u9898\u8981\u6c42\u7ef4\u62a4\u4e0b\u5217\u56db\u4e2a\u64cd\u4f5c\uff1a<br> \u5c06\u5e8f\u5217\u4e2d\u7684\u4e00\u4e2a\u6570\u4e0e\u5b83\u7684\u524d\u4e00\u4e2a\u6570\/\u540e\u4e00\u4e2a\u6570\u4ea4\u6362\u3002<br> \u5c06\u5e8f\u5217\u4e2d\u7684\u4e00\u4e2a\u6570\u79fb\u5230\u5e8f\u5217\u5934\/\u5e8f\u5217\u5c3e\u3002<br> \u5982\u679c\u5355\u5355\u5982\u6b64\u7684\u8bdd\u90a3\u8fd9\u4e00\u9898\u5c31\u592a\u7b80\u5355\u4e86\u3002\u5bf9\u4e8e\u4e00\u4e8c\u64cd\u4f5c\u53ea\u9700\u8981\u76f4\u63a5\u548c\u524d\u9a71\u3001\u540e\u7ee7\u8c03\u6362\uff0c\u5bf9\u4e8e\u4e09\u56db\u64cd\u4f5c\u53ea\u9700\u8981\u5c06\u5de6\/\u53f3\u5b50\u6811\u79fb\u52a8\u5230\u53f3\/\u5de6\u5b50\u6811\u7684\u6700\u5de6\/\u53f3\u8282\u70b9\u7684\u5de6\/\u53f3\u5b69\u5b50\u3002<br> \u4f46\u4e8b\u5b9e\u4e0a\u5e76\u975e\u8fd9\u6837\u3002\u8fd9\u4e00\u9898\u5bf9\u5e8f\u5217\u4e2d\u6570\u7684\u64cd\u4f5c\u5e76\u975e\u662f\u76f4\u63a5\u7ed9\u51fa\u7684\uff0c\u800c\u662f\u5bf9\u5e8f\u5217\u4e2d\u7684\u6bcf\u4e00\u4e2a\u70b9\u7f16\u4e86\u53f7\uff0c\u7136\u540e\u6bcf\u4e00\u6b21\u8bbf\u95ee\u8fd9\u4e2a\u7f16\u53f7\u3002<br> \u4f46\u4ed4\u7ec6\u601d\u8003\u5c31\u4f1a\u53d1\u73b0\uff0c\u8003\u8651\u5230\u5bf9\u5e8f\u5217\u7684\u64cd\u4f5c\u53ea\u4f1a\u66f4\u6362\u4f4d\u7f6e\uff0c<br> \u6545\u800c\uff0c\u5bf9\u4e8e\u8fd9\u79cd\u64cd\u4f5c\uff0c\u6211\u4eec\u5b9a\u4e49\u4e00\u4e2a\u6570\u7ec4\u540d\u4e3aloc\uff0c\u50a8\u5b58\u7684\u662f\uff0c\u7f16\u53f7\u4e3a\\(loc_i\\)\u7684\u6570\u5728\u6570\u5217\u4e2d\u7684\u6807\u53f7\u3002 <br> \u8981\u5341\u5206\u6ce8\u610f\u7f16\u53f7\u548c\u9006\u7f16\u53f7\u7684\u5bf9\u5e94\u5173\u7cfb\u3002\u4ee5\u53ca\u4ea4\u6362\u4e4b\u540e\u5bf9\u5b83\u4eec\u539f\u6765\u7684\u5173\u7cfb\u7684\u5f71\u54cd\u3002 <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;iostream>\n#include&lt;cstdio>\n#define MID ((L+R)>>1)\nint loc[80005],aloc[80005];\nclass Splay{\n\tprivate:\n\t\tclass Node{\n\t\t\tpublic:\n\t\t\t\tint fa;\n\t\t\t\tint sn[2];\n\t\t\t\tint sz;\n\t\t\t\tinline void prnt(){\n\t\t\t\t\tprintf(\"(%d,%d,%d)\\n\",fa,sn[0],sn[1]);\n\t\t\t\t}\n\t\t\tinline Node(int FA=0,int LS=0,int RS=0,int SZ=0){\n\t\t\t\tfa=FA,sn[0]=LS,sn[1]=RS,sz=SZ;\n\t\t\t}\n\t\t};\n\t\tNode tr[80005];\n\t\tint rt;\n\t\tinline void updt(int X){\n\t\t\ttr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+1;\n\t\t}\n\t\tinline int fndD(int X){\n\t\t\treturn tr[tr[X].fa].sn[1]==X;\n\t\t}\n\t\tinline void splayOne(int X){\n\t\t\tint D=fndD(X),D2=fndD(tr[X].fa);\n\t\t\ttr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];\n\t\t\ttr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].fa].fa;\n\t\t\ttr[tr[X].fa].sn[D2]=X,tr[tr[X].sn[D^1]].fa=X;\n\t\t\tupdt(tr[X].sn[D^1]),updt(X);\n\t\t}\n\t\tinline void splayTwo(int X){\n\t\t\tint D=fndD(X),D2=fndD(tr[X].fa);\n\t\t\ttr[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\t\t}\n\t\tinline void splayRnw(int X){\n\t\t\twhile(tr[X].fa){\n\t\t\t\tsplayTwo(X);\n\t\t\t}\n\t\t\trt=X;\n\t\t}\n\t\tinline int fnd(int K){\n\t\t\tint P=rt,FP=0;\n\t\t\twhile(P){\n\t\t\t\tFP=P;\n\t\t\t\tif(tr[tr[P].sn[0]].sz+1&lt;K){\n\t\t\t\t\tK-=(tr[tr[P].sn[0]].sz+1);\n\t\t\t\t\tP=tr[P].sn[1];\n\t\t\t\t}else if(tr[tr[P].sn[0]].sz&lt;K){\n\t\t\t\t\treturn P;\n\t\t\t\t}else{\n\t\t\t\t\tP=tr[P].sn[0];\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn FP;\n\t\t}\n\t\tinline int fndMn(int X){\n\t\t\tint P=X,FP=tr[X].fa;\n\t\t\twhile(P){\n\t\t\t\tFP=P;\n\t\t\t\tP=tr[P].sn[0];\n\t\t\t}\n\t\t\treturn FP;\n\t\t}\n\t\tinline int fndMx(int X){\n\t\t\tint P=X,FP=tr[X].fa;\n\t\t\twhile(P){\n\t\t\t\tFP=P;\n\t\t\t\tP=tr[P].sn[1];\n\t\t\t}\n\t\t\treturn FP;\n\t\t}\n\t\tinline int build(int L,int R,int FA){\n\t\t\tif(L>R){\n\t\t\t\treturn 0;\n\t\t\t}\n\t\t\ttr[MID].fa=FA,tr[MID].sz=1;\n\t\t\ttr[MID].sn[0]=build(L,MID-1,MID);\n\t\t\ttr[MID].sn[1]=build(MID+1,R,MID);\n\t\t\tupdt(MID);\n\t\t\treturn MID;\n\t\t}\n\t\tinline void prnt(int X){\n\t\t\tif(!X){\n\t\t\t\treturn;\n\t\t\t}\n\t\t\tprnt(tr[X].sn[0]);\n\t\t\tprintf(\"%d \",X);\n\t\t\tprnt(tr[X].sn[1]);\n\t\t}\n\tpublic:\n\t\tinline void INIT(int N){\n\t\t\tbuild(1,N,0);\n\t\t\trt=(1+N)>>1;\n\t\t}\n\t\tinline void SWAP(int X,int D){\n\t\t\tsplayRnw(X);\n\t\t\tint P=D?fndMn(tr[X].sn[1]):fndMx(tr[X].sn[0]);\n\t\t\tint X_2=aloc[X],P_2=aloc[P];\n\t\t\tstd::swap(loc[X_2],loc[P_2]);\n\t\t\tstd::swap(aloc[X],aloc[P]);\n\t\t\tsplayRnw(X);\n\t\t}\n\t\tinline void LST(int X){\n\t\t\tsplayRnw(X);\n\t\t\tint P=fndMn(tr[X].sn[1]);\n\t\t\ttr[tr[X].sn[0]].fa=P,tr[P].sn[0]=tr[X].sn[0],tr[X].sn[0]=0;\n\t\t\tsplayRnw(tr[P].sn[0]);\n\t\t}\n\t\tinline void RST(int X){\n\t\t\tsplayRnw(X);\n\t\t\tint P=fndMx(tr[X].sn[0]);\n\t\t\ttr[tr[X].sn[1]].fa=P,tr[P].sn[1]=tr[X].sn[1],tr[X].sn[1]=0;\n\t\t\tsplayRnw(tr[P].sn[1]);\n\t\t}\n\t\tinline int RNK(int X){\n\t\t\tsplayRnw(X);\n\t\t\treturn tr[tr[X].sn[0]].sz;\n\t\t}\n\t\tinline int ARNK(int X){\n\t\t\tint P=fnd(X);\n\t\t\tsplayRnw(P);\n\t\t\treturn P;\n\t\t}\n\t\tinline void PRINT(){\n\t\t\tprintf(\"%d ->\",rt);\n\t\t\tprnt(rt);\n\t\t\tputs(\"\");\n\t\t}\n};\nint n,m;\nSplay T;\nvoid init(){\n\tscanf(\"%d%d\",&amp;n,&amp;m);\n\tT.INIT(n);\n\tint x,t;\n\tfor(int i=1;i&lt;=n;++i){\n\t\tscanf(\"%d\",&amp;x);\n\t\tloc[x]=i,aloc[i]=x;\n\t}\n\tchar op[10];\n\tfor(int i=1;i&lt;=m;++i){\n\t\tstd::cin>>op;\n\t\tscanf(\"%d\",&amp;x);\n\t\tswitch(op[0]){\n\t\t\tcase 'T':{\n\t\t\t\tT.LST(loc[x]);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 'B':{\n\t\t\t\tT.RST(loc[x]);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 'I':{\n\t\t\t\tscanf(\"%d\",&amp;t);\n\t\t\t\tt==0?0:(T.SWAP(loc[x],t==-1?0:1),0);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 'A':{\n\t\t\t\tprintf(\"%d\\n\",T.RNK(loc[x]));\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 'Q':{\n\t\t\t\tprintf(\"%d\\n\",aloc[T.ARNK(x)]);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t} \n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u770b\u5230\u8fd9\u4e00\u9898\u6211\u4eec\u5c31\u53ef\u4ee5\u60f3\u5230Splay\u3002 \u5177\u4f53\u6765\u8bf4\uff0c\u8fd9\u4e00\u9898\u8981\u6c42\u7ef4\u62a4\u4e0b\u5217\u56db\u4e2a\u64cd\u4f5c\uff1a \u5c06\u5e8f\u5217\u4e2d\u7684\u4e00\u4e2a\u6570\u4e0e\u5b83\u7684\u524d\u4e00\u4e2a\u6570\/ &hellip; <\/p>\n<p class=\"link-more\"><a href=\"http:\/\/SmokeyDays.top\/wordpress\/2018\/12\/23\/lp2596-zjoi2006-%e4%b9%a6%e6%9e%b6\/\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">\u201clp2596 ZJOI2006 \u4e66\u67b6\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":[66,62,63,43,8,9,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/510"}],"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=510"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/510\/revisions"}],"predecessor-version":[{"id":511,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/510\/revisions\/511"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=510"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=510"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=510"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}