{"id":523,"date":"2018-12-25T12:30:36","date_gmt":"2018-12-25T04:30:36","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=523"},"modified":"2018-12-25T12:30:36","modified_gmt":"2018-12-25T04:30:36","slug":"at1219-%e5%8e%86%e5%8f%b2%e7%a0%94%e7%a9%b6","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2018\/12\/25\/at1219-%e5%8e%86%e5%8f%b2%e7%a0%94%e7%a9%b6\/","title":{"rendered":"AT1219 \u5386\u53f2\u7814\u7a76"},"content":{"rendered":"\n

\u4e00\u9053\u56de\u6eda\u83ab\u961f\u7684\u4f8b\u9898\u3002
\n\u83ab\u961f\u7b97\u6cd5\u80fd\u591f\u89e3\u51b3\u5f88\u591a\u7c7b\u4f3c\u4e8e\u6c42\u548c\u7684\u8be2\u95ee\u95ee\u9898\u3002\u4f46\u662f\u5bf9\u4e8e\u6c42\u6700\u503c\u7684\u8be2\u95ee\u5b83\u65e0\u80fd\u4e3a\u529b\u3002\u8fd9\u662f\u56e0\u4e3a\u83ab\u961f\u9700\u8981\u4e00\u4e2a\u533a\u95f4\u65e2\u80fd\u591f\u62d3\u5c55\u53c8\u80fd\u591f\u6536\u7f29\u3002
\n\u5bf9\u4e8e\u6c42\u6700\u503c\u7c7b\u7684\u95ee\u9898\uff0c\u5b83\u53ea\u80fd\u591f\u62d3\u5c55\uff0c\u4e0d\u80fd\u591f\u6536\u7f29\u3002
\n\u8fd9\u65f6\u5019\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528\u4e00\u79cd\u88ab\u79f0\u4e3a\u300c\u56de\u6eda\u83ab\u961f\u300d\u7684\u7b97\u6cd5\u3002
\n\u5177\u4f53\u6765\u8bf4\uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u5757\u5185\u7684\u8be2\u95ee\uff0c\u6211\u4eec\u90fd\u5206\u6210\u4e24\u90e8\u5206\u6765\u5904\u7406\u3002\u4e00\u90e8\u5206\u662f\u5c06\u53f3\u7aef\u70b9\u63a8\u8fdb\uff0c\u53e6\u4e00\u90e8\u5206\u5219\u662f\u5c06\u5de6\u7aef\u70b9\u63a8\u8fdb\u3002\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u8be2\u95ee\uff0c\u6211\u4eec\u5728\u6c42\u5f97\u5b83\u5411\u53f3\u7aef\u70b9\u63a8\u8fdb\u7684\u503c\u4ee5\u540e\uff0c\u66b4\u529b\u7edf\u8ba1\u4e0a\u5de6\u7aef\u70b9\u5bf9\u5b83\u7684\u8d21\u732e\u5373\u53ef\u3002
\n\u8bf7\u6ce8\u610f\u56de\u6eda\u83ab\u961f\u4e0d\u80fd\u5947\u5076\u5206\u5757\u3002\u7ed3\u5408\u56de\u6eda\u83ab\u961f\u7684\u6027\u8d28\u53ef\u4ee5\u5f88\u5bb9\u6613\u7406\u89e3\u3002 <\/p>\n\n\n\n

#include<iostream>\n#include<cstdio>\n#include<cmath>\n#include<algorithm>\nint BLOCK,NUM;\nint bl[100005],lb[100005],rb[100005];\nstruct Query{\n\tint l;\n\tint r;\n\tint id;\n\tinline bool operator<(const Query &B)const{\n\t\treturn (bl[l]^bl[B.l])?(bl[l]<bl[B.l]):(r<B.r);\n\t}\n}q[100005];\nint n,m,a[100005],cnt1[100005],cnt2[100005],loc[100005],typ[100005];\nlong long ans[100005];\nvoid init(){\n\tscanf(\"%d%d\",&n,&m);\n\tBLOCK=std::sqrt(n);\n\tNUM=std::ceil((double)n\/BLOCK);\n\tfor(int i=1;i<=NUM;++i){\n\t\tlb[i]=BLOCK*(i-1)+1;\n\t\trb[i]=BLOCK*i;\n\t\tfor(int j=lb[i];j<=rb[i];++j){\n\t\t\tbl[j]=i;\n\t\t}\n\t}\n\trb[NUM]=n;\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%d\",a+i);\n\t\tloc[i]=a[i];\n\t}\n\tstd::sort(loc+1,loc+1+n);\n\tint tot=std::unique(loc+1,loc+1+n)-loc-1;\n\tfor(int i=1;i<=n;++i){\n\t\ttyp[i]=std::lower_bound(loc+1,loc+1+tot,a[i])-loc;\n\t}\n\tfor(int i=1;i<=m;++i){\n\t\tscanf(\"%d%d\",&q[i].l,&q[i].r);\n\t\tq[i].id=i;\n\t}\n\tstd::sort(q+1,q+1+m);\n\tint p=1;\n\tfor(int i=0;i<=NUM;++i){\n\t\tint l=rb[i]+1,r=rb[i];\n\t\tlong long nw=0;\n\t\tfor(int j=1;j<=n;++j){\n\t\t\tcnt1[j]=0;\n\t\t}\n\t\tfor(;bl[q[p].l]==i;++p){\n\t\t\tint ql=q[p].l,qr=q[p].r;\n\t\t\tlong long tmp=0;\n\t\t\tif(bl[ql]==bl[qr]){\n\t\t\t\tfor(int j=ql;j<=qr;++j){\n\t\t\t\t\tcnt2[typ[j]]=0;\n\t\t\t\t}\n\t\t\t\tfor(int j=ql;j<=qr;++j){\n\t\t\t\t\t++cnt2[typ[j]];\n\t\t\t\t\ttmp=std::max(tmp,1ll*cnt2[typ[j]]*a[j]);\n\t\t\t\t}\n\t\t\t\tans[q[p].id]=tmp;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\twhile(r<qr){\n\t\t\t\t++r;\n\t\t\t\t++cnt1[typ[r]];\n\t\t\t\tnw=std::max(nw,1ll*cnt1[typ[r]]*a[r]);\n\t\t\t}\n\t\t\ttmp=nw;\n\t\t\twhile(l>ql){\n\t\t\t\t--l;\n\t\t\t\t++cnt1[typ[l]];\n\t\t\t\tnw=std::max(nw,1ll*cnt1[typ[l]]*a[l]);\n\t\t\t}\n\t\t\tans[q[p].id]=nw;\n\t\t\twhile(l<rb[i]+1){\n\t\t\t\t--cnt1[typ[l]];\n\t\t\t\t++l;\n\t\t\t}\n\t\t\tnw=tmp;\n\t\t}\n\t}\n\tfor(int i=1;i<=m;++i){\n\t\tprintf(\"%lld\\n\",ans[i]);\n\t}\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u4e00\u9053\u56de\u6eda\u83ab\u961f\u7684\u4f8b\u9898\u3002 \u83ab\u961f\u7b97\u6cd5\u80fd\u591f\u89e3\u51b3\u5f88\u591a\u7c7b\u4f3c\u4e8e\u6c42\u548c\u7684\u8be2\u95ee\u95ee\u9898\u3002\u4f46\u662f\u5bf9\u4e8e\u6c42\u6700\u503c\u7684\u8be2\u95ee\u5b83\u65e0\u80fd\u4e3a\u529b\u3002\u8fd9\u662f\u56e0\u4e3a\u83ab\u961f\u9700 … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201cAT1219 \u5386\u53f2\u7814\u7a76\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":[13,68,73,6,69,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/523"}],"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=523"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/523\/revisions"}],"predecessor-version":[{"id":524,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/523\/revisions\/524"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=523"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=523"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=523"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}