[Ynoi2014] 不归之人与望眼欲穿的人们
题目背景
【第一船队发来联络了】
【是关于第15号悬浮岛的战斗结果】
【15号悬浮岛的保卫作战...】
【失败了...】






题目描述
珂朵莉给了你一个序列,支持单点修改,或者询问满足区间 or 和**大于等于**一个数的区间的最短可能长度,无解输出 $-1$。
输入输出格式
输入格式
第一行有两个整数 $n,m$。
接下来一行 $n$ 个整数,表示这个序列 $a$。
接下来 $m$ 行,形如:
* $1\ i\ x$ 表示将 $a_i$ 修改为 $x$。
* $2\ k$ 表示询问最短的一个长度,满足存在一个该长度的区间,其 or 和 $\geq k$。
输出格式
对所有 $2$ 操作,输出一行,包含一个整数,表示答案,无解输出 $-1$。
输入输出样例
输入样例 #1
2 3
0 2
2 3
1 1 1
2 3
输出样例 #1
-1
2
说明
Idea:kczno1,
Solution:kczno1( $O( msqrtnloga )$ solution ),liu_cheng_ao($O( mlog^2nlog^2a$ ) solution ),142857cs($O( mlognlog^2a$ ) solution )
Code:kczno1( $O( msqrtnloga )$ code ),liu_cheng_ao($O( mlog^2nlog^2a$ ) code )
,Data:kczno1
对于 $100\%$ 的数据,$0\leq a_i,k\leq 2^{30}$,$1\leq n,m\leq 5\times 10^4$。