线段树-poj-2823

简介: 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

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. 

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

 微笑大意:给出数组a,内容为 a1 a2 a3 ... an。再给一个常数k。从i=1起,计算ai、a i+1、...、a i+k-1区间内的最小值和最大值。

线段树咯。

 


目录
相关文章
|
6月前
|
算法 数据建模
Poj 3169(差分约束系统)
Poj 3169(差分约束系统)
34 0
POJ 1936 All in All
POJ 1936 All in All
75 0
|
人工智能 机器学习/深度学习
poj 1455
Description n participants of > sit around the table. Each minute one pair of neighbors can change their places.
618 0
|
人工智能
POJ 2531
初学dfs参考别人代码,如有雷同,见怪不怪。#include using namespace std; int aa[25][25]; int maxa=0; int step[25]={0},n; void dfs(int a,int b) { int t=b; step...
709 0
|
人工智能 BI
poj-3185-开关问题
描述   牛一行20他们喝的水碗。碗可以那么(面向正确的为清凉水)或颠倒的(一个位置而没有水)。他们希望所有20个水碗那么,因此用宽鼻子翻碗。   嘴太宽,他们不仅翻转一碗还碗的碗两侧(总共三个或三个——在两端的情况下碗——两碗)。
811 0
poj-1008-玛雅历
Description 上周末,M.A. Ya教授对古老的玛雅有了一个重大发现。从一个古老的节绳(玛雅人用于记事的工具)中,教授发现玛雅人使用了一个一年有365天的叫做Haab的历法。这个Haab历法拥有19个月,在开始的18个月,一个月有20天,月份的名字分别是pop, no, zip, zotz, tzec, xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu。
883 0
|
人工智能
POJ 1936 All in All
Description You have devised a new encryption technique which encodes a message by inserting between its characters randomly generated strings in a clever way.
791 0