P4243 [JSOI2009]等差数列

    • 83通过
    • 298提交
  • 题目提供者 KSkun
  • 评测方式 云端评测
  • 标签 差分 线段树 各省省选 2009 江苏
  • 难度 省选/NOI-
  • 时空限制 1000ms / 256MB

题解

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

    推荐的相关题目 显示

    题目背景

    “一个长度为 $l$ 的数列 $a_i$ ,若相邻两数间的差 $a_i - a_{i-1} \ (2 \leq i \leq l)$ 全部相同,则这个数列为等差数列。”火星特级数学老师jyy,正在给他的火星学生们上数学课。

    题目描述

    为了检验学生的掌握情况,jyy布置了一道习题:给定一个长度为 $N$ ( $1 \leq N \leq 100,000$ )的数列,初始时第 $i$ 个数为 $v_i$ ( $v_i$ 是整数, $-100,000 \leq v_i \leq 100,000$ ),学生们要按照jyy的给出的操作步骤来改变数列中的某些项的值。操作步骤的具体形式为:A s t a b ( $s, t, a, b$ 均为整数, $1 \leq s \leq t \leq N$ , $-100,000 \leq a, b \leq 100,000$ ),它表示,在序列的 $[s, t]$ 区间上加上初值为 $a$ ,步长为 $b$ 的等差数列。即 $v_i$ 变为 $v_i + a + b \times (i - s)$ (对于 $s \leq i \leq t$ )。

    在焦头烂额地计算之余,可怜的火星学生们还得随时回答jyy提出的问题。问题形式为:B s t( $s, t$ 均为整数, $1 \leq s \leq t \leq N$ ),表示jyy询问当前序列的 $[s, t]$ 区间最少能划分成几段,使得每一段都是等差数列。比如说1 2 3 5 7最少能划分成 $2$ 段,一段是1 2 3,另一段是5 7。询问是需要同学们计算出答案后,作为作业交上来的。

    虽然操作数加问题数总共只有 $Q$ ( $1 \leq Q \leq 100,000$ )个,jyy还是觉得这个题很无聊很麻烦。于是他想让你帮他算一份标准答案。

    输入输出格式

    输入格式:

    第 $1$ 行: $1$ 个整数 $N$ ,第 $2 \cdots N + 1$ 行:每行一个整数。第 $i + 1$ 行表示 $v_i$ 。

    第 $N + 2$ 行: $1$ 个整数 $Q$ ,第 $N + 3 \cdots N + Q + 2$ 行:每行描述了一个操作或问题,格式如题中所述,不含引号。

    输出格式:

    若干行,每行一个整数,表示对一个问题的回答。请按照输入中的顺序依次给出回答。

    输入输出样例

    输入样例#1: 复制
    5
    1
    3
    -1
    -4
    7
    2
    A 2 4 -1 5
    B 1 5
    输出样例#1: 复制
    2

    说明

    样例说明:

    原数列1 3 -1 -4 7。经过操作之后,数列变为1 2 3 5 7。如题中所述,最少能划分成 $2$ 段。

    数据规模:

    对 $30\%$ 的数据, $N, Q \leq 5000$ 。

    对 $100\%$ 的数据, $1 \leq N, Q \leq 100,000$ 。

    其他数据范围见题面。

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