P4145 上帝造题的七分钟2 / 花神游历各国

    • 2.1K通过
    • 6.5K提交
  • 题目提供者 huangjunsen
  • 评测方式 云端评测
  • 标签 块状链表,块状数组,分块 并查集 枚举,暴力 线段树
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    XLk觉得《上帝造题的七分钟》不太过瘾,于是有了第二部。

    题目描述

    "第一分钟,X说,要有数列,于是便给定了一个正整数数列。

    第二分钟,L说,要能修改,于是便有了对一段数中每个数都开平方(下取整)的操作。

    第三分钟,k说,要能查询,于是便有了求一段数的和的操作。

    第四分钟,彩虹喵说,要是noip难度,于是便有了数据范围。

    第五分钟,诗人说,要有韵律,于是便有了时间限制和内存限制。

    第六分钟,和雪说,要省点事,于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。

    第七分钟,这道题终于造完了,然而,造题的神牛们再也不想写这道题的程序了。"

    ——《上帝造题的七分钟·第二部》

    所以这个神圣的任务就交给你了。

    输入输出格式

    输入格式:

    第一行一个整数$n$,代表数列中数的个数。

    第二行$n$个正整数,表示初始状态下数列中的数。

    第三行一个整数$m$,表示有$m$次操作。

    接下来$m$行每行三个整数k,l,r

    • k=0表示给$[l,r]$中的每个数开平方(下取整)
    • k=1表示询问$[l,r]$中各个数的和。

    数据中有可能$l>r$,所以遇到这种情况请交换l和r

    输出格式:

    对于询问操作,每行输出一个回答。

    输入输出样例

    输入样例#1: 复制
    10
    1 2 3 4 5 6 7 8 9 10
    5
    0 1 10
    1 1 10
    1 1 5
    0 5 8
    1 4 8
    输出样例#1: 复制
    19
    7
    6

    说明

    对于30%的数据,$1\le n,m\le 1000$,数列中的数不超过$32767$。

    对于100%的数据,$1 \le n,m \le 100000$,$1 \le l,r \le n$,数列中的数大于$0$,且不超过$10^{12}$。

    注意l有可能大于r,遇到这种情况请交换l,r。

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