POJ 2823 线段树 Or 单调队列

时限12s! 所以我用了线段树的黑暗做法，其实正解是用单调队列来做的。

//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1000001
#define lson l,mid,pos*2
#define rson mid+1,r,pos*2+1
using namespace std;
int n,k,xx,yy,ansmax,ansmin,tree[N*4],MAX[N*4],MIN[N*4],ANSMAX[N],ANSMIN[N];
void build(int l,int r,int pos){
    if(l==r){scanf("%d",&tree[pos]);MAX[pos]=MIN[pos]=tree[pos];return;}
    int mid=(l+r)/2;
    build(lson),build(rson);
    MAX[pos]=max(MAX[pos*2],MAX[pos*2+1]);
    MIN[pos]=min(MIN[pos*2],MIN[pos*2+1]);
}
void query(int l,int r,int pos){
    if(l>=xx&&r<=yy){ansmax=max(ansmax,MAX[pos]);ansmin=min(ansmin,MIN[pos]);return;}
    int mid=(l+r)/2;
    if(mid<xx)query(rson);
    else if(mid>=yy)query(lson);
    else query(lson),query(rson);
}
int main()
{
    scanf("%d%d",&n,&k);
    build(1,n,1);
    for(xx=1;xx<=n-k+1;xx++){
        yy=xx+k-1,ansmax=-1*0x3fffffff,ansmin=0x3fffffff;
        query(1,n,1),ANSMAX[xx]=ansmax,ANSMIN[xx]=ansmin;
    }
    for(xx=1;xx<=n-k+1;xx++)printf("%d ",ANSMIN[xx]);puts("");
    for(xx=1;xx<=n-k+1;xx++)printf("%d ",ANSMAX[xx]);
}

2016.11.16补坑 单调队列 （啊这题好水啊~）

//By SiriusRen
#include <deque>
#include <cstdio>
using namespace std;
int n,m,a[1000500];
struct Node{int pos,weight;Node(){}Node(int x,int y){pos=x,weight=y;}}ans[1000500];
deque<Node>maxx,minn;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        if(!maxx.empty()&&maxx.front().pos+m<=i)maxx.pop_front();
        if(!minn.empty()&&minn.front().pos+m<=i)minn.pop_front();
        while(!maxx.empty()&&maxx.back().weight<=a[i])maxx.pop_back();
        while(!minn.empty()&&minn.back().weight>=a[i])minn.pop_back();
        maxx.push_back(Node(i,a[i]));minn.push_back(Node(i,a[i]));
        ans[i].pos=maxx.front().weight,ans[i].weight=minn.front().weight;
    }
    for(int i=m;i<=n;i++)printf("%d ",ans[i].weight);putchar('
');
    for(int i=m;i<=n;i++)printf("%d ",ans[i].pos);
}