• [E] Search for the Iinflection Point

  • 时间限制: 1000 ms　内存限制: 65535 K
  • 问题描述
  • 给定一组整数序列，序列个数，所有整数，求在某个范围内拐点的个数，所谓拐点是在连续一段里即：

    或者


    则Sk称为拐点。

    如果碰到这种情况:

    或者

    则把S(k)作为一个拐点


  • 输入
  • 输入有多组,第一行输入n(2<n<=100000)代表有n个整数,接下来输入n个数,每个数介于-10^9~10^9。
    第三行输入一个m代表有m次询问(m<=1000),接下来m行每行有两个数l,r(1<=l<=r<=n)。
  • 输出
  • 对于每次询问,输出[l,r]之间的拐点个数。
  • 样例输入
  • 7
4 4 3 5 5 4 4
12
1 2
2 3
3 4
2 4
4 5
4 6
4 7
6 7
1 7
2 6
2 5
3 5
  • 样例输出
  • 0
1
1
1
1
1
1
0
2
2
2
2
  • 提示
  • 无
  • 来源
  • [ecjtu]xyyh
  • 操作

显示春菜