{"id":32,"date":"2016-05-04T18:06:12","date_gmt":"2016-05-04T10:06:12","guid":{"rendered":"http:\/\/tyswly.com\/?p=32"},"modified":"2016-05-04T18:06:12","modified_gmt":"2016-05-04T10:06:12","slug":"cogs-36%e4%bc%98%e9%9b%85%e7%9a%84%e7%ba%bf%e6%ae%b5%e6%a0%91%ef%bc%88%e6%b1%82%e5%92%8c%e9%97%ae%e9%a2%98%ef%bc%89","status":"publish","type":"post","link":"https:\/\/tys.fun\/?p=32","title":{"rendered":"[COGS 36]\u4f18\u96c5\u7684\u7ebf\u6bb5\u6811\uff08\u6c42\u548c\u95ee\u9898\uff09"},"content":{"rendered":"<p>\u9898\u9762\u89c1<a href=\"http:\/\/cogs.pro\/cogs\/problem\/problem.php?pid=36\">COGS<\/a><br \/>\n\u5206\u6790\uff1a\u8fd9\u9053\u9898\uff0c\u53c8\u53cc\u53d2\u53d5\u662f\u533a\u95f4\u64cd\u4f5c\uff0c\u679c\u65ad\u7ebf\u6bb5\u6811\u554a\u3002\u521a\u521a\u8ddf\u67d0\u4eba@dch\u63a2(si)\u8ba8(bi)\u5173\u4e8e\u7ebf\u6bb5\u6811\u5927\u6cd5\u597d\u8fd8\u662f\u4e8c\u53c9\u7d22\u5f15\u6811\u5927\u6cd5\u597d\u7684\u95ee\u9898\uff0c\u80af\u5b9a\u7ebf\u6bb5\u6811\u5927\u6cd5\u597d\u5566\uff01\uff01\uff01<br \/>\n\u8bdd\u8bf4\u4e8c\u53c9\u7d22\u5f15\u6811\u662f\u4ec0\u4e48\u9b3c\u5566\uff0c\u592a\u96be\u4e86\uff0c%dch\uff0c%jjq\u3002<br \/>\n\u7ebf\u6bb5\u6811\u5927\u6cd5\u597d\uff01\uff01\uff01<\/p>\n<pre class=\"lang:c++ decode:true\">#include &lt;iostream&gt;\n#include &lt;cstdio&gt;\n#define LL long long\nusing namespace std;\nconst int MX = 10005;\nint n, m;\nint num[MX];\nstruct node{\n\tint le, ri;\n\tLL sum;\n}tree[MX*4];\ninline int leftt(int a)\n{\n\treturn a&lt;&lt;1;\n}\ninline int rightt(int a)\n{\n\treturn (a&lt;&lt;1)^1;\n}\ninline int mid(int a,int b)\n{\n\treturn (a+b)&gt;&gt;1;\n}\nvoid biu(int cur,int l,int r)\n{\/\/\u5efa\u6811\n\tif(l==r)\n\t{\n\t\ttree[cur].sum=num[l];\n\t\ttree[cur].le=tree[cur].ri=l;\n\t\treturn;\n\t}\n\telse\n\t{\n\t\tbiu(leftt(cur),l,mid(l,r));\n\t\tbiu(rightt(cur),mid(l,r)+1,r);\n\t\ttree[cur].sum=tree[leftt(cur)].sum+tree[rightt(cur)].sum;\n\t\ttree[cur].le=l;\n\t\ttree[cur].ri=r;\n\t}\n\treturn;\n}\ninline LL ask(int cur, int l, int r)\n{\/\/\u67e5\u8be2\n\tif(l==tree[cur].le&amp;&amp;r==tree[cur].ri)\n\t{\n\t\treturn tree[cur].sum;\n\t}\n\telse\n\t{\n\t\tif(r&lt;=tree[leftt(cur)].ri)\n\t\t\treturn ask(leftt(cur),l,r);\n\t\telse if(l&gt;=tree[rightt(cur)].le)\n\t\t\treturn ask(rightt(cur),l,r);\n\t\telse\n\t\t\treturn ask(leftt(cur),l,tree[leftt(cur)].ri)+ask(rightt(cur),tree[rightt(cur)].le,r);\n\t}\n}\ninline int get_num()\n{\n\tint ans=0;\n\tchar tmp;\n\ttmp=getchar();\n\twhile(tmp&lt;'0'||tmp&gt;'9')\ttmp=getchar();\n\twhile(tmp&lt;='9'&amp;&amp;tmp&gt;='0')\n\t{\n\t\tans=ans*10+tmp-48;\n\t\ttmp=getchar();\n\t}\n\treturn ans;\n}\nint main()\n{\n\t\/\/freopen(\"sum.in\",\"r\",stdin);\n\t\/\/freopen(\"sum.out\",\"w\",stdout);\n\tint x, y;\n\tn=get_num();\n\tLL tmp=0;\n\tfor(int i=1;i&lt;=n;i++)\n\t{\n\t\tscanf(\"%d\",&amp;num[i]);\n\t}\n\tbiu(1,1,n);\n\tm=get_num();\n\tfor(int i=1;i&lt;=m;i++)\n\t{\n\t\tx=get_num();\n\t\ty=get_num();\n\t\ttmp=ask(1,x,y);\n\t\tcout&lt;&lt;tmp&lt;&lt;\"\\n\";\n\t}\n\treturn 0;\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u9762\u89c1COGS \u5206\u6790\uff1a\u8fd9\u9053\u9898\uff0c\u53c8\u53cc\u53d2\u53d5\u662f\u533a\u95f4\u64cd\u4f5c\uff0c\u679c\u65ad\u7ebf\u6bb5\u6811\u554a\u3002\u521a\u521a\u8ddf\u67d0\u4eba@dch\u63a2(si)\u8ba8(bi)\u5173\u4e8e\u7ebf\u6bb5 &hellip; <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[],"class_list":["post-32","post","type-post","status-publish","format-standard","hentry","category-report"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts\/32","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=32"}],"version-history":[{"count":0,"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts\/32\/revisions"}],"wp:attachment":[{"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=32"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=32"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=32"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}