TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2504
  • 题目
  • P2504【平衡树】区间翻转问题
    限制 : 时间限制 : 10000 MS   空间限制 : 265000 KB
    问题描述

    给你一个长度为N的序列{ai}和M个操作
    1.查询第k个数的值
    2.将第k个数增加d
    3.查询一段区间的和
    4.查询一段区间的最大值
    5.将一段区间镜面翻转(例如序列{1,2,3,4,5,6},将从2到5的区间翻转后得到序列{1,5,4,3,2,6})
    对于除操作2,5以外的操作,输出相应的答案

    输入格式

    第一行两个正整数N,M
    第二行N个整数,为初始的序列
    第三行到底M+2行,每行若干个整数
    ·如果第一个数为1,那么后面一个正整数k,表示查询第k个数的值
    ·如果第一个数是2,那么后面两个正整数k,d,表示将ak增加d
    ·如果第一个数为3,那么后面两个正整数l,r,表示查询从al到ar的区间和
    ·如果第一个数为4,那么后面两个正整数l,r,表示查询从al到ar的最大值
    ·如果第一个数为5,那么后面两个正整数l,r,表示翻转从al到ar的这个区间

    输出格式

    除操作2,5外每个操作输出占一行,一个整数,为本次提问的答案

    样例输入

    6 8
    1 2 3 4 5 6
    1 4
    3 2 5
    4 2 2
    5 2 5
    3 1 3
    5 2 5
    2 5 1
    4 1 6

    样例输出

    4
    14
    2
    10
    6

    提示

    2<=N<=100000
    1<=M<=100000
    原序列1<=ai<=1000
    每次1<=k<=N,1<=l<=r<=N,1<=d<=1000


    来源  感谢nodgd命题并提供数据