CDOJ1620 Kawashiro Nitori's Cucumber Detector

　　题目地址：http://acm.uestc.edu.cn/problem.php?pid=1620

　　题目分析：在1～N的位子种了N个黄瓜，每个黄瓜有个level值：0～9（我们把0看成level值好了，有影响吗？）。作者要在某点k以R为范围探查黄瓜，就是说作者想知道在区间[k-R，k+R]内所有黄瓜中最高的level值是多少（如果k-R<1或k+R>N怎么办呢？这样边界就是1或N了呗）。问题抽象出来就是求区间最大值的问题！

　　解题思路：求区间最大值，推荐使用线段树。

程序先完成对线段树的初始化：seg[i]=0,for all i;

再构造线段树了（详见代码中的cre函数）；

对每个k点求出范围[L,R]，再对线段树查询（详见代码中query函数）。

　　源代码：

    #include<cstdio>
    #define PN printf("\n");
    
    int cuc[20005];
    int seg[100000];
    
    void ini(int n)//初始化线段树。
    {
        int i;
        for(i=0;i<=4*n;i++)
            seg[i]==0;
    }
    
    int cre(int i,int l,int r)//构造线段树，调用返回区间[l,r]中最大的level值。
    {
        int a,b,mid;
        if(l==r)//若l==r，说明已经把区间缩到一个点了，直接存该点level值。
        {
            seg[i]=cuc[l];
            return cuc[l];
        }
        mid=(l+r)/2;//区间中点，将区间一分为二
        a=cre(i*2,l,mid);//递归构造左区间，并得到左区间最大值a；
        b=cre(i*2+1,mid+1,r);//递归构造右区间，并得到右区间最大值b
        if(a>b)    //[l，r]的最大值当然是max（a，b）咯～
            seg[i]=a;
        else
            seg[i]=b;
        return seg[i];//还得返回[l，r]最大值！
    }
    
    int query(int i,int l,int r,int L,int R)//查询[l，r]间的最大值。当前访问seg中的i点，该点存的是区间[L，R]间的最大值。
    {
        int a,b,mid;
        if(l>R || r<L)//[L，R]不在查询区间[l，r]中。
            return 0;//返回个最小值0，不影响查询结果。
        else if(l<=L && r>=R)//[L，R]包含在[l，r]中，直接返回seg[i]
            return seg[i];
        mid=(L+R)/2;
        a=query(2*i,l,r,L,mid);//递归查询左区间
        b=query(2*i+1,l,r,mid+1,R);//递归查询右区间
        if(a>b)
            return a;//返回左右区间最大值
        return b;
    }
    
    int main()
    {
        int T,N,M,R,i,P,x,y,num;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d%d",&N,&M,&R);
            for(i=1;i<=N;i++)
                scanf("%d",&cuc[i]);
            ini(N);
            cre(1,1,N);
            for(i=0;i<M;i++)
            {
                scanf("%d",&P);
                if(P-R<1)
                    x=1;
                else
                    x=P-R;
                if(P+R>N)
                    y=N;
                else
                    y=P+R;
                num=query(1,x,y,1,N);
                printf("%d ",num);
            }
            PN
        }
        return 0;
    }