Problem 1471 --等差数列

1471: 等差数列

上一题 正确率: $70.59\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $17$ 正确数量 $12$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 数据结构

Description

有一个长度为N（1<=N<=100000）的整数序列S[]，在这个序列上定义了两种操作：
●Add L R A D: 对于每一个i（L<=i<=R），S[i]+=A+(i-L)*D，也就是在子序列S[L,R]加上首项为A，公差为D的等差数列;
●Query L R: 询问[L,R]区间内最长的等差数列的长度，亦即寻找最大的len，使S[i], S[i+1], ... , S[i+len-1]（L<=i<=R, L<=i+len-1<=R）构成等差数列。
序列S[]各项初值均为0.

Input

多组测试数据。
每组测试数据的第一行为两个正整数N（1<=N<=100000）和M（1<=M<=100000），分别代表序列的长度和操作个数。接下来有M行，每行代表一个操作，操作具体含义见题目描述。其中，0<=L<=R<N，0<=A<=100000，0<=D<=10.

Output

对于每组测试数据，首先输出组号。然后对于每次询问，输出所求结果。详见样例输出。

Sample Input复制

5 3
Add 1 4 1 1
Query 0 4
Query 2 3
10 4
Add 0 9 1 1
Add 4 9 1 1
Query 0 9
Query 5 5

Sample Output复制

Case #1:
5
2
Case #2:
7
1

推荐代码 查看1471 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$0 $ms] 找队友，能刷题的那种 416786 2019-05-05 18:12:54
内存最少[$1216 $KB] autohe 709791 2021-01-24 22:32:39
第一AC 未实名用户 88660 2017-05-13 20:24:04
第一挑战 未实名用户 88660 2017-05-13 20:24:04

赛题来源/所属竞赛 2013 Anhui College Student Programming Contest N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛