{"id":282,"date":"2019-10-04T09:31:56","date_gmt":"2019-10-04T01:31:56","guid":{"rendered":"https:\/\/blog.chtholly.moe\/?p=282"},"modified":"2021-08-21T18:13:28","modified_gmt":"2021-08-21T10:13:28","slug":"%e5%8f%af%e6%8c%81%e4%b9%85%e5%8c%96%e7%ba%bf%e6%ae%b5%e6%a0%911","status":"publish","type":"post","link":"https:\/\/blog.sukasuka.cn\/?p=282","title":{"rendered":"\u53ef\u6301\u4e45\u5316\u6570\u7ec4(Low\u53ef\u6301\u4e45\u5316\u7ebf\u6bb5\u6811)"},"content":{"rendered":"<p><!--more--><\/p>\n<pre>#include&lt;cstdio&gt;\r\n#define MAXN 15000000\r\n\/\/15\u500d\u7a7a\u95f4...\r\nstruct node {\r\n\tint l,r,val;\r\n} tree[MAXN];\r\nint sav[15000000],M,N;\r\nint top,root[15000000];\r\nint New(int n) {\r\n\t\/\/\u6ce8\u610f:n\u8282\u70b9\u5148\u88ab\u590d\u5236\u518d\u88ab\u91cd\u65b0\u8d4b\u503c(return)\r\n\ttop++;\/\/top\u5b58\u50a8\u65b0\u8282\u70b9\u7684\u4f4d\u7f6e \r\n\ttree[top]=tree[n];\r\n\treturn top;\r\n}\r\nint make_tree(int n,int l,int r) {\r\n\tn=++top;\/\/\u83b7\u53d6\u5b58\u8282\u70b9\u7684\u4f4d\u7f6e \r\n\tif(l==r) {\r\n\t\ttree[n].val=sav[l];\r\n\t\treturn n;\r\n\t}\r\n\tint mid=(l+r)&gt;&gt;1;\r\n\ttree[n].l=make_tree(tree[n].l,l,mid);\r\n\ttree[n].r=make_tree(tree[n].r,mid+1,r);\r\n\treturn n; \r\n}\r\nint update(int n,int l,int r,int target,int val) {\r\n\tn=New(n);\/\/\u5efa\u65b0\u6811,n\u5148\u88ab\u590d\u5236\u518d\u88ab\u91cd\u65b0\u8d4b\u503c \r\n\tif(l==r) {\r\n\t\ttree[n].val=val;\/\/Target Reached \r\n\t} else {\r\n\t\tint mid=(l+r)&gt;&gt;1;\r\n\t\tif(target&lt;=mid) {\/\/\u9700\u8981\u5c31\u5efa\u7acb\u65b0\u6811 \r\n\t\t\ttree[n].l=update(tree[n].l,l,mid,target,val);\r\n\t\t} else {\r\n\t\t\ttree[n].r=update(tree[n].r,mid+1,r,target,val);\r\n\t\t}\r\n\t}\r\n\treturn n;\/\/\u65b0(\u5b50)\u6811\u7684root \r\n}\r\nint query(int n,int l,int r,int target) {\r\n\tif(l==r)return tree[n].val;\r\n\tint mid=(l+r)&gt;&gt;1;\r\n\tif(target&lt;=mid) {\r\n\t\treturn query(tree[n].l,l,mid,target);\r\n\t} else {\r\n\t\treturn query(tree[n].r,mid+1,r,target);\r\n\t}\r\n}\r\nint read() {\r\n\tint x=0,f=1;\r\n\tchar ch;\r\n\tdo {\r\n\t\tch=getchar();\r\n\t\tif(ch=='-')f=-1;\r\n\t} while(ch&lt;'0'||ch&gt;'9');\r\n\tdo {\r\n\t\tx=10*x+ch-'0';\r\n\t\tch=getchar();\r\n\t} while(ch&gt;='0'&amp;&amp;ch&lt;='9');\r\n\treturn f*x;\r\n}\r\nint main() {\r\n\tN=read(),M=read();\r\n\tfor(int i=1;i&lt;=N;i++)sav[i]=read();\r\n\troot[0]=make_tree(0,1,N);\/\/root[i]\u5b58\u50a8\u7248\u672ci\u7684\u6811\u6839 \r\n\tfor(int i=1;i&lt;=M;i++){\r\n\t\t\/\/\u5bf9\u4e8el,r\u7684\u95ee\u9898:l,r\u53ea\u7528\u4e8e\u4fee\u6539\/\u67e5\u8be2\u65f6,\u4f20\u9012\u8282\u70b9\u7684\u63a7\u5236\u8303\u56f4(log2) \r\n\t\t\/\/update(n,,,,)\/query(n,,,)\u4e2d\u7684n\u521d\u59cb\u662f\u6811\u6839,\u4f20\u9012\u4e2d\u662f\u5b50\u6811\u6811\u6839 \r\n\t\tint ver=read(),d=read();\r\n\t\tif(d==1){\r\n\t\t\tint x=read(),val=read();\r\n\t\t\troot[i]=update(root[ver],1,N,x,val);\r\n\t\t\t\/\/\u65b0\u8282\u70b9\u662f\u8001\u8282\u70b9\u7684update\r\n\t\t}else{\r\n\t\t\tint loc=read();\r\n\t\t\tprintf(\"%dn\",query(root[ver],1,N,loc));\r\n\t\t\troot[i]=root[ver];\/\/\u672a\u6539\u52a8,\u7ee7\u627f\u4e0a\u4e00\u9897\u7ebf\u6bb5\u6811 \r\n\t\t}\r\n\t}\r\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-282","post","type-post","status-publish","format-standard","hentry","category-cpp"],"_links":{"self":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/282","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=282"}],"version-history":[{"count":3,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/282\/revisions"}],"predecessor-version":[{"id":974,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/282\/revisions\/974"}],"wp:attachment":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=282"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=282"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=282"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}