被逼着写的一个题，以前觉得难度很大的东西，一旦有动力去好好学习，其实真的并没有那么难

ACM代码其实没有多少行，而且原理也就那么几句，怀着一颗向上的心，每天正能量，每天一道a+b，时间长了真的会有很大进步的

因为，时间都看得见

（废话了一波）


题目链接：POJ2823

题意：给定n，k，n个数，求每个连续的以K为区间长度的区间中的最小值和最大值

方法1：线段树！区间内的最大最小值，果断线段树搞

（不明白为啥只能用C++提交，G++会超时）

我对于这个的理解是：C++的很多实现较少，而且编译不稳定所以快（追求效率用C++提交）

G++很多东西实现得更好，或者说编译原理不相同，速度虽然慢点，但是有的题用G++能过C++一直wa的


代码就不解释了，直接贴：

int n,k;
int Min[maxn<<2];
int Max[maxn<<2];

void build(int rt,int l,int r){
	if (l==r){
		scanf("%d",&Min[rt]);
		Max[rt]=Min[rt];
		return;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	Min[rt]=min(Min[ll],Min[rr]);
	Max[rt]=max(Max[ll],Max[rr]);
	return;
}

int getMin(int L,int R,int rt,int l,int r){
	if (l>=L&&R>=r) return Min[rt];
	int mid=(l+r)>>1;
	if (R<=mid) return getMin(L,R,lson);
	else if (L>mid) return getMin(L,R,rson);
	return min(getMin(L,R,lson),getMin(L,R,rson));
}

int getMax(int L,int R,int rt,int l,int r){
	if (l>=L&&R>=r) return Max[rt];
	int mid=(l+r)>>1;
	if (R<=mid) return getMax(L,R,lson);
	else if (L>mid) return getMax(L,R,rson);
	return max(getMax(L,R,lson),getMax(L,R,rson));
}

int main(){
	//input;
	while(scanf("%d%d",&n,&k)!=EOF){
		build(1,1,n);
		for(int i=1;i<=n-k+1;i++)
			printf("%d%c",getMin(i,i+k-1,1,1,n),i==n-k+1?'\n':' ');
		for(int i=1;i<=n-k+1;i++)
			printf("%d%c",getMax(i,i+k-1,1,1,n),i==n-k+1?'\n':' ');
	}
	return 0;
}

方法2：单调队列

网上搜这个题，很多对于单调队列的解释和理解，毕竟算是个简单题

单调队列的意义：当前队列维护的是值的单调性，不是位置的单调性，意味着是个结构体，是按照值来sort的

任何一个数据结构，涉及到的最有意义的部分是插入和删除

以最小值为例：

添加时：准备添加时，把需要添加的元素值不断的和队尾的元素值比较，直到队尾的元素小于等于需要添加的值或者队列为空了

然后把该元素添加进去

比如：当前值是3，2，6，10，5（现在还没有管位置）

第一轮，队列为【3】

第二轮，3出队因为比2大，队列为【2】

第三轮，6进队，队列为【2，6】

第四轮，10进队，队列为【2，6，10】

第五轮，5进队之前先得让6和10出队，队列为【2，5】

添加的时候，是为了达到查询时：最小的元素一定在队头这个目的


删除：删除这个操作是要根据题意来搞的

比如这个题要求的是区间长度最大为K，那么需要用结构体记录每次插入元素的值和位置，两个差值需要小于K


懂了原理之后剩下的见代码（单调队列的时间确实比线段树省）

求最小的单调队列解释得很清楚，最大的同理

struct node{
	int pos,val;
}q[maxn];

int num[maxn],n,k;
int Min[maxn];
int Max[maxn];

void getMin(){
	int head=1,tail=0;
	for(int i=1;i<k;i++){
		//前k-1个数跟查询无关，直接放进来 
		while(head<=tail&&num[i]<q[tail].val) tail--;
		//插入的准备操作，要么队列为空，要么找到一个位置使得符合单调队列定义 
		tail++;
		q[tail].val=num[i];
		q[tail].pos=i;
		//插入 
	}
	for(int i=k;i<=n;i++){
		while(head<=tail&&num[i]<q[tail].val) tail--;
		tail++;
		q[tail].val=num[i];
		q[tail].pos=i;
		while(i-q[head].pos>=k) head++;
		//删除操作，维护最大的区间长度 
		Min[i-k]=q[head].val;
		//答案记录 
	}
}

void getMax(){
	int head=1,tail=0;
	for(int i=1;i<k;i++){
		while(head<=tail&&num[i]>q[tail].val) tail--;
		tail++;
		q[tail].val=num[i];
		q[tail].pos=i;
	}
	for(int i=k;i<=n;i++){
		while(head<=tail&&num[i]>q[tail].val) tail--;
		tail++;
		q[tail].val=num[i];
		q[tail].pos=i;
		while(i-q[head].pos>=k) head++;
		Max[i-k]=q[head].val;
	}
}

int main(){
	//input;
	while(scanf("%d%d",&n,&k)!=EOF){
		for(int i=1;i<=n;i++) scanf("%d",&num[i]);
		getMin();
		for(int i=0;i<=n-k;i++) printf("%d%c",Min[i],i==n-k?'\n':' ');
		getMax();
		for(int i=0;i<=n-k;i++) printf("%d%c",Max[i],i==n-k?'\n':' ');
	}
	return 0;
}


方法3：用STL的priority_queue来实现，上代码就很好理解了

int a[maxn],Min[maxn],Max[maxn],n,k;

struct cmp1{
	bool operator() (const int a1,const int a2){
		return a[a1]>a[a2];
	}
};

struct cmp2{
	bool operator() (const int a1,const int a2){
		return a[a1]<a[a2];
	}
};

priority_queue<int,vector<int>,cmp1> q1;
priority_queue<int,vector<int>,cmp2> q2;

int main(){
	//input;
	while(scanf("%d%d",&n,&k)!=EOF){
		int i,cnt1=0,cnt2=0;
		for(i=0;i<n;i++) scanf("%d",&a[i]);
		while(!q1.empty()) q1.pop();
		while(!q2.empty()) q2.pop();
		for(i=0;i<k;i++){
			q1.push(i);
			q2.push(i);
		}
		Min[cnt1++]=a[q1.top()];
		Max[cnt2++]=a[q2.top()];
		for(i=k;i<n;i++){
			q1.push(i);
			q2.push(i);
			while(i-q1.top()>=k) q1.pop();
			while(i-q2.top()>=k) q2.pop();
			Min[cnt1++]=a[q1.top()];
			Max[cnt2++]=a[q2.top()];
		}
		for(int i=0;i<=n-k;i++) printf("%d%c",Min[i],i==n-k?'\n':' ');
		for(int i=0;i<=n-k;i++) printf("%d%c",Max[i],i==n-k?'\n':' ');
	}
	return 0;
}