Sliding Window-----（线段树区间求最值）

Time limit 12000 ms  Case time limit 5000 ms Memory limit65536 kB

数据结构

来源：
poj：poj 2823 Sliding Window
vjudge： k-Sliding Window

Description

An array of size n ≤ 106 is given to you. There is a sliding window 
of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: 
The array is [1 3 -1 -3 5 3 6 7], and k is 3.

Your task is to determine the maximum and minimum values in the sliding window at each position. 

Input

The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line. 

Output

There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values. 

Sample Input

8 3
1 3 -1 -3 5 3 6 7

Sample Output

-1 -3 -3 -3 3 3
3 3 5 5 6 7

题意

输入的第一行包括两个数：n和d；
第二行包括n个数；
题目要求在这n个数中求出区间长度为d的区间内的最大值和最小值，其中第一行为最小值，第二行为最大值；

解题思路：

其实挂这个题的本意是想让我们多练习单调队列的吧!,然而我还是用线段树敲的@_@||,,,,唉！那就线段树吧！就只需要查询一个区间的最大值和最小值就好了。。。。。然后你就套了模板。。。。
交的时候记得要交C++而不是G++！！记得，，然而你斌不知道有什么区别！！！呵呵哒！
啊啊啊啊！！！我好烦呐！！！！！

完整代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int p[1000010];
struct node
{
    int l,r,n1,n2;
}tree[1000010*4];
void build(int id,int l,int r)
{
    int mid;
    tree[id].l=l;
    tree[id].r=r;
    mid=(l+r)/2;
    if(l==r)
     {
        tree[id].n1=p[mid];
        tree[id].n2=p[mid];
        return;
     }
     build(2*id,l,mid);
     build(2*id+1,mid+1,r);
     tree[id].n1=max(tree[2*id].n1,tree[2*id+1].n1);
     tree[id].n2=min(tree[2*id].n2,tree[2*id+1].n2);
}
int querymax(int id,int a,int b)//²éѯ
{
    int mid;
    if(tree[id].l==a&&tree[id].r==b)
        return tree[id].n1;
    mid=(tree[id].l+tree[id].r)/2;
    if(b<=mid)//×ó
         return querymax(2*id,a,b);
    else if(a>mid)
        return querymax(2*id+1,a,b);
    else
        return max(querymax(2*id,a,mid),querymax(2*id+1,mid+1,b));
}
int querymin(int id,int a,int b)//²éѯ
{
    int mid;
    if(tree[id].l==a&&tree[id].r==b)
        return tree[id].n2;
    mid=(tree[id].l+tree[id].r)/2;
    if(b<=mid)//×ó
         return querymin(2*id,a,b);
    else if(a>mid)
        return querymin(2*id+1,a,b);
    else
        return min(querymin(2*id,a,mid),querymin(2*id+1,mid+1,b));
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int maxn,minn;
        for(int i=1;i<=n;i++)
            scanf("%d",&p[i]);
        build(1,1,n);
        for(int i=1;i<=n-m+1;i++)
        {
            minn=querymin(1,i,i+m-1);
            if(i==1)
                printf("%d",minn);
            else
                printf(" %d",minn);
        }
        printf("\n");
        for(int i=1;i<=n-m+1;i++)
        {
            maxn=querymax(1,i,i+m-1);
            if(i==1)
                printf("%d",maxn);
            else
                printf(" %d",maxn);
        }
        printf("\n");
    }
    return 0;
}