不支持【单点删除】下的尺取法

可以随意转载，但请附带原文地址http://www.cnblogs.com/qswg/p/8620602.html

问题的提出　

　　有些情况下，操作是没有逆的操作，比如max函数。这导致我们没法通过删除端点来移动左指针。

所以直接用普通尺取来求区间最值是不可能的。

那么是否有办法是否在不支持删除区间端点的情况下，依旧进行尺取呢。

答案是有的，而且实现方法很简单，只要用栈做一个缓存就行了。

算法的实现

　　为了方便讨论，我们假设尺取时每次查询区间[l_i,r_i]，应满足l_i<=l_i+1且r_i<=r_{i +1}

算法描述如下

首先我们声明一下所需的变量：

p1:左指针

p2:右指针

temp ：[p1+1,p2】的区间值

st[]:缓存(栈)，其中st[i]代表 [p1-i+1,p1]的区间值

len:被缓存区间的长度。

具体流程：

step1:判断要查询区间[l_i,r_i]是否与缓存区间有交集。若没有执行step2，有则执行step3.

step2: 构造缓存区：将p1,p1赋值为r_i.并更新temp的值，然后依次将区间[r_i,r_i],[r_i-1_,r_i],[r_i-2_,r_i]，……，[l_i,r_i] 压入st[]这个栈内。 返回[l_i,r_i]的值

step3:（1）对st执行退栈操作，直至栈顶区间的左端点等于l_i (2)移动右指针至r_i，并更新temp（3）返回temp+st.top();

算法的原理很简单，精髓在于用退栈来实现代替左指针的移动，这样就不用进行删除操作了。

算法复杂度分析：首先双指针的移动的复杂度肯定是O(n)的，而我们每次缓存一个区间的复杂度是O(区间长度)，而这些缓存区间的是不相交的。所以缓存区间的长度和最多是n。

综上总复杂度依旧是O(n)

实战

现在我们用新的算法来解决区间最值的尺取问题

http://poj.org/problem?id=2823

Sliding Window

Time Limit: 12000MS		Memory Limit: 65536K
Total Submissions: 66282		Accepted: 18836
Case Time Limit: 5000MS

Description

An array of size n ≤ 10⁶ is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.

Window position	Minimum value	Maximum value
[1  3  -1] -3  5  3  6  7	-1	3
1 [3  -1  -3] 5  3  6  7	-3	3
1  3 [-1  -3  5] 3  6  7	-3	5
1  3  -1 [-3  5  3] 6  7	-3	5
1  3  -1  -3 [5  3  6] 7	3	6
1  3  -1  -3  5 [3  6  7]	3	7

Your task is to determine the maximum and minimum values in the sliding window at each position.

AC代码如下（注意：因为数据量很大，千万不要调用任何的cout和print不然输出会慢10倍以上,进而导致运行时间*10-_-||）

 

#include <stdio.h>
#include<stack>
#define MAXN 2000005
#define  MAX 0
using namespace std;
int a[MAXN];
struct Buff
{
    int st[MAXN],temp,len,p1,p2;
    int type;
    void init()
    {

        temp=0;
        p1=0;
        p2=0;
        len=0;
    }
    int fun(int x,int y)
    {
        if(type==MAX)
            return max(x,y);
        return min(x,y);
    }
    int  query(int l,int r)
    {
        if(l>p1)
        {
            build(l,r);
            return st[len];
        }
        else
        {
            while(l+len-1>p1)
            {
                len--;
            }
            while(p2<r)
            {
                p2++;
                temp=fun(a[p2],temp);
            }
            return fun(st[len],temp);
        }
    }
    void build(int l,int r)
    {
        int i;
        if(type==MAX)
            st[0]=-2e9-7;
        else
            st[0]=2e9+7;
        len=0;
        for(i=r; i>=l; i--)
        {
            ++len;
            st[len]=fun(st[len-1],a[i]);
        }
        p1=r;
        temp=st[0];
        p2=r;
    }
} q;
inline void Read(int &x)
{
    char c=getchar();
    int f=1;
    x=0;
    while (c<'0'||c>'9')
    {
        if (c=='-')
            f=-f;
        c=getchar();
    }
    while (c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    x*=f;
}
inline void Write(int a)
{
    if(a<0)
    {
        putchar('-');
        a=-a;
    }
    if(a>9)
        Write(a/10);
    putchar(a%10+'0');
}
int main()
{
    int n,k,i,x;
    scanf("%d%d",&n,&k);
    for(i=1; i<=n; i++)
    {
        Read(a[i]);
    }
    q.init();
    q.type=1;
    for(i=1; i<=n-k+1; i++)
    {
        if(i>1)
            putchar(' ');
        x=q.query(i,i+k-1);

        Write(x);
    }
    putchar('
');
    q.init();
    q.type=0;
    for(i=1; i<=n-k+1; i++)
    {
        if(i>1)
            putchar(' ');
        x=q.query(i,i+k-1);
        Write(x);
    }
    putchar('
');
    return 0;
}

 本题一个比较经典的解法是单调队列，现在我们对比一下两种算法的运行情况。

 

可以看到单调队列稍快且代码量较少，不过这只是因为我对单调队列没有进行封装而导致的。

所以无论是从空间,时间，还是编程复杂度上，该算法和单调队列都十分相近的，效率十分优秀。

总结

算法的优点：

本文的算法与单调队列一样是用于处理序列尺取的算法，但是单调队列只能处理最值问题的尺取。而本文的算法几乎能处理任何区间尺取问题（只要单点添加操作是O(1)的）。

所以更具有通用性

算法的缺点：

实现起来比单调队列麻烦得多，而且蕴含的区间信息很少，不像单调队列蕴含着偏序关系，所以可能没法实现某些查询；

所以最值的尺取问题还是上单调队列比较好。

 习题

http://www.fjutacm.com/Problem.jsp?pid=3260

(因为OJ的网页数据较大，第一次打开要花较长时间)