{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003e这个问题的内存限制(8兆字节)很不寻常!\u003c/span\u003e\u003c/p\u003e\u003cp\u003e爱丽丝和鲍勃正在玩尼姆游戏。在这个游戏中,有几堆石头,每堆可能包含多颗石头。两名玩家轮流移除石头。首先无法进行任何合法移动的玩家将输掉比赛。在每一步中,玩家可以选择一堆石头,然后从中移除一定数量的石头。\u003c/p\u003e\u003cp\u003e他们将在接下来的$$$n$$$天内玩$$$n$$$场游戏,每天一场。最初,没有任何石头堆。在第$$$i$$$天,将会发生一件事件,然后他们将开始新的一场游戏。爱丽丝总是先走,而双方玩家都会采取最优策略。鲍勃想要通过作弊赢得比赛。在每场比赛之前,鲍勃可以支付费用删除若干堆石头,使得爱丽丝永远无法赢得比赛。并且在每场比赛之后,鲍勃会将所有删除的石头堆恢复。\u003c/p\u003e\u003cp\u003e每天将会发生以下两种事件之一:\u003c/p\u003e\u003cul\u003e \u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eADD a[i] b[i]\u003c/span\u003e\"($$$1\\leq a[i]\u0026lt;16\\,384$$$,$$$1\\leq b[i]\\leq 100\\,000$$$):爱丽丝将一堆$$$a[i]$$$颗石头放在最右侧,这将花费鲍勃$$$b[i]$$$美元来删除它。\u003c/li\u003e\u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eDEL\u003c/span\u003e\":爱丽丝移除最右侧的一堆石头。保证这样的一堆石头始终存在。\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e你是鲍勃最好的朋友,请帮助鲍勃确定每场比赛应该删除哪些石头堆,以使总作弊成本最小化。请注意,鲍勃总是可以通过删除所有石头堆来获胜。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入仅包含一个测试用例。\u003c/p\u003e\u003cp\u003e输入的第一行包含一个整数$$$n$$$($$$1 \\leq n \\leq 40\\,000$$$),表示天数。\u003c/p\u003e\u003cp\u003e接下来的$$$n$$$行中,每行描述一个事件,其中第$$$i$$$行表示第$$$i$$$天发生的事件。\u003c/p\u003e\u003cp\u003e保证“\u003cspan class\u003d\"tex-font-style-tt\"\u003eADD\u003c/span\u003e”事件的数量永远不会超过$$$20\\,000$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出$$$n$$$行,其中第$$$k$$$行包含一个整数,表示鲍勃在第$$$k$$$天需要支付的最少美元数量。\u003c/p\u003e"}},{"title":"示例 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7\nADD 3 10\nADD 2 4\nADD 1 5\nADD 2 1\nDEL\nDEL\nADD 3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\n14\n0\n1\n0\n14\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}