题目传送门：http://tyvj.cn/p/4866
题目分析：做清北学堂NOIP模拟赛1的时候见到这题，一开始想了好久只会 O(Qm−−√log(n)) 的莫队，就是一边做莫队一边用线段树维护最左边的两个空摊位。后来tututu过来看到这题，转了两圈立马就想出了 O(Qlog(m)) 的正解做法……
我们先用 f[i] 表示 a[1] ~ a[i] 的摊位都被占用时答案是多少，很明显 f[i] 单调不降，一开始单调往后扫一遍即可得到每一个f值。现在我们考虑区间左端点右移时对f值的影响，比如当左端点变为2的时候， a[1] 就空出来了。假设 a[1]>1 ，且 a[j]=a[1]−1 ，那么 f[i](2<=i<j) 都可以考虑更新为 a[1]−1 （若j不存在则j=m+1）；假设 a[1]<n ，若 a[k]=a[1]+1 ，那么 f[i](2<=i<k) 都可以考虑更新为 a[1] 。这样f数组就可以用一棵线段树维护。
我听了之后很激动，然后码了45min，结果发现一直调不对手出的小数据，最后快到12点了，只好交上错的程序，再后来又调了15min发现两个m打成了n……
几天后我又交了我的程序上tyvj，结果爆10了，下了个小数据发现a数组的值可能重复，这样我们还要开一个数组记对于每一个i，离它最近的 a[j]=a[i](j>i) 是哪个，记 Next[i]=j ，然后在线段树更新的时候要分别跟 Next[i] 取min。
听说这题没有卡莫队，所以其实我一开始的方法也可能AC，结果中途转去写了tututu的方法，我就爆零了。Coming和Ab.Ever也写了这种方法，一个爆10一个爆0。我这次比赛500分，就差这题的分，唉。 Ab.Ever：早知码暴力，不听tu装逼。
CODE：
#include<iostream> #include<string> #include<cstring> #include<cmath> #include<cstdio> #include<cstdlib> #include<stdio.h> #include<algorithm> using namespace std; const int maxn=200100; struct data { int l,r,t; } ask[maxn]; int tree[maxn<<2]; int b[maxn]; int vis[maxn]; int Next[maxn]; int val[maxn]; int a[maxn]; int ans[maxn]; int n,m,q; bool Comp(data x,data y) { return ( x.l<y.l || ( x.l==y.l && x.r<y.r ) ); } void Build(int root,int L,int R) { if (L==R) { tree[root]=b[L]; return; } int mid=(L+R)>>1; int Left=root<<1; int Right=Left|1; Build(Left,L,mid); Build(Right,mid+1,R); tree[root]=maxn; } void Update(int root,int L,int R,int x,int y,int v) { if ( y<L || R<x ) return; if ( x<=L && R<=y ) { tree[root]=min(tree[root],v); return; } int mid=(L+R)>>1; int Left=root<<1; int Right=Left|1; Update(Left,L,mid,x,y,v); Update(Right,mid+1,R,x,y,v); } void Down(int root) { int Left=root<<1,Right=Left|1; tree[Left]=min(tree[Left],tree[root]); tree[Right]=min(tree[Right],tree[root]); tree[root]=maxn; } int Query(int root,int L,int R,int x) { if ( L==x && x==R ) return tree[root]; Down(root); int mid=(L+R)>>1; int Left=root<<1; int Right=Left|1; if (x<=mid) return Query(Left,L,mid,x); else return Query(Right,mid+1,R,x); } int main() { freopen("stall.in","r",stdin); freopen("stall.out","w",stdout); scanf("%d%d%d",&n,&m,&q); for (int i=1; i<=m; i++) scanf("%d",&a[i]); for (int i=1; i<=q; i++) scanf("%d%d",&ask[i].l,&ask[i].r),ask[i].t=i; sort(ask+1,ask+q+1,Comp); for (int i=1; i<=n; i++) val[i]=m+1; for (int i=m; i>=1; i--) Next[i]=val[ a[i] ],val[ a[i] ]=i; b[1]=1; if (a[1]==1) b[1]=2; vis[ a[1] ]++; for (int i=2; i<=m; i++) { vis[ a[i] ]++; b[i]=b[i-1]; while ( vis[ b[i] ] || vis[ b[i]+1 ] ) b[i]++; } Build(1,1,m); int tail=0; while (ask[tail+1].l==1) tail++,ans[ ask[tail].t ]=Query(1,1,m,ask[tail].r); for (int L=2; L<=m; L++) { int x=a[L-1]; val[x]=Next[L-1]; if (x) Update(1,1,m,L-1, min(val[x-1],val[x])-1 ,x-1); if (x<=n) Update(1,1,m,L-1, min(val[x],val[x+1])-1 ,x); while (ask[tail+1].l==L) tail++,ans[ ask[tail].t ]=Query(1,1,m,ask[tail].r); } for (int i=1; i<=q; i++) if (ans[i]<n) printf("%d %d\n",ans[i],ans[i]+1); else printf("-1 -1\n"); return 0; }