BZOJ3339/Rmq Problem

Posted on By 二价氢

题解在这里

我用的离线做法

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

  1. 从某一项开始的是单调不减序列
  2. 从第项开始的序列能通过从第项开始的序列在的时间内修改得到

离线算法的复杂度为

  1. 首先,做出从第1项开始的序列,并与处理对于每一项,下一次出现该项的位置
  2. 然后,如何将第项变为第项呢?我们只需要将这一区间的所有大于的项改为即可
  3. 上一过程看起来是的,但事实上,平均每一次修改,我们至多修改
  4. 我们能在的时间内作出单一询问的回答
  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一定是单调不减
//然后,就出结果了