… \u7ed9\u5b9a\u4e00\u4e2a\u76f4\u7ebf\u5f62\u7684\u5730\u94c1\u7ad9\uff0c\u4e00\u5171 n \u7ad9\uff0c\u53ea\u80fd\u5411\u4e00\u4e2a\u65b9\u5411\u79fb\u52a8\u3002\u3002\u6bcf\u4e00\u7ad9\u5355\u7ad9\u4ef7\u683c\u662f\u4ece n \u5f00\u59cb\u6bcf\u6b21\u51cf 1\u3002
\n\u3002\u3002bug \u662f\u8fd9\u4e2a\u7cfb\u7edf\u53ef\u4ee5\u901a\u8fc7\u5728\u7ad9\u5185\u4ea4\u6362\u8f66\u7968\u6765\u8fbe\u5230 cheat \u7684\u6548\u679c\u3002\u3002
\n\u3002\u3002\u7ed9\u5b9a m \u4e2a\u8bf7\u6c42 l, r, p \u8868\u793a\u4ece l \u53d1\u51fa p \u4e2a\u5ba2\u6d41\u5012 r\u3002
\n\u3002\u3002\u95ee\u6574\u4e2a\u7cfb\u7edf\u6700\u591a\u4f1a\u635f\u5931\u591a\u5c11\uffe5\u3002\u3002\u3002
\n( n <= 1e9, m <= 1e3 .. )\n<\/p>\n
\u3002\u3002\u76f4\u63a5\u628a\u6bcf\u4e2a\u8bf7\u6c42\u62c6\u6210\u4e00\u4e2a\u5165\u4e8b\u4ef6\u4e00\u4e2a\u51fa\u4e8b\u4ef6\u6df7\u5728\u4e00\u8d77\u6392\u5e8f O(mlogm)\u3002\u3002\u4e4b\u540e\u63a5\u4e00\u4e2a\u6808\u626b\u4e00\u904d\u5c31\u884c\u4e86\u3002\u3002O(m)\u3002\u3002<\/p>\n
\r\n...\r\n stack<event> S; REP(i, 2*m){\r\n if (E[i].p > 0) S.push(E[i]);\r\n else {\r\n while (E[i].p){\r\n int d = min(S.top().p, -E[i].p);\r\n res -= f(E[i].x - S.top().x) * d;\r\n E[i].p += d, S.top().p -= d;\r\n if (!S.top().p) S.pop();\r\n }\r\n }\r\n }\r\n<\/pre>\n\u53c2\u8003\u4ee3\u7801\u3002\u3002<\/a>
\n\u3002\u3002\u6bd4\u8d5b\u65f6\u5019\u7684\u8bdd\u3002\u3002\u6700\u597d\u50cf Tourist \u4e00\u6837\u76f4\u63a5\u7206 O(m^2) \u7684\u3002\u3002\u3002<\/a><\/p>\nProblem B. Many Prizes<\/h2>\nBrief description: <\/h3>\n
… 2^n \u4e2a\u4eba\u8fdb\u884c n \u8f6e\u6dd8\u6c70\u8d5b\u3002\u95ee\uff1a
\n\u3002\u3002\u4e00\u5b9a\u8fdb\u524d p \u540d\u7684\u4eba\u6709\u591a\u5c11\u4e2a\u3002\u3002\u3002\u3002
\n\u3002\u3002\u53ef\u4ee5\u8fdb\u524d p \u540d\u7684\u4eba\u6709\u591a\u5c11\u4e2a\u3002\u3002<\/p>\n
Analysis: <\/h3>\n
\u3002f1(n, p) n \u4e2a\u4eba\u91cc\u6709\u591a\u5c11\u4eba\u4e00\u5b9a\u6392\u524d p \u540d\u3002
\n\u3002f2(n, p) n \u4e2a\u4eba\u91cc\u6709\u591a\u5c11\u4eba\u53ef\u80fd\u6392\u524d p \u540d\u3002<\/p>\n
\u3002\u3002\u4f3c\u4e4e\u6ca1\u6709\u4e8c\u5206\u7b54\u6848\u4ee5\u5916\u7684\u65b9\u6cd5\uff0c\u8bbe
\n\u3002ff1(n, p) n \u4e2a\u4eba\u91cc\u6392\u540d\u4e3a p \u7684\u4eba\uff0c\u7684 \u6700\u574f \u6392\u540d\u3002
\n\u3002ff2(n, p) n \u4e2a\u4eba\u91cc\u6392\u540d\u4e3a p \u7684\u4eba\uff0c\u7684 \u6700\u597d \u6392\u540d\u3002
\n\u8003\u8651 ff1 \u60c5\u51b5\u3002\u3002\u8fd9\u4e2a\u663e\u7136\u53ef\u4ee5\u9012\u5f52\u3002\u3002
\n\u3002\u3002\u6bcf\u4e00\u6b21\u90fd\u8981\u5c3d\u53ef\u80fd\u8fdb\u5165\u8d25\u8005\u7ec4\u3002\u3002
\n\u3002\u3002\u540c\u65f6\u3002\u3002\u8981\u5c3d\u53ef\u80fd\u591a\u7684\u8ba9\u9ad8\u540d\u6b21\u7684\u73a9\u5bb6\u4e5f\u8fdb\u5165\u8d25\u8005\u7ec4\u3002
\n\u3002\u3002\u65b9\u6cd5\u662f\u914d\u5bf9\u3002\u3002\u540c\u65f6\u9884\u7559\u51fa\u4e00\u4e2a\u53ef\u4ee5\u51fb\u8d25\u5f53\u524d\u73a9\u5bb6\u7684\u3002
\nff2 \u7684\u60c5\u51b5\u7c7b\u4f3c\uff0c\u4e0d\u8fc7\u662f\u8ba9\u540d\u6b21\u4f4e\u7684\u8fdb\u884c\u914d\u5bf9\u4ee5\u5c3d\u53ef\u80fd\u591a\u7684\u8fdb\u5165\u80dc\u8005\u7ec4\u3002<\/p>\n
\r\n...\r\nLL ff1(LL n, LL x){\r\n if (!x) return 0; \/\/ \u65e0\u6cd5\u8fdb\u5165\u8d25\u8005\u7ec4\r\n return n\/2 + ff1(n\/2, (x-1)\/2);\r\n}\r\n..\r\nLL ff2(LL n, LL x){\r\n if (x == n-1) return x; \/\/ \u65e0\u6cd5\u8fdb\u5165\u80dc\u8005\u7ec4\r\n return ff2(n\/2, n\/2-((n-x))\/2);\r\n}\r\n<\/pre>\nNote\uff1a
\n\u770b\u4e86\u9898\u89e3\u540e\u3002\u3002\u53d1\u73b0\u5176\u5b9e\u4e24\u4e2a\u95ee\u9898\u662f\u7d27\u5bc6\u8054\u7cfb\u7684\u3002\u3002<\/p>\n
Let’s begin by an observation that will make our life a bit easier: if we reverse all the team numbers (that is, team 0 becomes team 2^N-1, team 1 becomes team 2^N-2, etc.), without changing the tournament list. This will result in the final ranks of the teams also being reversed, since it’s relatively easy to see that all the records will be reversed (wins becoming losses and vice versa). This means that the problem of having a team rank as low as possible to get into the first P is equivalent to the problem of a team ranked as high as possible to get into the bottom P (or, in other words, not get into the top 2^N – P). Thus, if we are able to answer the question what is the lowest rank that can possibly get into the top P, we can run the same code to see what’s the lowest rank that can possibly be in the top 2^N – P, subtract one, and reverse, and this will be the lowest rank that will always get a prize. This means we only have to solve one problem \u2014 lowest ranked team guaranteed to be in the top P .. .<\/p><\/blockquote>\n
\u3002\u3002\u3002\u901a\u8fc7\u8fd9\u4e2a\u5173\u7cfb\u3002\u3002\u3002\u89e3\u51fa\u4efb\u610f\u4e00\u4e2a\u5c31\u884c\u4e86\uff08\u4e3b\u8981\u6b64\u65f6\u9700\u8981\u52a0\u989d\u5916\u7684\u4e00\u7ec4\u8fb9\u754c\u6761\u4ef6\uff09\u3002\u3002Orz\u3002\u3002\u3002
\n\u3002\u3002\u3002\u5e76\u4e14\u3002\u3002\u660e\u663e\u95ee\u98982 \u5176\u5b9e\u66f4\u5bb9\u6613\u4e9b\u3002\u3002\u3002<\/p>\n