http://ejq.me/2014/01/15/bzoj3339/
这道题还是在这里贴一下吧2333
http://blog.ejq.me/oi/2014/01/15/bzoj3339/
题解在这里
我用的离线做法
我们得知道以下几点内容:
- 从某一项开始的
mex 是单调不减序列 - 从第i项开始的
mex 序列能通过从第i−1 项开始的mex 序列在O(n) 的时间内修改得到
离线算法的复杂度为
- 首先,做出从第1项开始的
mex 序列,并与处理对于每一项Ai ,下一次出现该项的位置Nexti - 然后,如何将第i项变为第
i+1 项呢?我们只需要将(i,Nexti) 这一区间的所有大于Ai 的项改为Ai 即可 - 上一过程看起来是
O(n) 的,但事实上,平均每一次修改,我们至多修改O(logn) 项 - 我们能在
O(1) 的时间内作出单一询问的回答 - 重复这一过程,直到处理完讯问队列
下面是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一定是单调不减 //然后,就出结果了