F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 5057. -- 区间k小值5

5057: 区间k小值5

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 84  Solved: 32
[Submit][Status][Discuss]

Description

有n(n<=30000)个位置,q(q<=30000)个操作,操作有两种。一. 1 l r a b 表示在第l个位置到第r个位置,每个位
置加入a到b之间的所有数,一开始所有位置为空。(1<=l<=r<=n,1<=a<=b<=n)二. 2 l r k 表示询问从第l个位置到
第r个位置,第k小的数是多少。(1<=l<=r<=n,1<=k<=n*n*q,保证k合法)

Input

第一行两个数n和q。
接下来q行,每行为1 l r a b或2 l r k。
保证第一次操作为操作一。
测试数据均为随机产生。

Output

输出每个询问的结果

Sample Input

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

Sample Output

1
1
2
2
1
1
2
2
2
1
2
2

HINT

Source

By Amayoneko

[Submit][Status][Discuss]

HOME Back