{"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\"\u003eOs mágicos de fantasia geralmente adquirem sua habilidade por um dos três métodos usuais: possuindo-a como um talento inato, adquirindo-a através de estudo e prática, ou recebendo-a de outro ser, muitas vezes um deus, espírito ou demônio de algum tipo. Alguns magos são retratados como tendo um dom especial que os diferencia da grande maioria dos personagens em mundos de fantasia que são incapazes de aprender magia.\u003cbr\u003e\u003cbr\u003eMágicos, feiticeiros, magos, magi e praticantes de magia por outros títulos apareceram em mitos, contos populares e literatura ao longo da história registrada, com obras de fantasia se inspirando nesse background.\u003cbr\u003e\u003cbr\u003eNas romances medievais de cavalaria, o mago muitas vezes aparece como um sábio e age como mentor, com Merlin das histórias do Rei Arthur representando um exemplo primordial. Outros mágicos podem aparecer como vilões, hostis ao herói.\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\u003eO Sr. Zstu é um mágico, ele tem muitos elfos como Dobby, cada um dos quais tem um poder mágico (talvez negativo). Um dia, o Sr. Zstu quer testar sua habilidade de fazer alguma magia. Ele fez os elfos ficarem em uma linha reta, da posição 1 à posição n, e ele usou dois tipos de magia, a Magia de Mudança e a Magia de Consulta, a primeira é mudar o poder de um elfo, a segunda é obter a soma máxima de uma subsequência bonita de um intervalo dado. Uma subsequência bonita é uma subsequência em que todos os pares adjacentes de elfos na sequência têm paridade de posição diferente. Você consegue fazer a mesma coisa que o Sr. Zstu?\u003cbr\u003e \u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"A primeira linha é um inteiro T que representa o número de casos de teste.\u003cbr\u003eCada caso de teste começa com dois inteiros n, m que representam o número de elfos e o número de vezes que o Sr. Zstu usou sua magia.\u003cbr\u003e(n, m \u0026lt;\u003d 100000)\u003cbr\u003eA próxima linha tem n inteiros que representam o poder mágico dos elfos, o poder mágico está entre -1000000000 e 1000000000.\u003cbr\u003eSeguidos por m linhas, cada linha tem três inteiros como \u003cbr\u003etipo a b descrevem uma magia.\u003cbr\u003eSe o tipo for igual a 0, você deve imprimir a soma máxima da subsequência bonita do intervalo [a, b].(1 \u0026lt;\u003d a \u0026lt;\u003d b \u0026lt;\u003d n)\u003cbr\u003eSe o tipo for igual a 1, você deve mudar o poder mágico do elfo na posição a para b.(1 \u0026lt;\u003d a \u0026lt;\u003d n, 1 \u0026lt;\u003d b \u0026lt;\u003d 1e9)\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"Para cada consulta de tipo 0, imprima a resposta correspondente."}},{"title":"Sample","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"}}]}