BZOJ3339/Rmq Problem

Posted on Jan 15, 2014 By 二价氢

题解在这里

我用的离线做法

我们得知道以下几点内容：

  1. 从某一项开始的\(mex\)是单调不减序列
  2. 从第\(i\)项开始的\(mex\)序列能通过从第\(i-1\)项开始的\(mex\)序列在\(O(n)\)的时间内修改得到

离线算法的复杂度为\(O(n \log n)\)

  1. 首先，做出从第1项开始的\(mex\)序列，并与处理对于每一项\(A_i\)，下一次出现该项的位置\(Next_i\)
  2. 然后，如何将第\(i\)项变为第\(i+1\)项呢？我们只需要将\((i,Next_i)\)这一区间的所有大于\(A_i\)的项改为\(A_i\)即可
  3. 上一过程看起来是\(O(n)\)的，但事实上，平均每一次修改，我们至多修改\(O(log n)\)项
  4. 我们能在\(O(1)\)的时间内作出单一询问的回答
  5. 重复这一过程，直到处理完讯问队列

下面是AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int MAXN=200005;
struct Query{int q,l,r;}Que[MAXN];
// mex   如题所述
// next  下一次出现数字i的位置
// mp    数字i上一次出现的位置
// a     如题所述
int mex[MAXN],next[MAXN];
int a[MAXN];
map<int,int> mp;
int QUERYANS[MAXN];
int n,q;
bool comp(Query a,Query b)
{
    return (a.l==b.l)?(a.r<b.r):(a.l<b.l);
}
void update(int from)
{
    int to=next[from];
    int val=a[from];
    mex[from]=0;
    if (!to)
        to=n;
    for (int i=to;i>from;i--)
    {
        if (mex[i]<val)
            break;
        mex[i]=val;
    }
}
void work()
{
    int lastwork=1;
    for (int i=1;i<=q;i++)
    {
        if (Que[i].l!=lastwork)
            for (int j=lastwork;j<Que[i].l;j++)
                update(j);
        lastwork=Que[i].l;
        QUERYANS[Que[i].q]=mex[Que[i].r];
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    memset(a,-1,sizeof(a));
    memset(mex,-1,sizeof(mex));
    memset(next,0,sizeof(next));
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if (mp[a[i]]>0)
        {
            next[mp[a[i]]]=i-1;
            mp[a[i]]=i;
        }else
        {
            next[mp[a[i]]]=n;
            mp[a[i]]=i;
        }
    }
    mp.clear();
    int min=0;
    if (a[1]==0)
        min=1;
    mex[1]=min;mp[a[1]]=1;
    for (int i=2;i<=n;i++)
    {
        mp[a[i]]=1;
        while (mp[min])
            min++;
        mex[i]=min;
    }
    for (int i=1;i<=q;i++)
    {
        Que[i].q=i;
        scanf("%d%d",&Que[i].l,&Que[i].r);
    }
    sort(&Que[1],&Que[q+1],comp);
    //--预处理到此为止
    work();
    for (int i=1;i<=q;i++)
        printf("%d\n",QUERYANS[i]);
    return 0;
}
//--
//备注：
//mex问题
//对于给定的左边界，从这一个边界开始的mex一定是单调不减
//然后，就出结果了