Problem B: 等差数列

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $17$ 正确数量 $12$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 数据结构
有一个长度为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.
多组测试数据。
每组测试数据的第一行为两个正整数N(1<=N<=100000)和M(1<=M<=100000),分别代表序列的长度和操作个数。接下来有M行,每行代表一个操作,操作具体含义见题目描述。其中,0<=L<=R<N,0<=A<=100000,0<=D<=10.
对于每组测试数据,首先输出组号。然后对于每次询问,输出所求结果。详见样例输出。
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
Case #1:
5
2
Case #2:
7
1