{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e奇幻魔术师通常通过以下三种方法之一获得他们的能力:天生具备、通过学习和实践获得,或者从另一个存在那里获得,通常是某种神、精灵或恶魔。一些巫师被描述为拥有特殊的天赋,使他们与奇幻世界中无法学习魔法的绝大多数角色区分开来。\u003cbr\u003e\u003cbr\u003e魔术师、巫师、魔法师等称号的实践者在神话、民间故事和文学作品中出现,这些奇幻作品都源自这一背景。\u003cbr\u003e\u003cbr\u003e在中世纪的骑士浪漫故事中,巫师通常出现为一位智慧的老人,并充当导师的角色,亚瑟王故事中的梅林就是一个典型的例子。其他魔术师可能会出现为反派,对英雄表示敌意。\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/1e46bbeb5f1edd92de4f3dd0ffad9d7c?v\u003d1706325350\"\u003e\u003c/center\u003e \u003cbr\u003e\u003cbr\u003eMr. Zstu是一位魔术师,他有许多像多比一样的小精灵,每个小精灵都有魔力(也许是负的)。一天,Mr. Zstu想测试自己施展魔法的能力。他让小精灵站成一排,从位置1到位置n,并使用了两种魔法,变换魔法和查询魔法,前者是改变一个小精灵的能力,后者是获取给定区间内美丽子序列的最大和。美丽子序列是一个子序列,其中序列中所有相邻的小精灵位置的奇偶性都不同。你能像Mr. Zstu一样做到吗?\u003cbr\u003e \u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行是一个整数T,表示测试用例的数量。\u003cbr\u003e每个测试用例以两个整数n和m开头,表示小精灵的数量和Mr. Zstu使用魔法的次数。\u003cbr\u003e(n,m ≤ 100000)\u003cbr\u003e接下来一行有n个整数表示小精灵的魔力,魔力的取值范围在-1000000000和1000000000之间。\u003cbr\u003e接下来是m行,每行有三个整数,如下:\u003cbr\u003etype a b 描述一个魔法。\u003cbr\u003e如果type等于0,你应该输出区间[a,b]内美丽子序列的最大和。(1 ≤ a ≤ b ≤ n)\u003cbr\u003e如果type等于1,你应该将位置a的小精灵的魔力改为b。(1 ≤ a ≤ n, 1 ≤ b ≤ 1e9)\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个类型为0的查询,输出相应的答案。"}},{"title":"样例","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\u003e1\r\n1 1\r\n1\r\n0 1 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}