【tyvj1463】智商问题

2014年3月4日1,5103

背景 Background

各种数据结构帝~
各种小姊妹帝~
各种一遍AC帝~ 来吧!

描述 Description

某个同学又有很多小姊妹了
他喜欢聪明的小姊妹 所以经常用神奇的函数来估算小姊妹的智商
他得出了自己所有小姊妹的智商
小姊妹的智商都是非负整数
但是这个同学看到别的同学的小姊妹
也喜欢用神奇的函数估算一下
然后看看这个小姊妹在自己的小姊妹群体中排在第几位…
(这么邪恶的兴趣…)

输入格式 InputFormat

第一行一个整数N 代表小姊妹的个数
第二行N个整数 代表这位同学N个小姊妹的智商
接下来若干行 每行一个整数
代表这位同学看中的别人的小姊妹的智商
0<=智商<=2^31-1
0<=N<=1000000

输出格式 OutputFormat

输出若干行
每行一个整数 回答新的小姊妹
在原来小姊妹中智商的排名

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

数据量很大
C语言用scanf输入输出!
另外 这个同学的小姊妹群体在这个题中是不会变的~
他会在看完所有别的同学的小姊妹之后…
大家听说过 苏格拉底和麦田的故事的吧…

题解

这题是个二分的简单题

不过可以用来练习分块,将a数组排序之后分为√n块,记录一下每一块的最大值

每次询问先√n枚举找到这个数所在的块,再在块内暴力√n个元素

 

  • zyf20002016年3月30日 下午4:01 回复

    黄学长,为什么我把last数组存成下标,然后每次查询的时候套上a,这样就会T掉一组。

    #1  
    • 李孜睿2016年3月30日 下午7:45 回复

      老老实实写二分呗,

      #11
      • zyf20002016年3月31日 下午3:12 回复

        。。那我就要练分块。。

        #12