{"id":381,"date":"2023-03-10T11:20:29","date_gmt":"2023-03-10T03:20:29","guid":{"rendered":"https:\/\/www.xgnd.net\/?p=381"},"modified":"2023-03-10T11:20:29","modified_gmt":"2023-03-10T03:20:29","slug":"p7252-jsoi2011-%e6%a3%92%e6%a3%92%e7%b3%96-%e9%a2%98%e8%a7%a3","status":"publish","type":"post","link":"https:\/\/www.xgnd.net\/index.php\/2023\/03\/10\/p7252-jsoi2011-%e6%a3%92%e6%a3%92%e7%b3%96-%e9%a2%98%e8%a7%a3\/","title":{"rendered":"P7252 [JSOI2011] \u68d2\u68d2\u7cd6 \u9898\u89e3"},"content":{"rendered":"<h2>\u9898\u610f\u7b80\u8ff0<\/h2>\n<p>\u6c42\u533a\u95f4\u4e25\u683c\u5927\u4e8e\u533a\u95f4\u957f\u5ea6\u4e00\u534a\u7684\u4f17\u6570\uff0c\u82e5\u4e0d\u5b58\u5728\u5219\u8f93\u51fa0\u3002<\/p>\n<p><del>\u8fd9\u4e0d\u5c31\u4e3b\u5e2d\u6811\u6a21\u677f\u9898\u561b<\/del><\/p>\n<h2>\u9898\u76ee\u5206\u6790<\/h2>\n<p>\u6c42\u533a\u95f4\u4f17\u6570\uff0c\u5176\u5b9e\u53ef\u4ee5\u5f88\u5bb9\u6613\u60f3\u5230\u4e3b\u5e2d\u6811\uff08\u5373\u53ef\u6301\u4e45\u5316\u6743\u503c\u7ebf\u6bb5\u6811\uff0c\u4e0d\u4f1a\u7684\u53ef\u4ee5\u5148\u53bb\u770b\u770b\u6a21\u677f\u9898<a href=\"https:\/\/www.luogu.com.cn\/problem\/P3834\">P3834<\/a>\uff09\u3002\u8fd9\u91cc\u7a0d\u5fae\u8bb2\u4e00\u4e0b\u4e3b\u5e2d\u6811\u7684\u57fa\u672c\u601d\u60f3\uff0c\u4ece\u5de6\u5230\u53f3\u6bcf\u63d2\u5165\u4e00\u4e2a\u6570 $a_i$ \u5c31\u4ea7\u751f\u4e00\u4e2a\u7248\u672c\u7684\u6743\u503c\u7ebf\u6bb5\u6811 $T_i$ \uff0c\u6743\u503c\u7ebf\u6bb5\u6811\u6bcf\u4e2a\u8282\u70b9\u4e0a\u8bb0\u5f55\u4e00\u4e2a\u503c $sum$ \uff0c\u8868\u793a\u8be5\u8282\u70b9\u5bf9\u5e94\u503c\u57df $[L,R]$ \u4e00\u5171\u63d2\u5165\u8fc7\u591a\u5c11\u6570\uff0c\u5373\u5728\u6b64\u7248\u672c\u7684\u6743\u503c\u7ebf\u6bb5\u6811 $T_i$ \u4e2d\u503c\u57df\u533a\u95f4 $[L,R]$ \u91cc\u6709\u591a\u5c11\u4e2a\u6570\u3002\u5904\u7406\u5b8c\u6240\u6709\u6570\u540e\uff0c\u7528\u7c7b\u4f3c\u524d\u7f00\u548c\u7684\u64cd\u4f5c\u5c06 $T<em>R$ \u7684 $sum$ \u51cf\u53bb $T<\/em>{L-1}$ \u7684 $sum$ \uff0c\u5373\u53ef\u6c42\u51fa\u503c\u57df\u533a\u95f4 $[L,R]$ \u7684\u6570\u7684\u4e2a\u6570\u3002<\/p>\n<p>\u57fa\u4e8e\u4ee5\u4e0a\u4e3b\u5e2d\u6811\u5904\u7406\u533a\u95f4\u7b2c k \u5c0f\u95ee\u9898\u7684\u57fa\u672c\u601d\u60f3\uff0c\u6211\u4eec\u5df2\u7ecf\u80fd\u6c42\u51fa\u4efb\u610f\u533a\u95f4\u7684\u6570\u7684\u4e2a\u6570\uff0c\u4f46\u9898\u76ee\u8981\u6c42\u7684\u662f\u533a\u95f4\u4e25\u683c\u5927\u4e8e\u533a\u95f4\u957f\u5ea6\u4e00\u534a\u7684\u4f17\u6570\uff0c\u8fd9\u8981\u600e\u4e48\u505a\u5462\uff1f<\/p>\n<p>\u5176\u5b9e\u5f88\u7b80\u5355\uff0c\u5bf9\u4e8e\u4e00\u4e2a\u6743\u503c\u7ebf\u6bb5\u6811\u7684\u8282\u70b9\uff0c\u5982\u679c\u5de6\u513f\u5b50\u7684\u6570\u7684\u4e2a\u6570\u6bd4\u603b\u6570\u4e00\u534a\u5927\uff0c\u90a3\u4e48\u6ee1\u8db3\u6761\u4ef6\u7684\u4f17\u6570\u5c31\u53ef\u80fd\u5728\u5de6\u513f\u5b50\u91cc\uff08\u4e5f\u53ef\u80fd\u6ca1\u6709\uff09\uff0c\u6b64\u65f6\u518d\u9012\u5f52\u627e\u5de6\u513f\u5b50\uff0c\u53f3\u513f\u5b50\u4e5f\u540c\u7406\u3002\u5982\u679c\u5de6\u53f3\u513f\u5b50\u7684\u6570\u7684\u4e2a\u6570\u90fd\u6bd4\u603b\u6570\u4e00\u534a\u5c0f\uff0c\u90a3\u663e\u7136\u5de6\u53f3\u513f\u5b50\u90fd\u4e0d\u5b58\u5728\u6ee1\u8db3\u6761\u4ef6\u7684\u4f17\u6570\u3002<\/p>\n<p>\u8981\u6ce8\u610f\u4e00\u70b9\uff0c\u5f53\u4e00\u4e2a\u8282\u70b9\u7684\u5de6\u513f\u5b50\u6ee1\u8db3\u6761\u4ef6\u65f6\uff0c\u4f17\u6570\u4e0d\u4e00\u5b9a\u5728\u5de6\u513f\u5b50\u91cc\uff0c\u53f3\u513f\u5b50\u4e5f\u53ef\u80fd\u6ee1\u8db3\u6761\u4ef6\uff0c\u6240\u4ee5\u4e24\u8fb9\u90fd\u8981\u5224\u65ad\u548c\u9012\u5f52\u67e5\u627e\u3002<\/p>\n<p>\u4e3b\u5e2d\u6811\u66f4\u65b0\u548c\u67e5\u627e\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u4e3a $O(n\\log n)$ \uff0c\u603b\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a $O((n+m)\\log n)$ \u3002<\/p>\n<h2>Code<\/h2>\n<pre><code class=\"language-cpp\">#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\ntypedef long long ll;\nconst int maxn=50005;\nint n,m,cnt,len,ans;\n\nstruct node{\n    int ls,rs,sum,zl;\n}tree[maxn&lt;&lt;5];\nint c[maxn],root[maxn];\n\n\/\/\u5efa\u6811\nint build(int l,int r){\n    int p=++cnt;\n    if(l==r){\n        tree[p].zl=1;\n        return p;\n    }\n    int mid=(l+r)&gt;&gt;1;\n    build(l,mid);\n    build(mid+1,r);\n\n    return p;\n}\n\n\/\/\u63d2\u5165\u64cd\u4f5c\nint update(int l,int r,int now,int val){\n    int p=++cnt;\n    tree[p]=tree[now];\n    tree[p].sum++;\n\n    if(l==r)return p;\n\n    int mid=(l+r)&gt;&gt;1;\n\n    if(val&lt;=mid)tree[p].ls=update(l,mid,tree[p].ls,val);\n    else tree[p].rs=update(mid+1,r,tree[p].rs,val);\n\n    return p;\n}\n\n\/\/\u8be2\u95ee\nvoid query(int l,int r,int p,int q,int k){\n    if(l==r){\n        ans=l;\n        return;\n    }\n\n    int m=(l+r)&gt;&gt;1;\n\n    int lx=tree[tree[p].ls].sum-tree[tree[q].ls].sum;   \/\/\u503c\u57df[l,m]\u4e0a\u6570\u7684\u4e2a\u6570\n    int rx=tree[tree[p].rs].sum-tree[tree[q].rs].sum;   \/\/\u503c\u57df[m+1,r]\u4e0a\u6570\u7684\u4e2a\u6570\n\n    if(lx&lt;=k and rx&lt;=k){    \/\/\u5982\u679c\u5de6\u53f3\u513f\u5b50\u7684\u6570\u7684\u4e2a\u6570\u90fd\u6bd4\u603b\u6570\u4e00\u534a\u5c0f\uff0c\u8bf4\u660e\u8be5\u533a\u95f4\u4e0a\u4e0d\u5b58\u5728\n        ans=0;\n        return;\n    }\n\n    if(lx&gt;k)query(l,m,tree[p].ls,tree[q].ls,k);     \/\/\u503c\u57df[l,m]\u4e0a\u6570\u7684\u4e2a\u6570\u5927\u4e8e\u603b\u6570\u4e00\u534a\uff0c\u5c31\u5c1d\u8bd5\u5728\u5de6\u8fb9\u627e\n\n    if(rx&gt;k)query(m+1,r,tree[p].rs,tree[q].rs,k);   \/\/\u503c\u57df[m+1,r]\u4e0a\u6570\u7684\u4e2a\u6570\u5927\u4e8e\u603b\u6570\u4e00\u534a\uff0c\u5c31\u5c1d\u8bd5\u5728\u53f3\u8fb9\u627e\n}\n\nint main(){\n    ios::sync_with_stdio(0);\n    cin&gt;&gt;n&gt;&gt;m;\n    for(int i=1;i&lt;=n;i++)cin&gt;&gt;c[i],len=max(len,c[i]);\n\n    root[0]=build(1,len);\n\n    for(int i=1;i&lt;=n;i++)root[i]=update(1,len,root[i-1],c[i]);\n\n    while(m--){\n        int l,r,k;\n        cin&gt;&gt;l&gt;&gt;r;\n        k=(r-l+1)&gt;&gt;1;\n        query(1,len,root[r],root[l-1],k);\n        cout&lt;&lt;ans&lt;&lt;endl;\n    }\n\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u610f\u7b80\u8ff0 \u6c42\u533a\u95f4\u4e25\u683c\u5927\u4e8e\u533a\u95f4\u957f\u5ea6\u4e00\u534a\u7684\u4f17\u6570\uff0c\u82e5\u4e0d\u5b58\u5728\u5219\u8f93\u51fa0\u3002 \u8fd9\u4e0d\u5c31\u4e3b\u5e2d\u6811\u6a21\u677f\u9898\u561b \u9898\u76ee\u5206\u6790 \u6c42\u533a\u95f4\u4f17\u6570\uff0c\u5176 [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,3,10],"tags":[],"class_list":["post-381","post","type-post","status-publish","format-standard","hentry","category-c","category-oi","category-10"],"_links":{"self":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts\/381","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/comments?post=381"}],"version-history":[{"count":0,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts\/381\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/media?parent=381"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/categories?post=381"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/tags?post=381"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}