2284: group
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：19
解决：7
题目描述
There are n men ,every man has an ID(1..n).their ID is unique. Whose ID is i and i-1 are friends, Whose ID is i and i+1 are friends. These n men stand in line. Now we select an interval of men to make some group. K men in a group can create K*K value. The value of an interval is sum of these value of groups. Every should has at least one friend in group otherwise he make a single-man group. Now we chose an interval of men and want to know there should be how many groups so the value of interval is max.
输入
First line is T indicate the case number.
For each case first line is n, m(1<=n ,m<=100000) indicate there are n men and m query.
Then a line have n number indicate the ID of men from left to right.
Next m line each line has two number L,R(1<=L<=R<=n),mean we want to know the answer of [L,R].
输出
For every query output a number indicate there should be how many group so that the sum of value is max.
样例输入 复制
1
5 2
3 1 2 5 4
1 5
2 4样例输出 复制
1
2