• [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
  • 操作

显示春菜