{"id":632,"date":"2020-12-02T21:41:48","date_gmt":"2020-12-02T13:41:48","guid":{"rendered":"https:\/\/blog.sukasuka.cn\/?p=632"},"modified":"2021-08-21T18:13:13","modified_gmt":"2021-08-21T10:13:13","slug":"c-ext-rope-%e4%bd%bf%e7%94%a8%e7%ac%94%e8%ae%b0","status":"publish","type":"post","link":"https:\/\/blog.sukasuka.cn\/?p=632","title":{"rendered":"C++ ext rope \u4f7f\u7528\u7b14\u8bb0"},"content":{"rendered":"<div class=\"hcb_wrap\">\n<pre class=\"prism line-numbers lang-cpp\" data-lang=\"C++\"><code>#include&lt;ext\/rope&gt; \/\/\u5305\u542b\u5934\r\ntypedef __gnu_cxx::rope&lt;int&gt; rp; \/\/\u540d\u79f0\u7a7a\u95f4\r\n\/*\r\nrope\u53ef\u4ee5\u5b9e\u73b0\r\n1.\u53ef\u6301\u4e45\u5316\u6570\u7ec4\r\n2.\u9ad8\u6548\u533a\u95f4\u7ffb\u8f6c\r\n\u64cd\u4f5c\r\ntest.push_back(x);\/\/\u5728\u672b\u5c3e\u6dfb\u52a0x\r\ntest.insert(pos,x);\/\/\u5728pos\u63d2\u5165x\r\ntest.erase(pos,x);\/\/\u4ecepos\u5f00\u59cb\u5220\u9664x\u4e2a\r\ntest.copy(pos,len,x);\/\/\u4ecepos\u5f00\u59cb\u5230pos+len\u4e3a\u6b62\u7528x\u4ee3\u66ff\r\ntest.replace(pos,x);\/\/\u5c06pos\u6362\u6210x\r\ntest.substr(pos,x);\/\/\u63d0\u53d6pos\u5f00\u59cbx\u4e2a\r\ntest.at(x)\/[x];\/\/\u8bbf\u95ee\u7b2cx\u4e2a\u5143\u7d20\r\n\u7b97\u6cd5\u590d\u6742\u5ea6n*sqrt(n)\u53ef\u4ee5\u5b9e\u73b0\u5feb\u901f\u7684\u63d2\u5165\u3001\u5220\u9664\u548c\u67e5\u627e\r\n*\/ \r\n\/\/1.\u53ef\u6301\u4e45\u5316\u5e76\u67e5\u96c6\r\nint find(int x,rp *ver) {\r\nif(x==ver-&gt;at(x))return x;\r\nint t=find(ver-&gt;at(x),ver);\r\nif(t!=ver-&gt;at(x))ver-&gt;replace(x,t);\r\nreturn ver-&gt;at(x);\r\n}\r\nvoid merge(int x,int y,rp*ver){\r\nx=find(x,ver),y=find(y,ver);\r\nif(x!=y)ver-&gt;replace(x,y);\r\n}\r\nint main() {\r\nn=read(),m=read();\r\nrp **V=new rp*[n+3];\r\nV[0]=new rp();\r\nfor(int i=0; i&lt;=n; i++)V[0]-&gt;push_back(i);\r\nfor(int i=1; i&lt;=m; i++) {\r\nV[i]=new rp(*V[i-1]);\/\/\u4e00\u5b9a\u6ce8\u610f\u8fd9\u91cc\u662fnew\u8001\u8282\u70b9 \r\nint o=read();\r\nif(o==1)merge(read(),read(),V[i]);\r\nelse if(o==2)V[i]=new rp(*V[read()]);\r\nelse puts(find(read(),V[i])==find(read(),V[i])?\"1\":\"0\");\r\n}\r\nreturn 0;\r\n}\r\n\r\n\/\/2.\u533a\u95f4\u7ffb\u8f6c\r\nvoid rev(int r,int l) {\r\nif(l&gt;r)std::swap(l,r);\r\nr++;\r\nrop tmp=s.substr(s.begin()+l,s.begin()+r);\r\ns=s.substr(s.begin(),s.begin()+l)+rs.substr(rs.begin()+n-r,rs.begin()+n-l)+s.substr(s.begin()+r,s.end());\r\nrs=rs.substr(rs.begin(),n-r+rs.begin())+tmp+rs.substr(n - l + rs.begin(),rs.end());\r\n}\r\nint main() {\r\nn=read(),m=read();\r\nfor(int i=1; i&lt;=n; i++)s.append(i),rs.append(n-i+1);\r\nwhile(m--)rev(read()-1,read()-1);\r\nfor(int i=0; i&lt;n; i++)printf(\"%d \",s.at(i));\r\nreturn 0;\r\n}\r\n\/*\r\n\u6ce8\u610f\u5230STL\u7684begin\u53caend\u4e3a\u5de6\u95ed\u53f3\u5f00 r++ \r\n\u53cd\u8f6c\u533a\u95f4\u65f6 l r\u5747-- \r\n*\/<\/code><\/pre>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>#include&lt;ext\/rope&gt; \/\/\u5305\u542b\u5934 typedef __gnu_cxx::rope&#038; [&hellip;]<\/p>\n","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-632","post","type-post","status-publish","format-standard","hentry","category-cpp"],"_links":{"self":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/632","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=632"}],"version-history":[{"count":1,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/632\/revisions"}],"predecessor-version":[{"id":633,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/632\/revisions\/633"}],"wp:attachment":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=632"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=632"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=632"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}