{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"Description","value":{"format":"HTML","content":"\u003cp\u003e 达达利亚是愚人众执行官末席——公子。公子想要盗取岩神——摩拉克斯的神之心,因此他需要在璃月港内引发元素乱流,吸引璃月七星的注意力。\u003c/p\u003e\n\u003cp\u003e 公子手下有n(1 ≤ n ≤ 50000)个愚人众士兵,潜伏的位置分别为1, 2, …, n。每个愚人众士兵能够引发的元素乱流是a\u003csub\u003ei\u003c/sub\u003e,由于愚人众士兵装备有邪眼,所以他们对元素的控制力不稳定,有些士兵能引发的元素乱流是负的(-10000 ≤ a\u003csub\u003ei\u003c/sub\u003e ≤ 10000)。\u003c/p\u003e\n\u003cp\u003e 作为旅行者的你得知了这一点,将情报告知了玉衡星刻晴。\u003c/p\u003e\n\u003cp\u003e 拥有星斗归位能力的刻晴非常擅长清除元素乱流。当刻晴投射雷之楔,然后发动星斗归位向雷之楔瞬移时,她可以瞬间清除开始位置到结束位置路径上所有的元素乱流。\u003c/p\u003e\n\u003cp\u003e 刻晴知道作为旅行者的你十分聪明,她会先挑选好自己的行动范围[x, y](1 ≤ x ≤ y ≤ n),接下去问你,若发动星斗归位的移动路径不超过这个范围,能够清除的元素乱流之和最大是多少?\u003c/p\u003e\n\u003cp\u003e 公子也有自己的应对方法,他可以选定一个位置x,将x位置的元素乱流修改为y。\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e 第一行有一个整数 n,代表公子手下有 n 个愚人众士兵(潜伏位置 1, 2, ..., n)。\u003c/p\u003e\n\u003cp\u003e 接下来一行 n 个整数 a\u003csub\u003e1\u003c/sub\u003e, a\u003csub\u003e2\u003c/sub\u003e, ..., a\u003csub\u003en\u003c/sub\u003e 代表 n 个愚人众士兵初始设置的元素乱流分别是多少。\u003c/p\u003e\n\u003cp\u003e 第三行一个整数 m,代表接下来有 m 个操作(一共两种操作):\u003cbr\u003e\n 0 x y:公子将x位置的元素乱流修改成 y,保证 -10000 ≤ y ≤ 10000。\u003cbr\u003e\n 1 x y:刻晴询问在[x, y]范围内,用星斗归位能够清除的元素乱流之和最大是多少?\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e 对于每次刻晴的询问,输出一行一个整数,即能够清除的最大元素乱流之和。\u003cp\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\n4\n1 2 3 4\n4\n1 1 3\n0 3 -3\n1 2 4\n1 3 3\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\n6\n4\n-3\u003c/pre\u003e"}}]}