poj 2823 Sliding Window 线段树

太过爱你忘了你带给我的痛 2022-06-08 08:13 129阅读 0赞

Sliding Window  
Time Limit: 12000MS  
Memory Limit: 65536K  
Total Submissions: 50906  
Accepted: 14640  
Case Time Limit: 5000MS  
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.  
Window position Minimum value Maximum value  
\[1 3 -1\] -3 5 3 6 7 -1 3  
1 \[3 -1 -3\] 5 3 6 7 -3 3  
1 3 \[-1 -3 5\] 3 6 7 -3 5  
1 3 -1 \[-3 5 3\] 6 7 -3 5  
1 3 -1 -3 \[5 3 6\] 7 3 6  
1 3 -1 -3 5 \[3 6 7\] 3 7  
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，k，第二行输入n个数。现在有一个长度为k的窗口，从第一个数开始滑动（每次滑动1个单位），每次只有窗口范围中的数字可见。输出两行，第一行是每次窗口中的最小数，第二行是每次窗口中的最大数。  
AC代码：

//用g++一直超时，要用c++，好坑
    
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    #define maxn 1000000
    int num[maxn];
    struct node
    {
        int minvalue, maxvalue; //此节点的值
        int left,right;     //此节点所维护区间的左右端点
    }tree[maxn*4];
    struct Node
    {
        int min, max;
    }ans[maxn];
    void build(int root,int left,int right)
    {
        tree[root].left = left;
        tree[root].right = right;
        if(left == right)        //区间的左右端点相同，也就是到了叶子节点 
        {
            tree[root].maxvalue =  tree[root].minvalue = num[left];
            return ;
        }
        int mid = (left+right) / 2;
        build(root*2, left, mid);           //继续构建左子树
        build(root*2+1, mid+1, right);     //继续构建右子树
        tree[root].maxvalue = max(tree[root*2].maxvalue,tree[root*2+1].maxvalue);
        tree[root].minvalue = min(tree[root*2].minvalue,tree[root*2+1].minvalue);
    }
    //查询left，right区间的最值 ，这里用一个flag来标记查询的是最大值还是最小值
    int query(int root, int left, int right, int flag)   
    {
        if(tree[root].left == left&&tree[root].right == right){
            if(flag == 0)
                return tree[root].minvalue; 
            if(flag == 1)
                return tree[root].maxvalue; 
        }         
        if(right <= tree[2*root].right)     //这个区间在根的左边 
           return query(root*2, left, right, flag);
        else  if(left >= tree[root*2+1].left)//这个区间在根的右边
           return query(root*2+1, left, right, flag);
        else                //这个区间既在根的左边又在根的右边
        {
            int mid = (tree[root].left+tree[root].right) / 2;
            if(flag == 0)
                return min(query(root*2, left, mid, flag), query(root*2+1, mid+1, right, flag));
            if(flag == 1)
                return max(query(root*2, left, mid, flag), query(root*2+1, mid+1, right, flag));
        }
    }
    int main()
    {
        int n, k;
        while(scanf("%d %d",&n, &k) != EOF){
            for(int i = 1; i <= n; i++)
                scanf("%d", &num[i]);   
            build(1, 1, n);     
            for(int j = 1; j <= n-k+1; j++){
                int right = j + k - 1;
                ans[j].min = query(1, j,right ,0);
                ans[j].max = query(1, j,right ,1);
            }
            for(int j = 1; j <= n-k+1; j++){
                if(j == 1)
                    printf("%d", ans[j].min);
                else
                    printf(" %d", ans[j].min);
            }
            printf("\n");
            for(int j = 1; j <= n-k+1; j++){
                if(j == 1)
                    printf("%d", ans[j].max);
                else
                    printf(" %d", ans[j].max);
            }
            printf("\n");
    
        }
        return 0;
    }