P2617 Dynamic Rankings

    • 830通过
    • 2K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 主席树 树套树
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序,从输入文件中读入序列a,然后读入一系列的指令,包括询问指令和修改指令。

    对于每一个询问指令,你必须输出正确的回答。

    输入输出格式

    输入格式:

    第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。

    第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。接下来的m行描述每条指令,每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t

    • Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。

    • C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t。

    输出格式:

    对于每一次询问,你都需要输出他的答案,每一个输出占单独的一行。

    输入输出样例

    输入样例#1: 复制
    5 3
    3 2 1 4 7
    Q 1 4 3
    C 2 6
    Q 2 5 3
    输出样例#1: 复制
    3
    6
    

    说明

    20%的数据中,m,n≤100;

    40%的数据中,m,n≤1000;

    100%的数据中,m,n≤10000。

    来源:bzoj1901

    本题数据为洛谷自造数据,使用CYaRon耗时5分钟完成数据制作。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。