{"id":317,"date":"2016-12-08T19:07:05","date_gmt":"2016-12-08T11:07:05","guid":{"rendered":"http:\/\/kylelv.com\/?p=317"},"modified":"2017-12-22T20:00:04","modified_gmt":"2017-12-22T12:00:04","slug":"bzoj-3224-tyvj-1728-%e6%99%ae%e9%80%9a%e5%b9%b3%e8%a1%a1%e6%a0%91","status":"publish","type":"post","link":"https:\/\/blog.kylelv.com\/?p=317","title":{"rendered":"bzoj 3224: Tyvj 1728 \u666e\u901a\u5e73\u8861\u6811"},"content":{"rendered":"<p><center><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_73 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69fdef758f655\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-69fdef758f655\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blog.kylelv.com\/?p=317\/#3224_Tyvj_1728_%E6%99%AE%E9%80%9A%E5%B9%B3%E8%A1%A1%E6%A0%91\" title=\"3224: Tyvj 1728 \u666e\u901a\u5e73\u8861\u6811\">3224: Tyvj 1728 \u666e\u901a\u5e73\u8861\u6811<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blog.kylelv.com\/?p=317\/#Description\" title=\"Description\">Description<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blog.kylelv.com\/?p=317\/#Input\" title=\"Input\">Input<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blog.kylelv.com\/?p=317\/#Output\" title=\"Output\">Output<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blog.kylelv.com\/?p=317\/#Sample_Input\" title=\"Sample Input\">Sample Input<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blog.kylelv.com\/?p=317\/#Sample_Output\" title=\"Sample Output\">Sample Output<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blog.kylelv.com\/?p=317\/#HINT\" title=\"HINT\">HINT<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/blog.kylelv.com\/?p=317\/#Source\" title=\"Source\">Source<\/a><\/li><\/ul><\/nav><\/div>\n<h2 style=\"text-align: center;\"><span class=\"ez-toc-section\" id=\"3224_Tyvj_1728_%E6%99%AE%E9%80%9A%E5%B9%B3%E8%A1%A1%E6%A0%91\"><\/span>3224: Tyvj 1728 \u666e\u901a\u5e73\u8861\u6811<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><span class=\"green\">Time Limit:\u00a010 Sec\u00a0\u00a0Memory Limit:\u00a0128 MB<\/span><\/center><\/p>\n<h2><span class=\"ez-toc-section\" id=\"Description\"><\/span>Description<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<p>\u60a8\u9700\u8981\u5199\u4e00\u79cd\u6570\u636e\u7ed3\u6784\uff08\u53ef\u53c2\u8003\u9898\u76ee\u6807\u9898\uff09\uff0c\u6765\u7ef4\u62a4\u4e00\u4e9b\u6570\uff0c\u5176\u4e2d\u9700\u8981\u63d0\u4f9b\u4ee5\u4e0b\u64cd\u4f5c\uff1a<br \/>\n1. \u63d2\u5165x\u6570<br \/>\n2. \u5220\u9664x\u6570(\u82e5\u6709\u591a\u4e2a\u76f8\u540c\u7684\u6570\uff0c\u56e0\u53ea\u5220\u9664\u4e00\u4e2a)<br \/>\n3. \u67e5\u8be2x\u6570\u7684\u6392\u540d(\u82e5\u6709\u591a\u4e2a\u76f8\u540c\u7684\u6570\uff0c\u56e0\u8f93\u51fa\u6700\u5c0f\u7684\u6392\u540d)<br \/>\n4. \u67e5\u8be2\u6392\u540d\u4e3ax\u7684\u6570<br \/>\n5. \u6c42x\u7684\u524d\u9a71(\u524d\u9a71\u5b9a\u4e49\u4e3a\u5c0f\u4e8ex\uff0c\u4e14\u6700\u5927\u7684\u6570)<br \/>\n6. \u6c42x\u7684\u540e\u7ee7(\u540e\u7ee7\u5b9a\u4e49\u4e3a\u5927\u4e8ex\uff0c\u4e14\u6700\u5c0f\u7684\u6570)<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Input\"><\/span>Input<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<p>\u7b2c\u4e00\u884c\u4e3an\uff0c\u8868\u793a\u64cd\u4f5c\u7684\u4e2a\u6570,\u4e0b\u9762n\u884c\u6bcf\u884c\u6709\u4e24\u4e2a\u6570opt\u548cx\uff0copt\u8868\u793a\u64cd\u4f5c\u7684\u5e8f\u53f7(1&lt;=opt&lt;=6)<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Output\"><\/span>Output<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<p>\u5bf9\u4e8e\u64cd\u4f5c3,4,5,6\u6bcf\u884c\u8f93\u51fa\u4e00\u4e2a\u6570\uff0c\u8868\u793a\u5bf9\u5e94\u7b54\u6848<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Sample_Input\"><\/span>Sample Input<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\"><span class=\"sampledata\">10<br \/>\n1 106465<br \/>\n4 1<br \/>\n1 317721<br \/>\n1 460929<br \/>\n1 644985<br \/>\n1 84185<br \/>\n1 89851<br \/>\n6 81968<br \/>\n1 492737<br \/>\n5 493598<br \/>\n<\/span><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Sample_Output\"><\/span>Sample Output<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\"><span class=\"sampledata\">106465<br \/>\n84185<br \/>\n492737<br \/>\n<\/span><\/div>\n<h2><span class=\"ez-toc-section\" id=\"HINT\"><\/span>HINT<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div class=\"content\">\n<p>&nbsp;<\/p>\n<div>1.n\u7684\u6570\u636e\u8303\u56f4\uff1an&lt;=100000<\/div>\n<div>2.\u6bcf\u4e2a\u6570\u7684\u6570\u636e\u8303\u56f4\uff1a[-1e7,1e7]<\/div>\n<div>\u6570\u636e\u5982\u4e0bhttp:\/\/pan.baidu.com\/s\/1jHMJwO2<\/div>\n<p>&nbsp;<\/p>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Source\"><\/span>Source<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<pre class=\"lang:c++ decode:true \">#include&lt;cstdio&gt;\r\n#include&lt;cstdlib&gt;\r\n#include&lt;iostream&gt;\r\nusing namespace std;\r\n#define N 100010\r\ninline int read()\r\n{\r\n    int tmp=0,pp=1;\r\n    char ch=getchar();\r\n    while(ch&lt;'0'||ch&gt;'9'){if(ch=='-')pp=-1; ch=getchar();}\r\n    while(ch&gt;='0'&amp;&amp;ch&lt;='9'){tmp=tmp*10+ch-'0';ch=getchar();}\r\n    return tmp*pp;\r\n}\r\nint op,x,ls[N],rs[N],w[N],a[N],siz[N],rnd[N],cnt,n,root,q,h;\r\ninline void pu(int p){siz[p]=siz[ls[p]]+siz[rs[p]]+w[p];}\r\ninline void lx(int &amp;p)\r\n{\r\n    int t=rs[p];\r\n    rs[p]=ls[t];\r\n    ls[t]=p;\r\n    pu(p);pu(t);\r\n    p=t;\r\n}\r\ninline void rx(int &amp;p)\r\n{\r\n    int t=ls[p];\r\n    ls[p]=rs[t];\r\n    rs[t]=p;\r\n    pu(p);pu(t);\r\n    p=t;\r\n}\r\ninline void cr(int &amp;p,int v)\r\n{\r\n    if(!p)\r\n    {\r\n        p=++cnt,a[p]=v,siz[p]=1,w[p]=1,rnd[p]=rand();\r\n        return;\r\n    }\r\n    if(v==a[p]) w[p]++;\r\n    else if(v&lt;a[p])\r\n    {\r\n        cr(ls[p],v);\r\n        if(rnd[ls[p]]&gt;rnd[p]) rx(p);\r\n    }\r\n    else\r\n    {\r\n        cr(rs[p],v);\r\n        if(rnd[rs[p]]&gt;rnd[p]) lx(p);\r\n    }\r\n    pu(p);\r\n}\r\ninline void del(int &amp;p,int v)\r\n{\r\n    if(!p) return;\r\n    if(v==a[p])\r\n    {\r\n        if(w[p]&gt;1) w[p]--;\r\n        else if(ls[p]*rs[p]==0) p=ls[p]+rs[p];\r\n        else if(rnd[ls[p]]&gt;rnd[rs[p]]) rx(p),del(p,v);\r\n        else lx(p),del(p,v);\r\n    }\r\n    else if(v&gt;a[p]) del(rs[p],v);\r\n    else del(ls[p],v);\r\n    pu(p);\r\n}\r\ninline int paim(int p,int v)\r\n{\r\n    if(v==a[p]) return siz[ls[p]]+1;\r\n    else if(v&gt;a[p]) return siz[ls[p]]+w[p]+paim(rs[p],v);\r\n    else return paim(ls[p],v);\r\n}\r\ninline int finx(int p,int v)\r\n{\r\n    if(siz[ls[p]]&gt;=v) return finx(ls[p],v);\r\n    else if(siz[ls[p]]+w[p]&gt;=v) return a[p];\r\n    else return finx(rs[p],v-siz[ls[p]]-w[p]);    \r\n}\r\ninline void qq(int p,int v)\r\n{\r\n    if(!p) return;\r\n    else if(v&gt;a[p])\r\n    {\r\n        q=a[p];\r\n        qq(rs[p],v);\r\n    }\r\n    else qq(ls[p],v);\r\n}\r\ninline void hj(int p,int v)\r\n{\r\n    if(!p) return;\r\n    else if(v&lt;a[p])\r\n    {\r\n        h=a[p];\r\n        hj(ls[p],v);\r\n    }\r\n    else hj(rs[p],v);\r\n}\r\nint main()\r\n{\r\n    n=read();\r\n    while(n--)\r\n    {\r\n        op=read();x=read();\r\n        if(op==1) cr(root,x);\r\n        else if(op==2) del(root,x);\r\n        else if(op==3) printf(\"%d\\n\",paim(root,x));\r\n        else if(op==4) printf(\"%d\\n\",finx(root,x));\r\n        else if(op==5){qq(root,x);printf(\"%d\\n\",q);}\r\n        else {hj(root,x);printf(\"%d\\n\",h);}\r\n    }\r\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>3224: Tyvj 1728 \u666e\u901a\u5e73\u8861\u6811 Time Limit:\u00a010 Sec\u00a0\u00a0Memory Limit: [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[18,19],"class_list":["post-317","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-treap","tag-19"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/317","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=317"}],"version-history":[{"count":1,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/317\/revisions"}],"predecessor-version":[{"id":318,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/317\/revisions\/318"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=317"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=317"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=317"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}