luogu1886：滑動的視窗（（線段樹+輸出優化）|| 單調隊列）

題目傳送門

題目大意：

    連續的區間查詢

解題過程（因為之間發表在了luogu的論壇上，現在整合過來而已）：

1、馬上想到了單調隊列的思路；

2、最近在磕線段樹，反正手速快，先跑一遍線段樹。

先寫線段樹的白癡思路1：

1、建空樹的時候，在葉子的時候順便讀初始值（省掉插初始值的函數和運算時間），建好就已經不是空樹了。

2、直接寫查詢最大值函數，然後複制一份，改成最小值。

3、輸出。

結果:50分，囧。

自己分析：感覺分大小值，查兩遍，時間複雜度翻倍了。

↓↓↓↓↓↓↓↓↓=還有這種操作=↓↓↓↓↓↓↓↓↓

果斷去翻題解：有大神說隻需要查一次，每次查的時候同時傳回最大和最小值！！

↑↑↑↑↑↑↑↑↑=還有這種操作=↑↑↑↑↑↑↑↑↑

機智的我，想到了傳回一個結構體，完美。

結果：80分，t最後2個點。

↓↓↓↓↓↓↓↓↓=還有這種操作=↓↓↓↓↓↓↓↓↓

回去認真再看了一次大神的分析，原來過程先輸出最小值，最後單獨輸出最大值。又省掉一個百萬級别的循環。

↑↑↑↑↑↑↑↑↑=還有這種操作=↑↑↑↑↑↑↑↑↑

然後終于 A 了，一會再刷一次單調隊列，現在先上線段樹的白癡代碼。

#include<cstdio>
    struct nod{int l,r,s1,s2,a,b;nod(){a=-999999999,b=999999999;}}a[2000010];
    int n,k,len=0;
    struct nod2{int a,b;}b[2000010];//存答案的結構體 
    int minn(int x,int y) { return x<y?x:y; }
    int maxx(int x,int y) { return x>y?x:y; }
    void br(int l,int r)
    {
        len++; int x=len; a[x].l=l; a[x].r=r;
        if(l==r) { scanf("%d",&a[x].a); a[x].b=a[x].a; return;} //到葉子了，讀資料 
        if(l<r)
        {
            int m=(l+r)/2;
            a[x].s1=len+1; br(l,m);
            a[x].s2=len+1; br(m+1,r);
        }
        a[x].a=maxx(a[a[x].s1].a,a[a[x].s2].a);//a 最大值 
        a[x].b=minn(a[a[x].s1].b,a[a[x].s2].b);//b 最小值 
    }
    nod2 cha(int x,int l,int r)
    {
        nod2 p; int ma=-999999999,mi=999999999;
        //p作為緩存結構體， ma 存臨時最大值，mi存臨時最小值 
        if(a[x].l==l&&a[x].r==r) { p.a=a[x].a; p.b=a[x].b; return p;}
        int m=(a[x].l+a[x].r)/2,s1=a[x].s1,s2=a[x].s2;
        if(r<=m) return cha(s1,l,r);
        else if(l>m) return cha(s2,l,r);
        else 
        {    p=cha(s1,l,m); ma=maxx(ma,p.a);mi=minn(mi,p.b);
            p=cha(s2,m+1,r); ma=maxx(ma,p.a);mi=minn(mi,p.b);
            p.a=ma; p.b=mi; return p;
        }
    }
    int main()
    {
        scanf("%d %d",&n,&k);
        br(1,n);
        for(int i=1;i<=n-k+1;i++)
        {
            int j=i+k-1;
            b[i]=cha(1,i,j);
            printf("%d ",b[i].b);//第一行輸出放在這裡，省掉一次百萬級的循環，拿下最後2個點 
        }
        printf("\n");
        for(int i=1;i<=n-k+1;i++) printf("%d ",b[i].a); 
        return 0;
    }
           

下面是用兩個單調隊列來完成的代碼（簡單粗暴）：

#include<cstdio>
    #include<cstring>
    int n,l,la=0,lb=0;
    int a[1000010],an[1000010],bn[1000010];
    struct nod{int x,i;} ;
    nod da[1000010];//下降隊列，頭最大 ：解決最大值 
    int t1=1,w1=1;//隊列的頭尾标簽 
    void pp1(int l,int x)//最大值 
    {    
        //進隊列 
        while(w1>=t1&&a[x]>da[w1].x) w1--;//找到插入的位置 
        w1++;//插入
        da[w1].x=a[x]; 
        da[w1].i=x;
        //出隊列（區間之前位置的數） 
        while(t1<=w1 &&da[t1].i<l) t1++; 
    }
    //==========================================================
    nod db[1000010];//上升隊列，頭最小：解決最小值 
    int t2=1,w2=1;// 頭尾标簽 
    void pp2(int l,int x)//最小值 
    {    
        //進隊列 
        while(w2>=t2&&a[x]<db[w2].x) w2--;//找到插入的位置 
        w2++;//插入  
        db[w2].x=a[x]; 
        db[w2].i=x;
        //出隊列（區間之前位置的數） 
        while(t2<=w2 &&db[t2].i<l) t2++; 
    }
    int main()
    {
        scanf("%d %d",&n,&l);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        da[1].x=-999999999;
        db[1].x= 999999999;
        for(int i=1;i<=l;i++)// 第一個區間 
        {    
            pp1(1,i); 
            pp2(1,i);
        }
        an[++la]=da[t1].x;
        bn[++lb]=db[t2].x;
        printf("%d ",bn[lb]);
        for(int i=2;i<=n-l+1;i++)//後續的區間 
        {
            int j=i+l-1;
            pp1(i,j); an[++la]=da[t1].x; 
            pp2(i,j); bn[++lb]=db[t2].x; printf("%d ",bn[lb]);
        }
        printf("\n");
        for(int i=1;i<=la;i++) printf("%d ",an[i]);
        return 0;
    }