{"id":796,"date":"2019-01-07T19:29:55","date_gmt":"2019-01-07T11:29:55","guid":{"rendered":"https:\/\/mnihyc.tk\/blog\/?p=796"},"modified":"2020-02-09T03:11:52","modified_gmt":"2020-02-08T19:11:52","slug":"2017-2018-petrozavodsk-wc-j-subsequence-sum-queries","status":"publish","type":"post","link":"https:\/\/0.mnihyc.com\/blog\/archives\/796","title":{"rendered":"[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries"},"content":{"rendered":"<h1 style=\"text-align: center;\">[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries<\/h1>\n<p style=\"text-align: center;\">\u65f6\u95f4\u9650\u5236\uff1a2000MS \u5185\u5b58\u9650\u5236\uff1a262144KB<\/p>\n<p style=\"text-align: center;\">\u96be\u5ea6\uff1a<span style=\"color: #ff9900;\">\\(5.2\\)<\/span><\/p>\n<ul>\n<li>\n<h3><strong>\u9898\u76ee\u63cf\u8ff0<\/strong><\/h3>\n<\/li>\n<\/ul>\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6\u4e3a \\(n\\) \u7684\u975e\u8d1f\u6574\u6570\u5e8f\u5217 \\(a\\) \u548c\u4e00\u4e2a\u6b63\u6574\u6570 \\(m\\) \u3002<\/p>\n<p>\u73b0\u5728\u6709 \\(q\\) \u7ec4\u8be2\u95ee\uff0c\u6bcf\u7ec4\u8be2\u95ee\u7ed9\u5b9a\u4e24\u4e2a\u6b63\u6574\u6570 \\(l, r\\) \uff0c\u6bcf\u6b21\u53ef\u4ee5\u9009\u62e9\u6ee1\u8db3 \\(l \\leq i \\leq r\\) \u7684\u82e5\u5e72\u4e2a \\(a_i\\) \uff08\u4e5f\u53ef\u4ee5\u4e00\u4e2a\u90fd\u4e0d\u9009\uff09\uff0c\u4f7f\u5f97\u8fd9\u4e9b \\(a_i\\) \u7684\u548c\u662f \\(m\\) \u7684\u975e\u8d1f\u6574\u6570\u500d\uff0c\u5e76\u8f93\u51fa\u6ee1\u8db3\u6761\u4ef6\u7684\u9009\u62e9\u65b9\u6848\u6570\u5bf9 \\(10^9+7\\) \u53d6\u6a21\u540e\u7684\u4f59\u6570\u3002<\/p>\n<ul>\n<li>\n<h3><strong>\u8f93\u5165\u683c\u5f0f<\/strong><\/h3>\n<\/li>\n<\/ul>\n<p>\u7b2c\u4e00\u884c\u4e3a\u4e24\u4e2a\u6b63\u6574\u6570 \\(n\\) \u548c \\(m\\) \u3002<\/p>\n<p>\u7b2c\u4e8c\u884c\u4e3a\u5e8f\u5217 \\(a\\) \uff0c\u5171 \\(n\\) \u4e2a\u5143\u7d20\uff0c\u7528\u4e00\u4e2a\u7a7a\u683c\u9694\u5f00\u3002<\/p>\n<p>\u7b2c\u4e09\u884c\u4e3a\u8be2\u95ee\u6570 \\(q\\) \u3002<\/p>\n<p>\u63a5\u4e0b\u6765\u7684 \\(q\\) \u884c\uff0c\u6bcf\u4e00\u884c\u90fd\u6709\u4e24\u4e2a\u6b63\u6574\u6570\uff0c\u5206\u522b\u4e3a \\(l\\) \u548c \\(r\\) \u3002<\/p>\n<ul>\n<li>\n<h3><strong>\u8f93\u51fa\u683c\u5f0f<\/strong><\/h3>\n<\/li>\n<\/ul>\n<p>\u5171 \\(q\\) \u884c\u3002<\/p>\n<p>\u7b2c \\(i\\) \u884c\u4e3a\u7b2c \\(i\\) \u7ec4\u8be2\u95ee\u7684\u7b54\u6848\u3002<\/p>\n<ul>\n<li>\n<h3><strong>\u6837\u4f8b\u8f93\u5165<\/strong><\/h3>\n<\/li>\n<\/ul>\n<pre class=\"\">4 3\r\n5 1 3 2\r\n4\r\n1 2\r\n1 3\r\n1 4\r\n2 4<\/pre>\n<ul>\n<li>\n<h3><strong>\u6837\u4f8b\u8f93\u51fa<\/strong><\/h3>\n<\/li>\n<\/ul>\n<pre class=\"\">2\r\n4\r\n6\r\n4<\/pre>\n<ul>\n<li>\n<h3><strong>\u6837\u4f8b\u8bf4\u660e<\/strong><\/h3>\n<\/li>\n<\/ul>\n<p>\u5bf9\u4e8e\u7b2c\u4e00\u7ec4\u8be2\u95ee \\(l=1, r=2\\) \uff0c\u6709 \u4e0d\u9009\u3001\u9009\u62e9 \\(5, 1\\) \uff0c\u5171 \\(2\\) \u79cd\u60c5\u51b5\u3002<\/p>\n<p>\u5bf9\u4e8e\u7b2c\u4e8c\u7ec4\u8be2\u95ee \\(l=1, r=3\\) \uff0c\u6709 \u4e0d\u9009\u3001\u9009\u62e9 \\(5, 1\\) \u3001\u9009\u62e9 \\(5, 1, 3\\) \u3001\u9009\u62e9 \\(3\\) \uff0c\u5171 \\(4\\) \u79cd\u60c5\u51b5\u3002<\/p>\n<p>\u5bf9\u4e8e\u7b2c\u4e09\u7ec4\u8be2\u95ee \\(l=1, r=4\\) \uff0c\u6709 \u4e0d\u9009\u3001\u9009\u62e9 \\(5, 1\\) \u3001\u9009\u62e9 \\(5, 1, 3\\) \u3001\u9009\u62e9 \\(3\\) \u3001\u9009\u62e9 \\(1, 2\\) \u3001\u9009\u62e9 \\(1, 3, 2\\) \uff0c\u5171 \\(6\\) \u79cd\u60c5\u51b5\u3002<\/p>\n<p>\u5bf9\u4e8e\u7b2c\u56db\u7ec4\u8be2\u95ee \\(l=2, r=4\\) \uff0c\u6709 \u4e0d\u9009\u3001\u9009\u62e9 \\(3\\) \u3001\u9009\u62e9 \\(1, 2\\) \u3001\u9009\u62e9 \\(1, 3, 2\\) \uff0c\u5171 \\(4\\) \u79cd\u60c5\u51b5\u3002<\/p>\n<ul>\n<li>\n<h3><strong>\u6570\u636e\u8303\u56f4<\/strong><\/h3>\n<\/li>\n<\/ul>\n<p>\u5bf9\u4e8e \\(10\\%\\) \u7684\u6570\u636e\uff0c\u6709 \\(1 \\leq n, q \\leq 10\\) \u3002<\/p>\n<p>\u5bf9\u4e8e \\(40\\%\\) \u7684\u6570\u636e\uff0c\u6709 \\(1 \\leq n, q \\leq 1000\\) \u3002<\/p>\n<p>\u5bf9\u4e8e \\(100\\%\\) \u7684\u6570\u636e\uff0c\u6709 \\(1 \\leq n, q \\leq 2 \\times 10^5\\)\uff0c\\(1 \\leq m \\leq 20\\)\uff0c\\(0 \\leq a_i \\leq 10^9\\) \u3002<\/p>\n<p>\u4fdd\u8bc1\u6bcf\u7ec4\u8be2\u95ee\u7684 \\(l, r\\) \u6ee1\u8db3 \\(1 \\leq l \\leq r \\leq n\\) \u3002<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>YZOJ P4199<\/p>\n<p>\\(Source\\): <a href=\"https:\/\/codeforces.com\/gym\/101741\/problem\/J\" data-cke-saved-href=\"https:\/\/codeforces.com\/gym\/101741\/problem\/J\">[2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest] J. Subsequence Sum Queries<\/a><\/p>\n<p><!--more--><\/p>\n<hr \/>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>\uff08\u6ce8\uff1a\u4ee5\u4e0b\u7684\u53d6\u6a21\u64cd\u4f5c\u5747\u5728<strong>\u975e\u8d1f\u6574\u6570<\/strong>\u610f\u4e49\u4e0b\u3002\uff09<\/p>\n<p>\u6700\u66b4\u529b\u7684\u505a\u6cd5\u5c31\u662f\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u8be2\u95ee\u7684\u533a\u95f4\u66b4\u529b\u505a\u4e00\u904d<strong>\u80cc\u5305\u8ba1\u6570<\/strong>\uff0c\u5bb9\u91cf\u5c31\u53d8\u6210 \\(\\bmod m\\) \u7684\u4f59\u6570 \\(0\\) ~ \\((m-1)\\) \u4e86\u3002\u8f6c\u79fb\u5c31\u662f <span style=\"color: #000000;\">\\(f_{i,<\/span> j}=f_{i-1, j}+f_{i-1, (j-a_i)\\%m}\\) \uff0c\u8868\u793a \\(a_i\\) \u4e0d\u9009\u548c\u9009\u7684\u60c5\u51b5\u6570\u4e4b\u548c\u3002\u8fd9\u6837\u7684\u590d\u6742\u5ea6\u53ef\u4ee5\u8fbe\u5230 \\(O(nmq)\\) \u662f\u65e0\u6cd5\u627f\u53d7\u7684\u3002<\/p>\n<p>\u8fd8\u53ef\u4ee5\u60f3\u5230\u7ebf\u6bb5\u6811\u8fdb\u884c\u80cc\u5305\u5408\u5e76\uff0c\u4f46\u662f\u8fd9\u6837\u7684\u590d\u6742\u5ea6\u4e3a \\(O((n+q)m^2logn)\\) \uff0c\u4f1a <span style=\"color: #ff00ff;\">TLE<\/span> \u3002<\/p>\n<p>\u6240\u4ee5\u60f3\u5230\u8fdb\u884c<strong>\u5206\u6cbb<\/strong>\u3002\uff08\u4ee5\u4e0b\u6240\u6709 \\(mid=\\lfloor\\frac{l+r}{2}\\rfloor\\)\uff09<\/p>\n<p>\u9996\u5148<strong>\u79bb\u7ebf<\/strong>\u5904\u7406\u8be2\u95ee\uff0c\u7136\u540e\u8003\u8651\u533a\u95f4 \\([l, r]\\) \u5982\u4f55\u5bf9\u8fd9\u4e2a\u8be2\u95ee\u4ea7\u751f\u8d21\u732e\u3002\u9996\u5148\uff0c\u5982\u679c\u8fd9\u4e2a\u8be2\u95ee\u533a\u95f4\u5b8c\u5168\u5728 \\([l, mid-1]\\) \u4e2d\uff0c\u90a3\u4e48\u5148<strong>\u4e0d\u7528\u5904\u7406<\/strong>\u5b83\uff0c\u5728\u9012\u5f52\u8fdb \\([l, mid-1]\\) \u65f6\u5904\u7406\u5c31\u597d\u4e86\uff08<strong>\u6ce8\u610f<\/strong>\uff0c\u533a\u95f4\u7aef\u70b9 \\(=mid\\) \u7684\u4f1a\u5728\u4e0b\u9762\u8fdb\u884c\u5904\u7406\uff09\u3002\u540c\u6837\u5982\u679c\u8fd9\u4e2a\u8be2\u95ee\u533a\u95f4\u5b8c\u5168\u5728 \\([mid+1, r]\\) \u4e2d\u4e5f\u662f\u540c\u7406\u3002<\/p>\n<p>\u5982\u679c\u8fd9\u4e2a\u8be2\u95ee\u533a\u95f4\u8de8\u8fc7\u4e86 \\(mid\\) \uff08\\(l \\leq ql \\leq mid \\leq qr \\leq r\\)\uff09\uff0c\u90a3\u4e48\u8fd9\u4e2a\u8be2\u95ee\u7684\u7b54\u6848\u5c31\u53ef\u4ee5\u88ab\u5904\u7406\u51fa\u6765\u3002\u6ce8\u610f\u56e0\u4e3a \\([l, r]\\) \u88ab\u5206\u5272\u6210\u4e86 \\([l, mid]\\) \u548c \\([mid+1, r]\\) \u8fd9\u4e24\u4e2a\u5b50\u533a\u95f4\uff0c\u6240\u4ee5\u8be2\u95ee\u533a\u95f4 \\([ql, qr]\\) \u4e5f\u53ef\u4ee5\u88ab\u5206\u5272\u6210\u4e24\u4e2a\u5b50\u533a\u95f4 \\([ql, mid]\\) \u548c \\([mid+1, qr]\\) \u3002\u8981\u5feb\u901f\u7684\u5408\u5e76\uff0c\u6240\u4ee5\u5bf9 \\([mid+1, r]\\) \u4e2d\u7684\u5143\u7d20\u505a\u4e00\u904d<strong>\u6b63\u5411DP<\/strong>\u8bbe\u5f97\u5230 \\(f\\) \u6570\u7ec4\uff0c\u5bf9 \\([l, mid]\\) \u4e2d\u7684\u5143\u7d20\u505a\u4e00\u904d<strong>\u53cd\u5411DP<\/strong>\u8bbe\u5f97\u5230 \\(g\\) \u6570\u7ec4\uff0c\u8fd9\u6837 \\(f\\) \u548c \\(g\\) \u5408\u5e76\u5c31\u53ef\u4ee5\u5f97\u5230\u8de8\u8fc7 \\(mid\\) \u7684\u4e00\u6bb5\u533a\u95f4\u7684\u5b8c\u6574\u7684\u7b54\u6848\u4e86\u3002\u5408\u5e76\u7684\u65f6\u5019\u5c31\u76f4\u63a5\u628a \\(f\\) \u4e2d\u7684\u65b9\u6848\u6570\u548c \\(g\\) \u4e2d\u7684\u65b9\u6848\u6570<strong>\u76f8\u4e58<\/strong>\u5373\u53ef\uff0c\u5373 \\([ql, qr]\\) \u8fd9\u4e2a\u8be2\u95ee\u7684\u7b54\u6848\u662f \\(\\sum\\limits_{j+k=m}{f_{qr, j} \\times g_{ql, k}}\\) \u3002<\/p>\n<p>\u8fd9\u6837\u5904\u7406\u4e0b\u53bb\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u53ea\u6709 \\(O(m(nlogn+q))\\) \u8db3\u4ee5\u901a\u8fc7\u672c\u9898\u3002<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:default decode:true\">#include &lt;cstdio&gt;\r\n#include &lt;cstdlib&gt;\r\n#include &lt;cstring&gt;\r\n#include &lt;climits&gt;\r\n\r\n#define MOD 1000000007\r\n\r\n#define MAXBFN 4194304\r\nchar buffer[MAXBFN+1],*S,*T; \r\ninline char GetChar()  \r\n{\r\n    if(S==T)\r\n    {\r\n        T=(S=buffer)+fread(buffer,1,MAXBFN,stdin);\r\n        if(S==T)return EOF;\r\n    }\r\n    return *S++;\r\n}\r\n\r\nchar pbuf[MAXBFN+1],*pp=pbuf;\r\ninline void PutChar(const char&amp;c)\r\n{\r\n    if(pp-pbuf==MAXBFN)\r\n\t\tfwrite(pbuf,1,MAXBFN,stdout),pp=pbuf;\r\n    *pp++=c;\r\n}\r\n\r\ninline void PrintNum(int a)\r\n{\r\n\tif(a&gt;9)\r\n\t\tPrintNum(a\/10);\r\n\tPutChar(a%10+'0');\r\n}\r\n\r\ninline int getnum()\r\n{\r\n\tregister char c=GetChar();\r\n\twhile(!(c&gt;='0' &amp;&amp; c&lt;='9'))\r\n\t\tc=GetChar();\r\n\tregister int a=0;\r\n\twhile(c&gt;='0' &amp;&amp; c&lt;='9')\r\n\t{\r\n\t\ta*=10;a+=c-'0';\r\n\t\tc=GetChar();\r\n\t}\r\n\treturn a;\r\n}\r\n\r\nint M;\r\nint a[205050];\r\n\r\nstruct _query\r\n{\r\n\tint ql,qr;\r\n\tint idx;\r\n}query[405050];\r\nint ans[205050];\r\n\r\nvoid Divide(int l,int r,int ql,int qr)\r\n{\r\n\tif(l&gt;r || ql&gt;qr)\r\n\t\treturn;\r\n\t\r\n\tregister int mid=(l+r)&gt;&gt;1;\r\n\tregister int nqlr=ql-1,nqrl=qr+1,nq=ql;\r\n\tstatic _query tquery[405050];\r\n\tfor(register int i=ql;i&lt;=qr;i++)\r\n\t\tif(query[i].qr&lt;mid)\r\n\t\t\ttquery[++nqlr]=query[i];\r\n\t\telse if(query[i].ql&gt;mid)\r\n\t\t\ttquery[--nqrl]=query[i];\r\n\t\telse\r\n\t\t\tquery[nq++]=query[i];\r\n\t\r\n\tstatic int f[205050][21];\r\n\tf[mid][0]=1;\r\n\tfor(register int j=1;j&lt;M;j++)\r\n\t\tf[mid][j]=0;\r\n\tfor(register int i=mid+1;i&lt;=r;i++)\r\n\t\tfor(register int j=0;j&lt;M;j++)\r\n\t\t\tf[i][j]=(f[i-1][j]+f[i-1][(j-a[i]+M)%M])%MOD;\r\n\t\r\n\tstatic int rf[205050][21];\r\n\trf[mid+1][0]=1;\r\n\tfor(register int j=1;j&lt;M;j++)\r\n\t\trf[mid+1][j]=0;\r\n\tfor(register int i=mid;i&gt;=l;i--)\r\n\t\tfor(register int j=0;j&lt;M;j++)\r\n\t\t\trf[i][j]=(rf[i+1][j]+rf[i+1][(j-a[i]+M)%M])%MOD;\r\n\t\r\n\tfor(register int i=ql;i&lt;nq;i++)\r\n\t{\r\n\t\tregister int tans=0;\r\n\t\tfor(register int j=0;j&lt;M;j++)\r\n\t\t\ttans=(tans+(long long)f[query[i].qr][j]*rf[query[i].ql][(M-j)%M]%MOD)%MOD;\r\n\t\tans[query[i].idx]=tans;\r\n\t}\r\n\t\r\n\tfor(register int i=ql;i&lt;=nqlr;i++)\r\n\t\tquery[i]=tquery[i];\r\n\tfor(register int i=nqrl;i&lt;=qr;i++)\r\n\t\tquery[i]=tquery[i];\r\n\t\r\n\tDivide(l,mid-1,ql,nqlr);\r\n\tDivide(mid+1,r,nqrl,qr);\r\n\t\r\n}\r\n\r\nint main()\r\n{\r\n\tregister int N=getnum();M=getnum();\r\n\tfor(register int i=1;i&lt;=N;i++)\r\n\t\ta[i]=getnum(),a[i]%=M;\r\n\tregister int Q=getnum();\r\n\tfor(register int i=1;i&lt;=Q;i++)\r\n\t{\r\n\t\tquery[i].ql=getnum(),query[i].qr=getnum();\r\n\t\tquery[i].idx=i;\r\n\t}\r\n\tDivide(1,N,1,Q);\r\n\tfor(register int i=1;i&lt;=Q;i++)\r\n\t\tPrintNum(ans[i]),PutChar('\\n');\r\n\tfwrite(pbuf,1,pp-pbuf,stdout);\r\n\treturn 0;\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries  &hellip; <a href=\"https:\/\/0.mnihyc.com\/blog\/archives\/796\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[36,38,40],"tags":[],"class_list":["post-796","post","type-post","status-publish","format-standard","hentry","category-harda","category-partition","category-bagdp"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.1.1 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries - mnihyc&#039;s Blog<\/title>\n<meta name=\"description\" content=\"J. Subsequence Sum Queries \u65f6\u95f4\u9650\u5236\uff1a2000MS \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6\u4e3a (n) \u7684\u975e\u8d1f\u6574\u6570\u5e8f\u5217 (a) \u548c\u4e00\u4e2a\u6b63\u6574\u6570 (m) \u3002 \u73b0\u5728\u6709 (q) \u7ec4\u8be2\u95ee\uff0c\u6bcf\u7ec4\u8be2\u95ee\u7ed9\u5b9a\u4e24\u4e2a\u6b63\u6574\u6570 (l, r) \uff0c\u6bcf\u6b21\u53ef\u4ee5\u9009\u62e9\u6ee1\u8db3 (l\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/0.mnihyc.com\/blog\/archives\/796\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries - mnihyc&#039;s Blog\" \/>\n<meta property=\"og:description\" content=\"J. Subsequence Sum Queries \u65f6\u95f4\u9650\u5236\uff1a2000MS \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6\u4e3a (n) \u7684\u975e\u8d1f\u6574\u6570\u5e8f\u5217 (a) \u548c\u4e00\u4e2a\u6b63\u6574\u6570 (m) \u3002 \u73b0\u5728\u6709 (q) \u7ec4\u8be2\u95ee\uff0c\u6bcf\u7ec4\u8be2\u95ee\u7ed9\u5b9a\u4e24\u4e2a\u6b63\u6574\u6570 (l, r) \uff0c\u6bcf\u6b21\u53ef\u4ee5\u9009\u62e9\u6ee1\u8db3 (l\" \/>\n<meta property=\"og:url\" content=\"https:\/\/0.mnihyc.com\/blog\/archives\/796\" \/>\n<meta property=\"og:site_name\" content=\"mnihyc&#039;s Blog\" \/>\n<meta property=\"article:published_time\" content=\"2019-01-07T11:29:55+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-02-08T19:11:52+00:00\" \/>\n<meta name=\"author\" content=\"mnihyc\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@mnihyc\" \/>\n<meta name=\"twitter:site\" content=\"@mnihyc\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"mnihyc\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/0.mnihyc.com\/blog\/archives\/796#article\",\"isPartOf\":{\"@id\":\"https:\/\/0.mnihyc.com\/blog\/archives\/796\"},\"author\":{\"name\":\"mnihyc\",\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\"},\"headline\":\"[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries\",\"datePublished\":\"2019-01-07T11:29:55+00:00\",\"dateModified\":\"2020-02-08T19:11:52+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/0.mnihyc.com\/blog\/archives\/796\"},\"wordCount\":196,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\"},\"articleSection\":[\"5.0 ~ 6.0\",\"\u5206\u6cbb\",\"\u80cc\u5305\"],\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/0.mnihyc.com\/blog\/archives\/796#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/0.mnihyc.com\/blog\/archives\/796\",\"url\":\"https:\/\/0.mnihyc.com\/blog\/archives\/796\",\"name\":\"[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries - mnihyc&#039;s Blog\",\"isPartOf\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/#website\"},\"datePublished\":\"2019-01-07T11:29:55+00:00\",\"dateModified\":\"2020-02-08T19:11:52+00:00\",\"description\":\"J. Subsequence Sum Queries \u65f6\u95f4\u9650\u5236\uff1a2000MS \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6\u4e3a \\\\(n\\\\) \u7684\u975e\u8d1f\u6574\u6570\u5e8f\u5217 \\\\(a\\\\) \u548c\u4e00\u4e2a\u6b63\u6574\u6570 \\\\(m\\\\) \u3002 \u73b0\u5728\u6709 \\\\(q\\\\) \u7ec4\u8be2\u95ee\uff0c\u6bcf\u7ec4\u8be2\u95ee\u7ed9\u5b9a\u4e24\u4e2a\u6b63\u6574\u6570 \\\\(l, r\\\\) \uff0c\u6bcf\u6b21\u53ef\u4ee5\u9009\u62e9\u6ee1\u8db3 \\\\(l\",\"breadcrumb\":{\"@id\":\"https:\/\/0.mnihyc.com\/blog\/archives\/796#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/0.mnihyc.com\/blog\/archives\/796\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/0.mnihyc.com\/blog\/archives\/796#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/mnihyc.com\/blog\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/mnihyc.com\/blog\/#website\",\"url\":\"https:\/\/mnihyc.com\/blog\/\",\"name\":\"mnihyc&#039;s Blog\",\"description\":\"Welcome!\",\"publisher\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/mnihyc.com\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"zh-Hans\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\",\"name\":\"mnihyc\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g\",\"caption\":\"mnihyc\"},\"logo\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/image\/\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries - mnihyc&#039;s Blog","description":"J. Subsequence Sum Queries \u65f6\u95f4\u9650\u5236\uff1a2000MS \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6\u4e3a (n) \u7684\u975e\u8d1f\u6574\u6570\u5e8f\u5217 (a) \u548c\u4e00\u4e2a\u6b63\u6574\u6570 (m) \u3002 \u73b0\u5728\u6709 (q) \u7ec4\u8be2\u95ee\uff0c\u6bcf\u7ec4\u8be2\u95ee\u7ed9\u5b9a\u4e24\u4e2a\u6b63\u6574\u6570 (l, r) \uff0c\u6bcf\u6b21\u53ef\u4ee5\u9009\u62e9\u6ee1\u8db3 (l","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/0.mnihyc.com\/blog\/archives\/796","og_locale":"zh_CN","og_type":"article","og_title":"[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries - mnihyc&#039;s Blog","og_description":"J. Subsequence Sum Queries \u65f6\u95f4\u9650\u5236\uff1a2000MS \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6\u4e3a (n) \u7684\u975e\u8d1f\u6574\u6570\u5e8f\u5217 (a) \u548c\u4e00\u4e2a\u6b63\u6574\u6570 (m) \u3002 \u73b0\u5728\u6709 (q) \u7ec4\u8be2\u95ee\uff0c\u6bcf\u7ec4\u8be2\u95ee\u7ed9\u5b9a\u4e24\u4e2a\u6b63\u6574\u6570 (l, r) \uff0c\u6bcf\u6b21\u53ef\u4ee5\u9009\u62e9\u6ee1\u8db3 (l","og_url":"https:\/\/0.mnihyc.com\/blog\/archives\/796","og_site_name":"mnihyc&#039;s Blog","article_published_time":"2019-01-07T11:29:55+00:00","article_modified_time":"2020-02-08T19:11:52+00:00","author":"mnihyc","twitter_card":"summary_large_image","twitter_creator":"@mnihyc","twitter_site":"@mnihyc","twitter_misc":{"\u4f5c\u8005":"mnihyc","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"3 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/0.mnihyc.com\/blog\/archives\/796#article","isPartOf":{"@id":"https:\/\/0.mnihyc.com\/blog\/archives\/796"},"author":{"name":"mnihyc","@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751"},"headline":"[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries","datePublished":"2019-01-07T11:29:55+00:00","dateModified":"2020-02-08T19:11:52+00:00","mainEntityOfPage":{"@id":"https:\/\/0.mnihyc.com\/blog\/archives\/796"},"wordCount":196,"commentCount":0,"publisher":{"@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751"},"articleSection":["5.0 ~ 6.0","\u5206\u6cbb","\u80cc\u5305"],"inLanguage":"zh-Hans","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/0.mnihyc.com\/blog\/archives\/796#respond"]}]},{"@type":"WebPage","@id":"https:\/\/0.mnihyc.com\/blog\/archives\/796","url":"https:\/\/0.mnihyc.com\/blog\/archives\/796","name":"[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries - mnihyc&#039;s Blog","isPartOf":{"@id":"https:\/\/mnihyc.com\/blog\/#website"},"datePublished":"2019-01-07T11:29:55+00:00","dateModified":"2020-02-08T19:11:52+00:00","description":"J. Subsequence Sum Queries \u65f6\u95f4\u9650\u5236\uff1a2000MS \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6\u4e3a \\(n\\) \u7684\u975e\u8d1f\u6574\u6570\u5e8f\u5217 \\(a\\) \u548c\u4e00\u4e2a\u6b63\u6574\u6570 \\(m\\) \u3002 \u73b0\u5728\u6709 \\(q\\) \u7ec4\u8be2\u95ee\uff0c\u6bcf\u7ec4\u8be2\u95ee\u7ed9\u5b9a\u4e24\u4e2a\u6b63\u6574\u6570 \\(l, r\\) \uff0c\u6bcf\u6b21\u53ef\u4ee5\u9009\u62e9\u6ee1\u8db3 \\(l","breadcrumb":{"@id":"https:\/\/0.mnihyc.com\/blog\/archives\/796#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/0.mnihyc.com\/blog\/archives\/796"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/0.mnihyc.com\/blog\/archives\/796#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/mnihyc.com\/blog"},{"@type":"ListItem","position":2,"name":"[2017-2018 Petrozavodsk WC] J. Subsequence Sum Queries"}]},{"@type":"WebSite","@id":"https:\/\/mnihyc.com\/blog\/#website","url":"https:\/\/mnihyc.com\/blog\/","name":"mnihyc&#039;s Blog","description":"Welcome!","publisher":{"@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/mnihyc.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"zh-Hans"},{"@type":["Person","Organization"],"@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751","name":"mnihyc","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g","caption":"mnihyc"},"logo":{"@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/image\/"}}]}},"_links":{"self":[{"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/posts\/796","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/comments?post=796"}],"version-history":[{"count":0,"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/posts\/796\/revisions"}],"wp:attachment":[{"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/media?parent=796"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/categories?post=796"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/tags?post=796"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}