单调队列入门题

单调队列：队列里的元素是单调的（只入队那些可能会影响答案的数据，一定不影响答案数据直接不入队）。复杂度O（2n)

洛谷 P1440 链接

题意：一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。

题解：单调队列模板题，入队时弹出，出队时判断。这题用j解除流绑定的cin还是会超时...

#include <bits/stdc++.h>
using namespace std; 
#define _for(i,a,b) for(int i=(a); i< (b); i++)
#define _rep(i,a,b) for(int i=(a); i<=(b); i++)
typedef long long ll; 

const int MAXN=2e6+5; 

struct Que{
    int idx, val;
}q[MAXN];
int a[MAXN];

int main()
{
    //ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, k;
    scanf("%d%d", &n, &k);
    _rep(i, 1, n) scanf("%d", &a[i]);
    int front=1, back=0;
    _rep(i, 1, n)
    {
        if(front>back) printf("0
");
        else
        {
            while(q[front].idx+k<i)
                front++;
            printf("%d
", q[front].val);
        }
        while(back>=front && q[back].val>=a[i]) 
            back--;
        q[++back].val=a[i]; q[back].idx=i;
    }    
    return 0;
}

View Code

HDU 3530

题意：找一个最长的子序列，使其中的最大值-最小值的范围在[m, k]

题解：这题错了好多次呀。开始的想法是：二分长度len，然后再用2个单调队列维护每一个长度为len的区间最大最小值，再判断是否满足。这是不对的，这个答案不满足单调性。长度为len时候不满足，可能为len+1的时候满足。

　　　正解：通过单调队列扫一遍数组（维护尽可能长的满足条件的子区间），维护最大最小值，在判断条件是否满足，（缩小最值的差上界，再判断是否满足下界），因为这里要求长度，这里队列记录的是坐标。注意当求子区间的起始点坐标别弄错了。

#include <bits/stdc++.h>
using namespace std;
#define _for(i,a,b) for(int i=(a); i< (b); i++)
#define _rep(i,a,b) for(int i=(a); i<=(b); i++)

const int MAXN=1e6+5;
int a[MAXN], q1[MAXN], q2[MAXN];

int main()
{
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, k;
    while(cin>>n>>m>>k)
    {
        _rep(i, 1, n) cin>>a[i];
        int l1=1, l2=1, r1=0, r2=0;
        int front=1, ans=0;
        _rep(i, 1, n)
        {
            while(r1>=l1 && a[q1[r1]]<a[i]) r1--;
            while(r2>=l2 && a[q2[r2]]>a[i]) r2--;
            q1[++r1]=i; q2[++r2]=i;
            while(r1>=l1 && r2>=l2 && a[q1[l1]]-a[q2[l2]]>k)
            {
                if(q1[l1]<q2[l2]) front=q1[l1++]+1;
                else front=q2[l2++]+1;
                //printf("!front=%d
", front);
            }
            if(r1>=l1 && r2>=l2 && a[q1[l1]]-a[q2[l2]]>=m)
                ans=max(ans, i-front+1);
            
            // 以下是自己一直写错的代码
            // front（满足条件的子序列开头的位置）不是这样子更新的
            /* 
            while(r1>=l1 && r2>=l2 && a[q1[l1]]-a[q2[l2]]>k)
            {
                if(q1[l1]<q2[l2]) l1++;
                else l2++;
                front=min(q1[l1], q2[l2]);
                //printf("!front=%d
", front);
            }
            if(r1>=l1 && r2>=l2 && a[q1[l1]]-a[q2[l2]]>=m)
                ans=max(ans, i-front+1);
            */ 
        }
        cout<<ans<<endl;
         
    }    
    return 0;
}

View Code

BZOJ 1012 [JSOI2008]最大数maxnumber

题意：现在请求你维护一个数列，要求提供以下两种操作：1、查询操作。语法：Q L 功能：查询当前数列中末尾L
个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、插入操作。语法：A n 功能：将n加
上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取
模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个
数。

题解：每次加入一个值，可能会更改比他这个值小的区间，单调队列往前扫即可。

单调队列：

#include <bits/stdc++.h>
using namespace std;

const int MAXN=2e5+5;
int m, d, t;
int q[MAXN];

int main()
{
    //freopen("in.txt", "r", stdin);
    scanf("%d%d", &m, &d);
    int l=1, r=0;
    while(m--)
    {
        char cmd[10]; 
        scanf("%s", cmd);
        if(cmd[0]=='A')
        {
            int n; scanf("%d", &n);
            n=(n+t)%d;
            int tr=r;
            while(tr>=l && q[tr]<n){
                q[tr]=n; tr--;
            }
            q[++r]=n;
        }
        else if(cmd[0]=='Q')
        {
            int L; scanf("%d", &L);
            t=q[r-L+1];
            printf("%d
", t);
        }
    }
    return 0;    
}

View Code

单调栈：

#include <bits/stdc++.h>
using namespace std;

const int MAXN=2e5+5;
int m, d, t;
int stk[MAXN], top;

int main()
{
    //freopen("in.txt", "r", stdin);
    scanf("%d%d", &m, &d);
    while(m--)
    {
        char cmd[10]; int p; 
        scanf("%s%d", cmd, &p);
        if(cmd[0]=='A')
        {
            p=(p+t)%d;
            for(int i=top; i; i--)
                if(stk[i]<p) stk[i]=p;
                else break;
            stk[++top]=p;
        }
        else 
            printf("%d
", t=stk[top-p+1]);
    }
    return 0;    
}

View Code

线段树

#include <bits/stdc++.h>
using namespace std;
#define ls l, m, rt<<1
#define rs m+1, r, rt<<1|1

const int MAXN=2e5+5;
const int INF=0x3f3f3f3f;
int m, d, t;
int tree[MAXN<<2];

void push_up(int rt)
{
    tree[rt]=max(tree[rt<<1], tree[rt<<1|1]);    
}

int query(int L, int R, int l, int r, int rt)
{
    if(L<=l && r<=R) return tree[rt];
    
    int m=l+r>>1, ret=-INF;
    if(L<=m) ret=max(ret, query(L, R, ls));
    if(R> m) ret=max(ret, query(L, R, rs));
    return ret;                                          
}

void update(int x, int v, int l, int r, int rt)
{
    if(l==r){
        tree[rt]=v; return ;
    }
    int m=l+r>>1;
    if(x<=m) update(x, v, ls);
    else update(x, v, rs);
    push_up(rt); 
}

void print(int l, int r, int rt)
{
    printf("l=%d, r=%d, tree=%d
", l, r, tree[rt]);
    if(l==r) return ;
    int m=l+r>>1;
    print(ls); print(rs);
}

int main()
{
    //freopen("in.txt", "r", stdin);
    scanf("%d%d", &m, &d);
    memset(tree, -0x3f, sizeof(tree));
    int pos=0;
    for(int i=0; i<m; i++)
    {
        //print(1, m, 1);
        char cmd[10]; int p; 
        scanf("%s%d", cmd, &p);
        if(cmd[0]=='A')
        {
            p=(p+t)%d;
            update(++pos, p, 1, m, 1);
        }
        else printf("%d
", t=query(pos-p+1, pos, 1, m, 1));
    }
    return 0;    
}

View Code

POJ 3017