codeforces#333 div2 B. Approximating a Constant Range

http://codeforces.com/contest/602/problem/B

这道题的两种做法，

滑窗+线段树查询区间最值：

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=(1<<29);

struct SegTree
{
    struct Node
    {
        int l,r;
        int Min,Max;
    };
    Node T[maxn<<2];
    void push_up(int rt)
    {
        T[rt].Max=max(T[rt<<1].Max,T[rt<<1|1].Max);
        T[rt].Min=min(T[rt<<1].Min,T[rt<<1|1].Min);
    }
    void build(int *a,int l,int r,int rt)
    {
        T[rt].l=l;T[rt].r=r;
        if(l==r){
            T[rt].Max=T[rt].Min=a[l];
            return;
        }
        int m=(l+r)>>1;
        build(a,l,m,rt<<1);
        build(a,m+1,r,rt<<1|1);
        push_up(rt);
    }
    int queryMax(int L,int R,int rt)
    {
        if(L<=T[rt].l&&T[rt].r<=R) return T[rt].Max;
        int m=(T[rt].l+T[rt].r)>>1;
        int res=-INF;
        if(L<=m) res=max(res,queryMax(L,R,rt<<1));
        if(R>m) res=max(res,queryMax(L,R,rt<<1|1));
        return res;
    }
    int queryMin(int L,int R,int rt)
    {
        if(L<=T[rt].l&&T[rt].r<=R) return T[rt].Min;
        int m=(T[rt].l+T[rt].r)>>1;
        int res=INF;
        if(L<=m) res=min(res,queryMin(L,R,rt<<1));
        if(R>m) res=min(res,queryMin(L,R,rt<<1|1));
        return res;
    }
};SegTree sgt;
int a[maxn],n;

int main()
{
    //freopen("in.txt","r",stdin);
    while(cin>>n){
        REP(i,1,n) scanf("%d",&a[i]);
        sgt.build(a,1,n,1);
        int pre=1;
        int ans=1;
        REP(i,1,n){
            while(sgt.queryMax(pre,i,1)-sgt.queryMin(pre,i,1)>1) pre++;
            ans=max(ans,i-pre+1);
        }
        cout<<ans<<endl;
    }
    return 0;
}

滑窗+单调队列维护滑窗最值：

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=1<<29;

deque<int> q1,q2;
int n,a[maxn];

int main()
{
    freopen("in.txt","r",stdin);
    while(cin>>n){
        REP(i,1,n) scanf("%d",&a[i]);
        int pre=1,ans=1;
        while(!q1.empty()) q1.pop_back();
        while(!q2.empty()) q2.pop_back();
        REP(i,1,n){
            while(!q1.empty()&&q1.back()<a[i]) q1.pop_back();
            q1.push_back(a[i]);
            while(!q2.empty()&&q2.back()>a[i]) q2.pop_back();
            q2.push_back(a[i]);
            while(q1.front()-q2.front()>1){
                if(a[pre]==q1.front()) q1.pop_front();
                if(a[pre]==q2.front()) q2.pop_front();
                pre++;
            }
            ans=max(ans,i-pre+1);
        }
        cout<<ans<<endl;
    }
    return 0;
}

第一道单调队列= =