维护一个递增的和递减的单调队列

Assignment

2
4 2
3 1 2 4
10 5
0 3 4 5 2 1 6 7 8 9

5
28
Hint
First Sample, the satisfied groups include:[1,1]、[2,2]、[3,3]、[4,4] 、[2,3] 
 

/* ***********************************************
Author        :CKboss
Created Time  :2015年07月21日 星期二 12时36分35秒
File Name     :1002.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

typedef long long int LL;
const int maxn=100100;

struct Node
{
    int val,pos;
};

int n,K;
int a[maxn];
// q1 dizheng q2 dijian
deque<Node> q1,q2;

LL ans;

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int T_T;
    scanf("%d",&T_T);
    while(T_T--)
    {
        ans=0;
        while(!q1.empty()) q1.pop_back();
        while(!q2.empty()) q2.pop_back();

        scanf("%d%d",&n,&K);
        for(int i=0;i<n;i++) scanf("%d",a+i);

        int head=0;
        for(int i=0;i<n;i++)
        {
            Node node = (Node){a[i],i};

            /// push q1 tail dizheng
            while(!q1.empty())
            {
                Node b = q1.back();
                if(b.val<node.val) q1.pop_back();
                else break;
            }
            q1.push_back(node);

            /// push q2 tail dijian
            while(!q2.empty())
            {
                Node b = q2.back();
                if(b.val>node.val) q2.pop_back();
                else break;
            }
            q2.push_back(node);

            if(i==0) ans++;
            else
            {
                /// bijiao head
                while(true)
                {
                    Node big = q1.front();
                    Node small = q2.front();

                    if(big.val-small.val<K) break;
                    else
                    {
                        if(small.pos<big.pos)
                        {
                            head=small.pos+1; q2.pop_front();
                        }
                        else
                        {
                            head=big.pos+1; q1.pop_front();
                        }
                    }
                }
                ans+=i-head+1;
            }
        }

        cout<<ans<<endl;
    }
    
    return 0;
}

HDOJ 5289 Assignment 单调队列

原文：http://blog.csdn.net/ck_boss/article/details/46990123