Codevs 4373 窗口(线段树 单调队列 st表)
4373 窗口
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 Description
给你一个长度为N的数组,一个长为K的滑动的窗体从最左移至最右端,你只能见到窗口的K个数,每次窗体向右移动一位,如下表:
Window position Min value
Max 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
你的任务是找出窗口在各位置时的max value, min value.
输入描述 Input Description
第1行n,k,第2行为长度为n的数组
输出描述 Output Description
2行
第1行每个位置的min value
第2行每个位置的max value
样例输入 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
数据范围及提示 Data Size & Hint
数据范围:20%: n<=500; 50%: n<=100000;100%: n<=1000000;
/*
线段树区间查询.
o(nlogn+nlogn).
1726ms.
还好能卡过去orz.
*/
#include<iostream>
#include<cstdio>
#define MAXN 1000001
using namespace std;
struct data{int l,r,lc,rc,min,max;}tree[MAXN*4];
int n,m,cut,ans;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void build(int l,int r)
{
int k=++cut;tree[k].l=l,tree[k].r=r;
if(l==r){
tree[k].min=tree[k].max=read();return ;
}
int mid=(l+r)>>1;
tree[k].lc=cut+1;
build(l,mid);
tree[k].rc=cut+1;
build(mid+1,r);
tree[k].min=min(tree[tree[k].lc].min,tree[tree[k].rc].min);
tree[k].max=max(tree[tree[k].lc].max,tree[tree[k].rc].max);
}
int querymin(int k,int l,int r)
{
if(l<=tree[k].l&&tree[k].r<=r) return tree[k].min;
int tot=1e9,mid=(tree[k].l+tree[k].r)>>1;
if(l<=mid) tot=min(tot,querymin(tree[k].lc,l,r));
if(r>mid) tot=min(tot,querymin(tree[k].rc,l,r));
return tot;
}
int querymax(int k,int l,int r)
{
if(l<=tree[k].l&&tree[k].r<=r) return tree[k].max;
int tot=-1e9,mid=(tree[k].l+tree[k].r)>>1;
if(l<=mid) tot=max(tot,querymax(tree[k].lc,l,r));
if(r>mid) tot=max(tot,querymax(tree[k].rc,l,r));
return tot;
}
int main()
{
n=read();m=read();
build(1,n);
for(int i=1;i<=n-m+1;i++)
printf("%d ",querymin(1,i,i+m-1));
printf("\n");
for(int i=1;i<=n-m+1;i++)
printf("%d ",querymax(1,i,i+m-1));
return 0;
}
/*
st表写法.
复杂度O(nlogn+n).
2608ms.
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#define MAXN 1000001
#define D 21
using namespace std;
int n,k,a[MAXN],f[MAXN][D+5],s[MAXN][D+5],mi[D+5];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void slove()
{
int k=log(n)/log(2)+1;
for(int j=1;j<=k;j++)
for(int i=1;i<=n-mi[j-1];i++)
f[i][j]=max(f[i][j-1],f[i+mi[j-1]][j-1]),
s[i][j]=min(s[i][j-1],s[i+mi[j-1]][j-1]);
return ;
}
int querymax(int l,int r)
{
int k=log(r-l+1)/log(2);
return max(f[l][k],f[r-mi[k]+1][k]);
}
int querymin(int l,int r)
{
int k=log(r-l+1)/log(2);
return min(s[l][k],s[r-mi[k]+1][k]);
}
int main()
{
freopen("window.in","r",stdin);
freopen("window.out","w",stdout);
int x,y;
n=read();k=read();mi[0]=1;
for(int i=1;i<=D;i++) mi[i]=mi[i-1]<<1;
for(int i=1;i<=n;i++) a[i]=read(),f[i][0]=s[i][0]=a[i];
slove();
for(int i=1;i<=n-k+1;i++) printf("%d ",querymin(i,i+k-1));
printf("\n");
for(int i=1;i<=n-k+1;i++) printf("%d ",querymax(i,i+k-1));
return 0;
}
/*
单调队列维护[i,i-m+1]的min和max.
632ms.
论常数的重要性.
一开始傻逼的讲将1到m元素都入队.
然后不一定单调啊啊啊啊.
唉~.
*/
#include<iostream>
#include<cstdio>
#define MAXN 1000001
using namespace std;
int s[MAXN],n,m,q[MAXN],head=1,tail=1;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) s[i]=read();
q[1]=1;
for(int i=2;i<=n;i++)
{
while(head<=tail&&s[q[tail]]>s[i]) tail--;
q[++tail]=i;
while(head<=tail&&q[head]<i-m+1) head++;
if(i>=m) printf("%d ",s[q[head]]);
}
printf("\n");
head=tail=1;
for(int i=2;i<=n;i++)
{
while(head<=tail&&s[q[tail]]<s[i]) tail--;
q[++tail]=i;
while(head<=tail&&q[head]<i-m+1) head++;
if(i>=m) printf("%d ",s[q[head]]);
}
return 0;
}
最新文章
- Codeigniter基础
- 每天一个linux命令(28):tar命令
- centos7 + php7 lamp全套最新版本配置,还有mongodb和redis
- JBoss+Ant实现EJB无状态会话bean实例
- StackExchange.Redis 使用 - 事件(五)
- 当今Web应用的主要技术
- spring 集成mongo配置
- BZOJ:4820: [Sdoi2017]硬币游戏&;&;BZOJ:1444: [Jsoi2009]有趣的游戏(高斯消元求概率)
- java1.8--Null Object模式
- gcc创建静态库和共享库
- FFmpeg 结构体学习(六): AVCodecContext 分析
- ehcache缓存使用
- 【深入 MongoDB 开发】使用正确的姿势连接分片集群
- jQuery实现全选/反选和批量删除
- WordPress主题开发:输出指定页面导航
- FastDFS client for .net
- C#,清晨随手写
- influxdb 命令
- vue 可编辑表格组件
- java发送http的get和post请求