UESTC 1015 Lweb and pepper --前，后缀最值

题意： n种食物，每种含花椒的概率为Pi，现在已经选择了[L,R]这个区间（下标）的食物，要再选一个，使总的食物只有一种含花椒的概率最大，问选哪个最好，相同的选下标小的。

解法： 就不写解法了。此处有官方题解： http://acm.uestc.edu.cn/bbs/read.php?tid=5835

维护一个前缀后缀的最值即可。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#define Mod 1000000007

#define eps 1e-8

using namespace std;

#define N 100002

int preMax[N],bacMax[N],preMin[N],bacMin[N];

double pMax[N],pMin[N],bMax[N],bMin[N],p[N];

int sgn(double x)

{

    if(x < -eps) return -;

    if(x > eps)  return ;

    return ;

}

int main()

{

    int t,n,i,m,L,R;

    cin>>t;

    while(t--)

    {

        scanf("%d",&n);

        for(i=;i<=n;i++)

            scanf("%lf",&p[i]);

        preMax[] = ;   preMin[] = ;

        pMax[] = -;      pMin[] = Mod;

        bacMax[n+] = n+; bacMin[n+] = n+;

        bMax[n+] = -;  bMin[n+] = Mod;

        for(i=;i<=n;i++)

        {

            preMax[i] = preMax[i-];

            preMin[i] = preMin[i-];

            pMax[i] = pMax[i-];

            pMin[i] = pMin[i-];

            if(p[i] > pMax[i]) pMax[i] = p[i], preMax[i] = i;

            if(p[i] < pMin[i]) pMin[i] = p[i], preMin[i] = i;

        }

        for(i=n;i>=;i--)

        {

            bacMax[i] = bacMax[i+];

            bacMin[i] = bacMin[i+];

            bMax[i] = bMax[i+];

            bMin[i] = bMin[i+];

            if(p[i] >= bMax[i]) bMax[i] = p[i], bacMax[i] = i;

            if(p[i] <= bMin[i]) bMin[i] = p[i], bacMin[i] = i;

        }

        scanf("%d",&m);

        while(m--)

        {

            scanf("%d%d",&L,&R);

            L++,R++;

            double B = 1.0, E = 0.0;

            for(i=L;i<=R;i++)

                B *= (-p[i]), E += p[i]/(-p[i]);

            if(sgn(-E) > )

            {

                if(pMax[L-] >= bMax[R+]) printf("%d\n",preMax[L-]-);

                else                       printf("%d\n",bacMax[R+]-);

            }

            else

            {

                if(pMin[L-] <= bMin[R+]) printf("%d\n",preMin[L-]-);

                else                       printf("%d\n",bacMin[R+]-);

            }

        }

    }

    return ;

}