P1533 可怜的狗狗

    • 575通过
    • 2K提交
  • 题目提供者 cyrcyr
  • 评测方式 云端评测
  • 标签 平衡树 排序 线段树 洛谷原创 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    小卡由于公务需要出差,将新家中的狗狗们托付给朋友嘉嘉,但是嘉嘉是一个很懒的人,他才没那么多时间帮小卡喂狗狗。

    题目描述

    小卡家有N只狗,由于品种、年龄不同,每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比(漂亮值越低越漂亮),吃饭时,狗狗们会按顺序站成一排等着主人给食物。

    可是嘉嘉真的很懒,他才不肯喂这么多狗呢,这多浪费时间啊,于是他每次就只给第i只到第j只狗中第k漂亮的狗狗喂食(好狠心的人啊)。而且为了保证某一只狗狗不会被喂太多次,他喂的每个区间(i,j)不互相包含。

    输入输出格式

    输入格式:

    第一行输入两个数n,m,你可以假设n<300001 并且 m<50001;m表示他喂了m次。

    第二行n个整数,表示第i只狗的漂亮值为ai。

    接下来m行,每行3个整数i,j,k表示这次喂食喂第i到第j只狗中第k漂亮的狗的漂亮值。

    输出格式:

    M行,每行一个整数,表示每一次喂的那只狗漂亮值为多少。

    输入输出样例

    输入样例#1: 复制
    7 2
    1 5 2 6 3 7 4
    1 5 3
    2 7 1
    
    输出样例#1: 复制
    3
    2
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。