【完璧に待つ】HDU-3530:Subsequence

Subsequence
ソース:HDU
ラベル:データ構造、単調なキュー
参考資料:
似たようなテーマ:
テーマ
The e e e is a sequence of integers.Your task is to find the longest subsequence that satis fies the following condition:the difference between the maximelement and the minum element of the subsequence no.slant slant
入力
The re are multile test cases.For each test case,the first line has three integers,n,m and k.n is the length of the sequence and is in the range[1,000].m and the are the range[0,000]
出力
For each test case,print the length of the subsequence on a single line.
入力サンプル
5 0 1 1 1 1 1 5 0 3 1 2 3 5
出力サンプル
5 4
タイトルの大意
一番長い連続サブシーケンスを見つけることが必要です.このサブシーケンスの最大値と最小値の差はmに等しく、k以下です.
問題を解く構想
一つの区間の最大値と最小値を見つけたいです.二つの単調な列を使って、一つは増分行列、一つは減少行列です.分かりにくいです.詳しく説明します.
参照コード

#include
#include
#define MAXN 100005
using namespace std;

struct Node{
	int v;
	int p;
}up[MAXN],down[MAXN];//    ，     

int n,m,k;
int num[MAXN];

int main(){
	while(~scanf("%d%d%d",&n,&m,&k)){
		for(int i=0;i<n;i++){
			scanf("%d",&num[i]);
		}
		
		int head_d=0, tail_d=0;
		int head_u=0, tail_u=0;
		int ans=0;
		
		int pos=0;
		
		for(int i=0;i<n;i++){
			//     
			while(head_d<tail_d && num[i]>down[tail_d-1].v) tail_d--;
			down[tail_d].v=num[i]; down[tail_d++].p=i;
			
			//     
			while(head_u<tail_u && num[i]<up[tail_u-1].v) tail_u--;
			up[tail_u].v=num[i]; up[tail_u++].p=i;
			
			while(down[head_d].v-up[head_u].v>k){//     -   >k 
				if(down[head_d].p<up[head_u].p)//                     
					pos=down[head_d++].p+1;//                      
				else 
					pos=up[head_u++].p+1;//                      
			}
			
			if(down[head_d].v-up[head_u].v>=m){
				ans=max(ans,i-pos+1);
			}
		}
		printf("%d
",ans);
	}
	return 0;
}