poj 2823

この問題はとても穴のお父さんで、まず問題の意味を言います:最初からk個の最大値を探して、最小値、簡単にrmqを思いつきましたが、私は今日単調な列を練習して、書き終わってから提出して、tle.の私はその时、死の循环があると思って、后で确かに后でdiscussを见に行きます.人はG++がタイムアウトして、c++が过ごすことができると言って、交际するとやはりAになって、百思难解で、后でrmqを书いて超を见て、線分の木を书くことができなくて、倍増のdpでするしかなくて、配列が大きすぎて、メモリを爆発することを発见します.その後discussで最適化方法を発見し、正しいのはスクロール配列であり、私はまだ学ぶことができなかったようだ.変更後に提出するか、それともtleが神馬の原因なのか、C++に変更すると単調なキューよりも遅くなり、コード量も空間も大きいので、単調なキューを使うほうがいいです.
Run ID
User
Problem
Result
Memory
Time
Language
Code Length
Submit Time
9128755
201030720425
2823
Accepted
7068K
5485MS
C++
1048B
2011-08-10 19:35:37
9128735
201030720425
2823
Accepted
11940K
5891MS
C++
1429B
2011-08-10 19:34:36
たんちょうキュー

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
struct queuey
{
	int key,flag;
}q[1000005],qq[1000005];
int r,f,rr,ff;
int insertq(int flag,int key)
{
	while(r>f&&key<q[r].key)
		r--;
	q[++r].flag=flag;
	q[r].key=key;
	return 1;
}
int insertqq(int flag,int key)
{
	while(rr>ff&&key>qq[rr].key)
		rr--;
	qq[++rr].flag=flag;
	qq[rr].key=key;
	return 1;
}
void init()
{
	r=f=0;
	rr=ff=0;
}
int q1[1000005],q2[1000005];
int main()
{
	int n,k,key,flag=0;
	scanf("%d%d",&n,&k);
		init();flag=0;
	for(int i=1;i<=k&&i<=n;i++)
	{
		scanf("%d",&key);
		insertq(i,key);
		insertqq(i,key);
	}
	q1[flag]=q[f+1].key;
	q2[flag++]=qq[ff+1].key;
	for(int i=k+1;i<=n;i++)
	{
		scanf("%d",&key);
		insertq(i,key);
		insertqq(i,key);
		while(q[f+1].flag<=i-k&&f<r)
			f++;
		while(qq[ff+1].flag<=i-k&&ff<rr)
			ff++;
		q1[flag]=q[f+1].key;
		q2[flag++]=qq[ff+1].key;
	}
	for(int i=0;i<flag-1;i++)
		printf("%d ",q1[i]);
	printf("%d
",q1[flag-1]);
	for(int i=0;i<flag-1;i++)
		printf("%d ",q2[i]);
	printf("%d
",q2[flag-1]);
	return 0;
}

rmq倍増+スクロール配列

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int dp[1000000][2],n,m,a[1000000],key;
int rmq(int m)
{
	for(int i=0;i<n;i++)
		dp[i][0]=a[i];
	for(int k=1;k<=key;k++)
		for(int i=0;i+(1<<k)-1<n;i++)
		{
			dp[i][k%2]=max(dp[i][(k-1)%2],dp[i+(1<<(k-1))][(k-1)%2]);
		}
		if(n<m)
		{
		    int ans=max(dp[0][key%2],dp[n-(1<<key)][key%2]);
			printf("%d
",ans);
		}
		else
		{
			for(int i=0;i+m-1<n-1;i++)
			{
			int ans=max(dp[i][key%2],dp[i+m-(1<<key)][key%2]);
			printf("%d ",ans);
			}
			int ans=max(dp[n-m][key%2],dp[n-(1<<key)][key%2]);
			printf("%d
",ans);
		}
		return 1;
}
int rmq1(int m)
{
	for(int i=0;i<n;i++)
		dp[i][0]=a[i];
	for(int k=1;k<=key;k++)
		for(int i=0;i+(1<<k)-1<n;i++)
		{
			dp[i][k%2]=min(dp[i][(k-1)%2],dp[i+(1<<(k-1))][(k-1)%2]);
		}
		if(n<m)
		{
		    int ans=min(dp[0][key%2],dp[n-(1<<key)][key%2]);
			printf("%d
",ans);
		}
		else
		{
			for(int i=0;i+m-1<n-1;i++)
			{
			int ans=min(dp[i][key%2],dp[i+m-(1<<key)][key%2]);
			printf("%d ",ans);
			}
			int ans=min(dp[n-m][key%2],dp[n-(1<<key)][key%2]);
			printf("%d
",ans);
		}
		return 1;
}
int main()
{
	int m;
	scanf("%d%d",&n,&m);
	if(n<m)
		key=(int)(log((n)*1.0)/log(2.0));
	else
		key=(int)(log((m-1)*1.0)/log(2.0));
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	rmq1(m);
	rmq(m);
	return 0;
}