Problem E: 等差数列

上一题 正确率: $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