{"problem":{"name":"「TERRA-OI R1」神，不惧死亡","description":{"content":"李子要在一个长度为 $n$ 的序列 $a$ 上玩游戏，他每次会把下标在 $[l,r]$ 范围内，且取值在 $[p,q]$ 范围内的所有数全部找出来，每次他可以选择其中两个相同的值，并进行**抵消**操作，将这两个数从数列中删除。当且仅当一个原本存在的值被消除掉后，所有值小于这个数的每个值全部要被删除一次（例如数列中原本有三个 $2$，进行一次删除后将会仅剩两个 $2$），并且这个游戏将会立即停止。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8930"},"statements":[{"statement_type":"Markdown","content":"李子要在一个长度为 $n$ 的序列 $a$ 上玩游戏，他每次会把下标在 $[l,r]$ 范围内，且取值在 $[p,q]$ 范围内的所有数全部找出来，每次他可以选择其中两个相同的值，并进行**抵消**操作，将这两个数从数列中删除。当且仅当一个原本存在的值被消除掉后，所有值小于这个数的每个值全部要被删除一次（例如数列中原本有三个 $2$，进行一次删除后将会仅剩两个 $2$），并且这个游戏将会立即停止。\n\n李子会不止一次的玩这个游戏，并且每次取的区间都不相同，而且，为了加大游戏难度，李子会时不时的修改序列中某个数的值。\n\n现在李子想让剩下的数列中的最小值尽可能大，需要请你针对每次游戏，输出这个最大的最小值。特别地，如果这个游戏无法停止或者存在一种方案可以消除整个数列，输出 $-1$。\n\n## Input\n\n第一行两个用空格分隔的正整数 $n,m$，含义见题目描述。\n\n第二行 $n$ 个用空格分隔的正整数，表示对应 $a$ 序列。\n\n第三行到第 $m+2$ 行，每行有以下两种情况：\n\n- $1$ $p$ $x$ 表示给 $a_p$ 的值加上 $x$。\n- $2$ $l$ $r$ $p$ $q$ 表示询问将下标属于 $[l,r]$，取值属于 $[p,q]$ 的数列取出进行游戏的结果。\n\n## Output\n\n针对每个询问 $2$，输出一行一个整数表示答案。\n\n[samples]\n\n## Background\n\n战斗已经到了白热化阶段，你已经精疲力竭，手臂因承受不住手中巨剑重量不住地发抖，噬神者的紫色外壳已经脱落大半，似乎再承受几次重击就会碎落一地。天空中紫色的迷雾开始变得暗淡，空间由于被不断撕裂而逐渐扭曲。在你的身前，噬神者最后一次撕开裂缝，用最原始的方式向你发起最后一击。你握紧手中的巨剑，准备迎接这最后一击，即使你清楚这是神明吞噬者最后的倔强，可你依然不敢放松一分一毫。最后一击过后，远处响起了钟声，战斗终将落下帷幕......\n\n## Note\n\n#### 【样例解释 #1】\n\n第一个询问对应的数列为 $[1,1,4,5,1,4]$，我们将两个 $1$ 先抵消，再抵消两个 $4$，此时比 $4$ 小的 $1$ 将会删除一次，整个序列只剩一个 $5$。\n\n第二个询问针对前 $4$ 个数，且由于 $5$ 不属于 $[1,4]$ 值域范围，所以数列为 $[1,1,4]$，将两个 $1$ 抵消后游戏直接结束，答案为 $4$。\n\n第三次修改将 $a_1$ 加 $1$，修改后数列为 $[2,1,4,5,1,4]$。\n\n第四次询问对应的数列为 $[2,1,4]$，所有数据都只出现一次，没办法进行抵消操作，游戏无法停止所以输出 $-1$。\n\n第五次询问的数列为 $[1,4,5,1,4]$，我们选择将两个 $1$ 抵消，由于数列中不再有 $1$，游戏结束，最小为 $4$。你也可以抵消两个 $4$，但这样答案为 $1$，比 $4$ 要小。\n\n------------\n\n#### 【数据范围】\n\n**本题采用捆绑测试。**\n\n| Subtask | Score | $n,m\\le$ | limit |\n| :----------: | :----------: | :----------: | :----------: |\n| $1$ | $10$ | $10^3$ | 无 |\n| $2$ | $20$ | $10^5$ | 保证不存在操作 $1$ |\n| $3$ | $30$ | $10^5$ | 保证对于每个操作 $2$ ，$p=1,q=n$ |\n| $4$ | $40$ | $10^5$ | 无 |\n\n对于 $100\\%$ 的数据，$1\\le n,m\\le10^5$，对于任何时刻 $\\forall i,a_i\\in[1,n]$。\n\n对于每个操作 $1$，$1\\le p\\le n$，$-n+1\\le x\\le n-1$ 并且 $-a_p<x\\le n-a_p$。\n\n对于每个询问 $2$，$1\\le l \\le r \\le n$，$1\\le p \\le q \\le n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8930","tags":["莫队","O2优化","分块"],"sample_group":[["6 5\n1 1 4 5 1 4\n2 1 6 1 5\n2 1 4 1 4\n1 1 1\n2 1 4 1 4\n2 2 6 1 5","5\n4\n-1\n4"],["12 12\n10 2 8 12 12 3 3 12 1 10 7 2\n2 3 4 1 11\n2 3 4 5 12\n2 1 3 1 3\n2 2 10 2 10\n2 8 10 5 10\n2 5 5 8 11\n2 10 12 7 10\n2 1 5 4 9\n1 12 6\n1 1 -6\n2 5 8 5 12\n2 5 8 2 12","-1\n-1\n-1\n8\n-1\n-1\n-1\n-1\n-1\n12"]],"created_at":"2026-03-03 11:09:25"}}