TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P9033
  • 题目
  • P9033「USACO 2021 Dec Gold」HILO
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    Bessie 有一个数 \(x+0.5\) ,其中 \(x\) 是某个 \(0\)\(N\) 之间的整数( \(1\le N\le 2 \cdot 10^5\) )。

    Elsie 正试着猜这个数。她可以以如下形式对于某个 \(1\)\(N\) 之间的整数提问:「 \(i\) 是大了还是小了?」如果 \(i\) 大于 \(x+0.5\) ,Bessie 会回答 "HI",如果 \(i\) 小于 \(x+0.5\) 则回答 "LO"。

    Elsie 想到了以下猜测 Bessie 的数的策略。在进行任何猜测之前,她创建了一个包含 \(N\) 个整数的序列,其中从 \(1\)\(N\) 的每个数均恰好出现一次(换句话说,这个序列是长为 \(N\) 的一个排列)。然后她遍历这一列表,按列表中的数的顺序依次猜数。

    然而,Elsie 会跳过所有不必要的猜测。也就是说,如果 Elsie 将要猜某个数 \(i\) ,而 Elsie 之前已经猜过了某个 \(j < i\) 并且 Bessie 回答 "HI",Elsie 不会再猜 \(i\) ,而是继续猜序列中的下一个数。类似地,如果她将要猜某个数 \(i\) ,而她之前已经猜过了某个 \(j > i\) 并且 Bessie 回答 "LO",Elsie 不会再猜 \(i\) ,而是继续猜序列中的下一个数。可以证明,使用这一策略,对于 Elsie 创建的任意序列,她都可以唯一确定 \(x\)

    如果我们将所有 Bessie 回答的 "HI" 或 "LO" 拼接成一个字符串 \(S\) ,那么 Bessie 说 "HILO" 的次数为 \(S\) 等于 "HILO" 的长为 \(4\) 的子串数量。

    Bessie 知道 Elsie 将要使用这一策略;此外,她还知道 Elsie 将要使用的排列。然而, Bessie 尚未决定选用哪个值 \(x\)

    帮助 Bessie 对于每个值 \(x\) 求出她会说 "HILO" 的次数。

    输入格式

    输入的第一行包含 \(N\)

    第二行包含 Elsie 的长为 \(N\) 的排列。

    输出格式

    对于从 \(0\)\(N\) 的每一个 \(x\) ,输出一行,包含 Bessie 会说 HILO 的次数。

    样例输入

    5
    5 1 2 4 3

    样例输出

    0
    1
    1
    2
    1
    0

    提示

    样例1解释

    对于 \(x=0\) ,Bessie 会说 "HIHI",总计零次 "HILO"。 对于 \(x=2\) ,Bessie 会说 "HILOLOHIHI",总计一次 "HILO"。 对于 \(x=3\) ,Bessie 会说 "HILOLOHILO",总计两次 "HILO"。


    数据范围

    • 测试点 1-4 满足 \(N \leq 5000\)
    • 测试点 5-8 为均匀随机的排列。
    • 测试点 9-20 没有额外限制。