P2496 [SDOI2012]体育课

    • 39通过
    • 199提交
  • 题目提供者 kkksc03 吉祥物
  • 评测方式 云端评测
  • 标签 各省省选 2012 山东 高性能
  • 难度 省选/NOI-
  • 时空限制 6000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    警告:滥用本题评测将被封号

    题目描述

    又是一节体育课的时间了,有n个同学排成了一排。他们都很讨厌排在第一个位置的同学,于是后面的同学中比第一个高的都会产生一个高兴值,这个高兴值等于他的身高减去第一个同学的身高。当然比第一个同学矮的同学产生兴奋值为0。

    现在体育老师来了,他拥有神奇的魔法,现在他能做如下的三件事:

    1:询问某段区间高兴值最大的那个是多少。

    2:把某两个同学交换一下位置。

    3:选取一段区间的人,把第一个人身高加上t,第二个加上2t,第三个加上3t以此类推。

    但是体育老师不会数数,于是他找到你了,对于每一个询问,他要你帮他求出那个值。

    输入输出格式

    输入格式:

    第一行两个整数n,m表示有n个人,有m个操作。

    第二行n个整数,顺序输入每个人的身高。(身高<=10^8)

    接下来m行,每行第一个数位一个type表示是做哪一件事情。

    如果type=1,那么接下来有两个整数l,r,表示询问这段区间的最大的高兴值

    如果Type=2,接下来两个整数a,b,表示交换这两个位置的人

    如果type=3,接下来三个整数l,r,t,表示把l个人的升高增加t,l+1个人增加2t…第r个人增加(r-l+1)t, (0<=t<= 10000)

    输出格式:

    对于每个询问按照顺序输出每个操作1的答案。

    输入输出样例

    输入样例#1: 复制
    6 7
    109 827 100 530 10 826
    3 1 6 1
    2 2 6
    1 2 4
    1 2 3
    2 2 6
    1 2 6
    1 2 5
    输出样例#1: 复制
    722
    722
    722
    719

    说明

    数据范围:

    有20%的数据:n,m<=5000

    另有10%的数据:没有第三种操作.

    另有20%的数据: 没有第二种操作

    对于100%的数据:n,m<=100000

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