Home => ProblemSet => 线段树上二分
Problem2303--线段树上二分

2303: 线段树上二分

Time Limit: 1 Sec  Memory Limit: 1024 MB  Submit: 0  Solved: 1
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

给定n个数a1,a2,a3,...,an
共计m个操作:
1 x d, 修改ax=d
2 l r d, 查询al, al+1, al+2,...,ar中大于等于d的第一个数的下标。
如果不存在，输出-1.也就是说，求最小的i(l <= i <= r)满足ai >= d.

Input

第一行两个整数n, m(1 <= n, q <= 2 * 105);
接下来一行n个整数a1, a2,...,an(1 <= ai <= 109);
接下来m行，每行一个操作。数据保证1 <= x <= n, 1 <= l <= r <= n, 1<= d <= 109

Output

对于每个查询，输出一行表示答案

Sample Input Copy 

5 5
1 2 3 4 5
2 4 5 5
1 5 1
2 1 5 3
1 3 2
2 1 3 3

Sample Output Copy 

5
3
-1

Source/Category

数据结构 线段树 
[ Submit ] [ Status ]