题目名称 2951. [SYOI 2018] WHZ 的序列
输入输出 whz_sequence.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 2018-07-03
开放分组 全部用户
提交状态
分类标签
线段树 SYOI
通过:2, 提交:2, 通过率:100%
GravatarWHZ0325 100 1.003 s C++
Gravatar呵呵 100 2.429 s C++
关于 WHZ 的序列 的讨论
标程公开。
GravatarWHZ0325
2018-07-04 12:23 1楼

2951. [SYOI 2018] WHZ 的序列

★★   输入文件:whz_sequence.in   输出文件:whz_sequence.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】

给定一个长度为 $n$ 的序列,WHZ 希望对这个序列执行 $q$ 次操作,每次修改将给定区间 $[l,r]$ 内的每个数都加上一个值 $d$,每次查询一个区间 $[l,r]$ 内的交替序列值,所谓交替序列值,就是指 $a_l-a_{l+1}+a_{l+2}-a_{l+3}+...+a_r$ 的值。

【数据范围】

针对 40% 的数据,有 $0≤n,q≤3\times10^4$,$1≤a_i≤10^8$.

针对 100% 的数据,有 $0≤n,q≤2\times10^5$,$1≤a_i≤10^8$.

【输入格式】

第一行是一个整数 $n$,表示序列的长度。

接下来是 $n$ 个整数 $a_1,a_2,...,a_n$。

第三行有一个整数 $q$,表示操作的个数。

下面是 $q$ 种操作,每行第一个整数 $opt$ 表示询问的类型。

当 $opt=1$ 时,该操作时修改操作,将 $[l,r]$ 之间的所有数都加上 $d$。

当 $opt=2$ 时,该操作是查询操作,输出 $[l,r]$ 内的交替序列值。

【输出格式】

每次查询操作输出一行包含一个整数,即查询的结果。

【样例输入】

5
1 3 5 4 2
5
2 2 4
1 1 4 1
2 4 5
1 3 5 -1
2 1 3

【样例输出】

2
3
3

【来源】

WHZOI Easy Round #1