#P5065. [Ynoi2014] 不归之人与望眼欲穿的人们

[Ynoi2014] 不归之人与望眼欲穿的人们

题目背景

【第一船队发来联络了】
【是关于第15号悬浮岛的战斗结果】
【15号悬浮岛的保卫作战...】
【失败了...】





题目描述

珂朵莉给了你一个序列,支持单点修改,或者询问满足区间 or 和大于等于一个数的区间的最短可能长度,无解输出 1-1

输入格式

第一行有两个整数 n,mn,m

接下来一行 nn 个整数,表示这个序列 aa

接下来 mm 行,形如:

  • 1 i x1\ i\ x 表示将 aia_i 修改为 xx
  • 2 k2\ k 表示询问最短的一个长度,满足存在一个该长度的区间,其 or 和 k\geq k

输出格式

对所有 22 操作,输出一行,包含一个整数,表示答案,无解输出 1-1

2 3
0 2 
2 3
1 1 1
2 3
-1
2

提示

Idea:kczno1,

Solution:kczno1( O(mnloga)O( m\sqrt n\log a ) solution ),liu_cheng_ao(O(mlog2nlog2aO( m\log^2 n\log^2 a ) solution ),142857cs(O(mlognlog2aO( m\log n\log^2 a ) solution )

Code:kczno1( O(mnloga)O( m\sqrt n\log a ) code ),liu_cheng_ao(O(mlog2nlog2aO( m\log^2 n\log^2a ) code )

,Data:kczno1

对于 100%100\% 的数据,0ai,k2300\leq a_i,k\leq 2^{30}1n,m5×1041\leq n,m\leq 5\times 10^4