青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 74,  comments - 33,  trackbacks - 0
Sliding Window
Time Limit: 12000MS Memory Limit: 65536K
Total Submissions: 7213 Accepted: 1859
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 positionMinimum valueMaximum value
[1??3??-1]?-3??5??3??6??7?-13
?1?[3??-1??-3]?5??3??6??7?-33
?1??3?[-1??-3??5]?3??6??7?-35
?1??3??-1?[-3??5??3]?6??7?-35
?1??3??-1??-3?[5??3??6]?7?36
?1??3??-1??-3??5?[3??6??7]37

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

Source

POJ Monthly--2006.04.28, Ikki
這題讓我想到了 幾個月前的浙大月賽題的區間最大最小值,用隊列維護的方法還是不會
用線段樹AC,有點郁悶,我的半吊子線段樹啊?? 居然10s才ac,不過幸好服務器沒掛。。。。。。
代碼如下
?
#include<stdio.h>
#include
<string.h>
#define?MAX?1001010
struct?node{
????
int?l,r;
????
int?m;
}
;
node?Max_Stree[
2*MAX];
node?Min_Stree[
2*MAX];
int?w[MAX];
int?getmax(int?a,int?b)
{
????
return?a>b?a:b;????
}

int?getmin(int?a,int?b)
{
????
return?a>b?b:a;????
}

int?Build_Max(int?now,int?l,int?r){
????Max_Stree[now].l
=l;
????Max_Stree[now].r
=r;
????
if(l==r)Max_Stree[now].m=w[l];
????
else?{
????????
int?mid=(l+r)>>1;
????????
int?max1=Build_Max(2*now,l,mid);
????????
int?max2=Build_Max(2*now+1,mid+1,r);
????????Max_Stree[now].m
=getmax(max1,max2);????
????}

????
return?Max_Stree[now].m;????
}

int?Build_Min(int?now,int?l,int?r){
????Min_Stree[now].l
=l;
????Min_Stree[now].r
=r;
????
if(l==r)Min_Stree[now].m=w[l];
????
else?{
????????
int?mid=(l+r)>>1;
????????
int?min1=Build_Min(2*now,l,mid);
????????
int?min2=Build_Min(2*now+1,mid+1,r);
????????Min_Stree[now].m
=getmin(min1,min2);????
????}

????
return?Min_Stree[now].m;????
}

int?Find_Max(int?now,int?l,int?r){
????
int?left=Max_Stree[now].l;
????
int?right=Max_Stree[now].r;
????
if(left==l&&right==r)
????????
return?Max_Stree[now].m;
????
int?mid=(left+right)>>1;
????
if(mid+1>r)return?Find_Max(2*now,l,r);
????
if(mid<l)return?Find_Max(2*now+1,l,r);????
????
else?return?getmax(Find_Max(2*now,l,mid),Find_Max(2*now+1,mid+1,r));
}

int?Find_Min(int?now,int?l,int?r){
????
int?left=Min_Stree[now].l;
????
int?right=Min_Stree[now].r;
????
if(left==l&&right==r)
????????
return?Min_Stree[now].m;
????
int?mid=(left+right)>>1;
????
if(mid+1>r)return?Find_Min(2*now,l,r);
????
if(mid<l)return?Find_Min(2*now+1,l,r);????
????
else?return?getmin(Find_Min(2*now,l,mid),Find_Min(2*now+1,mid+1,r));
}
posted on 2009-02-19 11:16 KNIGHT 閱讀(340) 評論(0)  編輯 收藏 引用
<2009年2月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
1234567

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

Friends

OJ

搜索

  •  

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产精品欧美风情| 亚洲在线播放| 欧美黄在线观看| 亚洲精品日产精品乱码不卡| 欧美护士18xxxxhd| 欧美wwwwww| 亚洲一区免费| 久久精品一区二区三区不卡牛牛 | 一区二区三区久久网| 欧美视频网址| 久久免费99精品久久久久久| 麻豆freexxxx性91精品| 一本久道久久综合婷婷鲸鱼| 亚洲手机在线| …久久精品99久久香蕉国产| 最新国产成人在线观看| 欧美日本中文| 久久久久久夜精品精品免费| 农村妇女精品| 午夜在线电影亚洲一区| 久久理论片午夜琪琪电影网| 一区二区三区久久| 久久国产精品99精品国产| 亚洲欧洲日本专区| 午夜激情久久久| a4yy欧美一区二区三区| 欧美一区二区女人| 日韩小视频在线观看| 午夜宅男欧美| 一区二区免费在线观看| 久久国产精品一区二区| 一本综合精品| 久久综合狠狠综合久久激情| 午夜精品久久久久久99热| 免费成人黄色片| 久久av一区二区三区| 欧美日本精品| 欧美高清在线视频| 国产女人精品视频| 亚洲七七久久综合桃花剧情介绍| 国产欧美 在线欧美| 最近中文字幕mv在线一区二区三区四区| 国产精品三级视频| 亚洲免费黄色| 亚洲另类自拍| 老司机凹凸av亚洲导航| 久久精品欧洲| 国产日韩欧美精品在线| 一区二区三区**美女毛片| 最新亚洲一区| 免费视频一区| 免费欧美高清视频| 狠狠综合久久| 久久精品一二三区| 老司机成人在线视频| 国产日本亚洲高清| 亚洲影院色无极综合| 在线视频日韩| 欧美日韩一卡二卡| 亚洲激情成人在线| 亚洲精品一二三区| 男人的天堂亚洲在线| 欧美成人中文| 亚洲国产日韩一区| 男人插女人欧美| 亚洲激情第一页| 日韩一区二区精品视频| 欧美日韩 国产精品| 亚洲国产欧美一区二区三区久久 | 日韩系列欧美系列| 一区二区日韩| 国产精品日韩欧美| 欧美一区二区三区在线视频 | 亚洲精品日韩激情在线电影| 亚洲免费观看高清完整版在线观看熊 | 亚洲人精品午夜| 亚洲视频高清| 国产免费成人在线视频| 亚洲中字在线| 麻豆久久婷婷| 99视频精品全国免费| 国产精品久久久久久久久久免费看 | 亚洲一区bb| 国产女主播一区二区| 久久久久久久波多野高潮日日| 久久综合久久综合久久| 91久久在线| 国产精品黄视频| 久久精品视频免费播放| 亚洲人成人77777线观看| 亚洲自拍三区| 1000精品久久久久久久久| 欧美精品xxxxbbbb| 亚洲综合电影| 亚洲国产天堂久久综合网| 亚洲欧美日韩中文播放| 在线观看日韩av电影| 欧美日本韩国一区| 久久av一区二区三区漫画| 亚洲高清不卡在线观看| 午夜在线观看免费一区| 亚洲大胆视频| 国产精品久久久久久久久久久久久 | 国产精品vip| 久久精品五月婷婷| 在线视频欧美日韩精品| 麻豆91精品| 午夜精品999| 亚洲日本成人网| 国户精品久久久久久久久久久不卡| 欧美黄色一级视频| 久久久久久久网| 亚洲小说春色综合另类电影| 亚洲国产精品久久| 久久久久久**毛片大全| 亚洲少妇最新在线视频| 亚洲电影免费观看高清完整版在线观看 | 国产日韩av在线播放| 欧美色道久久88综合亚洲精品| 久久综合伊人77777| 性欧美1819性猛交| 99在线视频精品| 亚洲三级免费电影| 欧美国产三级| 欧美超级免费视 在线| 欧美日韩国产高清| 久久影视三级福利片| 欧美一区激情| 午夜精品在线观看| 亚洲一区二区在线看| 亚洲精选在线观看| 亚洲国产三级| 亚洲国产成人porn| 亚洲成人中文| 欧美激情精品久久久久| 欧美成人在线网站| 欧美第一黄色网| 欧美电影免费网站| 欧美激情精品久久久久久久变态| 美女主播一区| 欧美成人一品| 亚洲国产日本| 亚洲日本视频| 日韩视频精品在线| 一本色道久久综合狠狠躁篇怎么玩 | 一区二区三区四区国产| 99视频精品| 亚洲午夜伦理| 午夜精品一区二区在线观看| 亚洲欧美一级二级三级| 欧美在线视频一区二区| 久久久久久久综合日本| 麻豆精品传媒视频| 欧美精品在线一区二区三区| 欧美日韩国产精品一区二区亚洲| 欧美日韩一区二区高清| 国产精品久久久久久久久免费 | 国产精品v日韩精品| 国产精品久久久久91| 国产午夜精品一区二区三区欧美| 国产资源精品在线观看| 亚洲大胆美女视频| 制服诱惑一区二区| 久久精品国产亚洲5555| 免费成年人欧美视频| 亚洲精品日韩一| 午夜精品久久久久99热蜜桃导演| 久久这里有精品15一区二区三区| 欧美成人高清视频| 国产精品户外野外| 在线观看视频欧美| 亚洲深爱激情| 美女黄色成人网| 亚洲视频高清| 麻豆精品一区二区av白丝在线| 欧美午夜精品久久久久久浪潮| 国产一区二区三区的电影| 亚洲精品日韩久久| 久久精品人人做人人综合| 亚洲福利视频三区| 亚洲欧美卡通另类91av | 香蕉久久a毛片| 欧美 日韩 国产 一区| 国产精品白丝av嫩草影院| 狠狠噜噜久久| 午夜视频精品| 亚洲国产欧美一区二区三区同亚洲| 亚洲一区三区在线观看| 欧美丰满少妇xxxbbb| 国产精品制服诱惑| 一区二区欧美日韩| 欧美成人综合一区| 欧美一区二区精品在线| 欧美视频在线观看| 亚洲人成人一区二区在线观看| 欧美在线视频播放| 一区二区三区你懂的| 欧美wwwwww| 黄色精品在线看| 久久精品论坛|