#PQJ64x2031. QOJ 64_2031
QOJ 64_2031
K 大数查询 大数查询 大数查询 大数查询 【问题描述】 【问题描述】 【问题描述】 【问题描述】 有n 个位置和m 个操作。操作有两种,每次操作如果是1 a b c 的形式,表 示往第a 个位置到第b 个位置每个位置加入一个数c。如果操作形如2 a b c 的形 式,表示询问从第a 个位置到第b 个位置,第c 大的数是多少。 【输入格式 输入格式 输入格式 输入格式】 在输入文件sequence.in 中,第一行两个数n,m。意义如题目描述。 接下来m 行每行形如1 a b c 或者2 a b c 如题目描述。 【输出格式 输出格式 输出格式 输出格式】 在输出文件sequence.out 中,对于每个询问回答k 大数是多少。 【样例输入 样例输入 样例输入 样例输入】 2 5 1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3 【样例输出 样例输出 样例输出 样例输出】 1 2 1 【样例说明】 【样例说明】 【样例说明】 【样例说明】 第一个操作后位置1 的数只有1,位置2 的数也只有1。第二个操作后位置1 的数有1、2,位置2 的数也有1、2。第三次询问位置1 到位置1 第2 大的数是 1。第四次询问位置1 到位置1 第1 大的数是2。第五次询问位置1 到位置2 第3 大的数是1。 【数据规模与约定】 30%的数据n=m=1000 100%的数据n,m≤50000,并且后7 个点的数据n,m 的范围从32000 到50000 近似成等差数列递增。a≤b≤n,1 操作中|c|≤n,2 操作中|c|≤maxlongint