P3616 富金森林公园

    • 77通过
    • 682提交
  • 题目提供者 kkksc03 站长团
  • 评测方式 云端评测
  • 标签 树状数组 离散化 线段树 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    博艾的富金森林公园里有一个长长的富金山脉,山脉是由一块块巨石并列构成的,编号从1到N。每一个巨石有一个海拔高度。而这个山脉又在一个盆地中,盆地里可能会积水,积水也有一个海拔高度,所有严格低于这个海拔高度的巨石,就会在水面下隐藏。

    由于地壳运动,巨石的海拔高度可能会随时变化,每次一块的巨石会变成新的海拔高度。当然,水面的高度也会随时发生变化。

    因为有这样奇妙的地质奇观,吸引了很多游客来游玩。uim作为一个游客,可以告诉你此时水位海拔,你得告诉他,能看到有几个连续露出水面的部分。(与水面持平我们也认为是露出)

    输入输出格式

    输入格式:

    第一行两个整数N和M,分别表示N块石头,M个询问。

    接下来一行,N个整数Ai表示每个巨石的初始海拔。

    接下来M行,每行有两个或者三个数,每一行如果第一个数是1,那么后面跟一个Bj,表示水面海拔。如果第一个数是2,后面跟两个整数,Cj和Dj,表示编号Cj的巨石海拔变为Dj。

    输出格式:

    对于每个"1"询问,给出一个整数答案,也就是露出了几部分的山峰。

    输入输出样例

    输入样例#1: 复制
    5 4
    8 6 3 5 4
    1 5
    2 4 1
    1 5
    1 3
    输出样例#1: 复制
    2
    1
    2

    说明

    10%的数据, N,M<=2000

    另外30%的数据, 只有"1"的询问。

    100%的数据, 1<=N,M<=200000,1<=Ai,Bj,Dj<=10^9,一定有"1"询问

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