{"id":930,"date":"2019-10-01T23:17:45","date_gmt":"2019-10-01T15:17:45","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=930"},"modified":"2019-10-01T23:17:45","modified_gmt":"2019-10-01T15:17:45","slug":"lp3302-sdoi2013-%e6%a3%ae%e6%9e%97","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2019\/10\/01\/lp3302-sdoi2013-%e6%a3%ae%e6%9e%97\/","title":{"rendered":"lp3302 SDOI2013 \u68ee\u6797"},"content":{"rendered":"\n<h2><\/h2>\n\n\n\n<p>\u6211\u4eec\u53d1\u73b0\uff0c\u6811\u4e0a\u7684\u94fe\u4e0a\u7b2ck\u5927\u662f\u53ef\u4ee5\u4f7f\u7528\u4e3b\u5e2d\u6811\u6765\u7ef4\u62a4\u7684\u3002\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u8282\u70b9\uff0c\u6211\u4eec\u4ece\u5b83\u7684\u7236\u4eb2\u590d\u5236\u4e00\u4e2a\u7248\u672c\uff0c\u7136\u540e\u6bcf\u4e00\u6b21\u6c42\u51faLCA\u4ee5\u540e\u5bf9\u94fe\u7684\u4e24\u4e2a\u7aef\u70b9\u3001\u94fe\u7684LCA\u3001\u94fe\u7684\u7236\u4eb2\u5206\u522b\u67e5\u8be2\u3002\u4e4b\u540e\u7edf\u8ba1\u7b54\u6848\u5373\u53ef\u3002<br>\n\u5bf9\u4e8e\u6709\u8fde\u8fb9\u64cd\u4f5c\u7684\u6811\uff0c\u6211\u4eec\u53ef\u80fd\u53ef\u4ee5\u60f3\u5230\u7528LCT\u6765\u7ef4\u62a4\u3002\u4f46\u662f\u4ee3\u7801\u96be\u5ea6\u592a\u9ad8\uff0c\u800c\u4e14\u4e8b\u5b9e\u4e0a\u6211\u4e5f\u4e0d\u77e5\u9053\u8981\u600e\u4e48\u5199\u3002\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u8003\u8651\u4e00\u79cd\u7c7b\u4f3c\u4e8e\u6309\u79e9\u5408\u5e76\u7684\u64cd\u4f5c\uff0c\u4e5f\u5c31\u662f\u8bf4\uff0c\u6bcf\u4e00\u6b21\uff0c\u6211\u4eec\u628a\u5b50\u6811\u5927\u5c0f\u8f83\u5c0f\u7684\u5b50\u6811\u5408\u5e76\u5230\u5b50\u6811\u5927\u5c0f\u8f83\u5927\u7684\u5b50\u6811\u3002\u5bf9\u4e8e\u8f83\u5c0f\u7684\u90a3\u68f5\u6811\uff0c\u6211\u4eec\u66b4\u529b\u66f4\u65b0\u5176\u4e2d\u7684\u6bcf\u4e00\u4e2a\u8282\u70b9\u3002\u4e8e\u662f\u53ef\u4ee5\u8bc1\u660e\uff0c\u6bcf\u4e2a\u8282\u70b9\u7684\u88ab\u66f4\u65b0\u6b21\u6570\u6700\u591a\u4e0d\u8d85\u8fc7log\u6b21\u3002<br>\n\u8fd9\u6837\u6211\u4eec\u5c31\u6709\u4e86\u4e00\u4e2a\\(O(nlog^2n)\\)\u7684\u505a\u6cd5\u3002<br>\n\u6ce8\u610f\uff1a\u4e3b\u5e2d\u6811\u7684L\uff0cR\u672c\u8eab\u5c31\u662f\u8282\u70b9\u4f4d\u7f6e\uff1b\u5408\u5e76\u7684\u65f6\u5019\u8981\u8bb0\u5f97\u66f4\u65b0\u5c0f\u6811\u7684\u6839\u8282\u70b9\uff1b\u8fd4\u56de\u7684\u503c\u662f\u7b2ck\u5927\u7684\u503c\u800c\u975e\u7b2ck\u5927\u7684\u6392\u540d\u56e0\u800c\u8981\u9006\u79bb\u6563\u5316\u3002 <\/p>\n\n\n\n<p><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;iostream>\n#include&lt;cstdio>\n#include&lt;cstring>\n#include&lt;algorithm>\n#include&lt;queue>\n#include&lt;vector>\n#include&lt;map>\nusing namespace std;\n\nconst int N=80005;\nstruct data{\n\tint id;\n\tint val;\n}a[N];\ninline bool cmp(const data &amp;A,const data &amp;B){\n\treturn A.val&lt;B.val;\n}\ninline bool cmp2(const data &amp;A,const data &amp;B){\n\treturn A.id&lt;B.id;\n}\nstruct ee{\n\tint v;\n\tint nxt;\n}e[N&lt;&lt;1];\nint h[N],et=0;\ninline void Eadd(int U,int V){\n\te[++et]=(ee){V,h[U]};\n\th[U]=et;\n}\ninline void add(int U,int V){\n\tEadd(U,V),Eadd(V,U);\n}\n#define MID (L+R>>1)\nclass CMT{\n\tprivate:\n\t\tclass Node{\n\t\t\tpublic:\n\t\t\t\tint l;int r;int sz;\n\t\t};\n\t\tNode tr[30000000];\n\t\tint cnt,rt[N];\n\t\tinline void bld(int LST,int &amp;NW,int L,int R,int V){\n\t\t\tNW=++cnt;tr[NW].sz=tr[LST].sz+1;\n\t\t\tif(L==R){return;}\n\t\t\tV&lt;=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);\n\t\t}\n\t\tinline int qry(int A,int B,int C,int D,int L,int R,int V){\n\t\t\twhile(L&lt;R){\n\/\/\t\t\t\tprintf(\"nw:%d %d %d %d %d\\n\",A,B,C,D,V);\n\t\t\t\t(tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz&lt;V)?\n\t\t\t\t(V-=tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz,L=MID+1,A=tr[A].r,B=tr[B].r,C=tr[C].r,D=tr[D].r):\n\t\t\t\t(R=MID,A=tr[A].l,B=tr[B].l,C=tr[C].l,D=tr[D].l);\n\t\t\t}\n\t\t\treturn L;\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].l);\n\t\t\tprnt(tr[X].r);\n\t\t\tprintf(\"%d \",tr[X].sz);\n\t\t}\n\tpublic:\n\t\tinline void ADD(int LST,int VER,int V){\n\t\t\tbld(rt[LST],rt[VER],1,80000,V);\n\t\t}\n\t\tinline int QRY(int A,int B,int C,int D,int V){\n\t\t\treturn qry(rt[A],rt[B],rt[C],rt[D],1,80000,V);\n\t\t}\n\t\tinline void prpr(){\n\t\t\tcnt=0;\n\t\t}\n\t\tinline void pt(int X){\n\t\t\tprnt(rt[X]);\n\t\t}\n}TR;\nint vis[N],fa[N][20],sz[N],dep[N],loc[N];\ninline void dfs0(int X){\n\/\/\tprintf(\"\\t\\t\\tdfs0(%d)%d\\n\",X,dep[X]);\n\tvis[X]=sz[X]=1;\n\tfor(int i=h[X];i;i=e[i].nxt){\n\t\tif(vis[e[i].v]){\n\t\t\tcontinue;\n\t\t}\n\t\tfa[e[i].v][0]=X;\n\t\tdep[e[i].v]=dep[X]+1;\n\t\tfor(int j=1;j&lt;=18;++j){\n\t\t\tfa[e[i].v][j]=fa[fa[e[i].v][j-1]][j-1];\n\t\t}\n\t\tTR.ADD(X,e[i].v,a[e[i].v].val);\n\t\tdfs0(e[i].v);\n\t\tsz[X]+=sz[e[i].v];\n\t}\n}\ninline void dfs1(int X){\n\tvis[X]=0;\n\tfor(int i=h[X];i;i=e[i].nxt){\n\t\tif(!vis[e[i].v]){\n\t\t\tcontinue;\n\t\t}\n\t\tdfs1(e[i].v);\n\t}\n}\ninline int szq(int X){\n\tfor(int i=18;i>=0;--i){\n\t\tif(fa[X][i]!=0){\n\t\t\tX=fa[X][i];\n\t\t}\n\t}\n\treturn sz[X];\n}\ninline void uni(int X,int Y){\n\tint SZ=szq(X);\n\tdfs1(X);\n\tadd(X,Y);\n\tfa[X][0]=Y;\n\tdep[X]=dep[Y]+1;\n\tTR.ADD(Y,X,a[X].val);\n\tfor(int i=1;i&lt;=18;++i){\n\t\tfa[X][i]=fa[fa[X][i-1]][i-1];\n\t}\n\tint RT=X;\n\tfor(int i=18;i>=0;--i){\n\t\tif(fa[RT][i]){\n\t\t\tRT=fa[RT][i];\n\t\t}\n\t}\n\tsz[RT]+=SZ;\n\tdfs0(X);\n}\ninline int lca(int X,int Y){\n\tif(dep[X]&lt;dep[Y]){\n\t\tX^=Y^=X^=Y;\n\t}\n\tfor(int i=18;i>=0;--i){\n\t\tif(dep[fa[X][i]]>=dep[Y]){\n\t\t\tX=fa[X][i];\n\t\t}\n\t}\n\tif(X==Y){\n\t\treturn X;\n\t}\n\tfor(int i=18;i>=0;--i){\n\t\tif(fa[X][i]!=fa[Y][i]){\n\t\t\tX=fa[X][i],Y=fa[Y][i];\n\t\t}\n\t}\n\treturn fa[X][0];\n}\nint n,m,q,tid;\nvoid init(){\n\tscanf(\"%d\",&amp;tid);\n\tscanf(\"%d%d%d\",&amp;n,&amp;m,&amp;q);\n\tfor(int i=1;i&lt;=n;++i){\n\t\tscanf(\"%d\",&amp;a[i].val);\n\t\ta[i].id=i;\n\t}\n\tstd::sort(a+1,a+1+n,cmp);\n\tfor(int i=1;i&lt;=n;++i){\n\t\tloc[i]=a[i].val;\n\t}\n\tfor(int i=1;i&lt;=n;++i){\n\t\tif(a[i].val!=a[i-1].val){\n\t\t\ta[i].val=a[i-1].val+1;\n\t\t}else{\n\t\t\ta[i].val=a[i-1].val;\n\t\t}\n\t}\n\tstd::sort(a+1,a+1+n,cmp2); \n\tint u,v;\n\tfor(int i=1;i&lt;=m;++i){\n\t\tscanf(\"%d%d\",&amp;u,&amp;v);\n\t\tadd(u,v);\n\t}\n\tTR.prpr();\n\tfor(int i=1;i&lt;=n;++i){\n\t\tif(!vis[i]){\n\t\t\tdep[i]=1;\n\t\t\tTR.ADD(0,i,a[i].val);\n\t\t\tdfs0(i);\n\t\t}\n\t}\n\/\/\tfor(int i=1;i&lt;n;++i){\n\/\/\t\tprintf(\"%d:\",i);\n\/\/\t\tTR.pt(i);\n\/\/\t\tputs(\"\");\n\/\/\t}\n\tint lans=0,x,lc;\n\tchar ch[10];\n\tfor(int i=1;i&lt;=q;++i){\n\t\tcin>>ch+1;\n\t\tswitch(ch[1]){\n\t\t\tcase 'Q':{\n\t\t\t\tscanf(\"%d%d%d\",&amp;u,&amp;v,&amp;x);\n\t\t\t\tu^=lans,v^=lans,x^=lans;\n\t\t\t\tlc=lca(u,v);\n\/\/\t\t\t\tprintf(\"\\t\\t\\t%d %d %d\\n\",u,v,x);\n\t\t\t\tprintf(\"%d\\n\",lans=loc[TR.QRY(fa[lc][0],u,lc,v,x)]);\n\t\t\t\tbreak; \n\t\t\t}\n\t\t\tcase 'L':{\n\t\t\t\tscanf(\"%d%d\",&amp;u,&amp;v);\n\t\t\t\tu^=lans,v^=lans;\n\/\/\t\t\t\tprintf(\"\\t\\t\\t%d %d\\n\",u,v);\n\t\t\t\tif(szq(u)>szq(v)){\n\t\t\t\t\tu^=v^=u^=v;\n\t\t\t\t}\n\t\t\t\tuni(u,v);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t}\n}\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u6211\u4eec\u53d1\u73b0\uff0c\u6811\u4e0a\u7684\u94fe\u4e0a\u7b2ck\u5927\u662f\u53ef\u4ee5\u4f7f\u7528\u4e3b\u5e2d\u6811\u6765\u7ef4\u62a4\u7684\u3002\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u8282\u70b9\uff0c\u6211\u4eec\u4ece\u5b83\u7684\u7236\u4eb2\u590d\u5236\u4e00\u4e2a\u7248\u672c\uff0c\u7136\u540e\u6bcf\u4e00\u6b21\u6c42\u51fa &hellip; <\/p>\n<p class=\"link-more\"><a href=\"http:\/\/SmokeyDays.top\/wordpress\/2019\/10\/01\/lp3302-sdoi2013-%e6%a3%ae%e6%9e%97\/\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">\u201clp3302 SDOI2013 \u68ee\u6797\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":[79,30,43,49,72,56,70,9,6,48,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/930"}],"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=930"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/930\/revisions"}],"predecessor-version":[{"id":931,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/930\/revisions\/931"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=930"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=930"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=930"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}