题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3339
突然发现自己智商拙计了，想了大半天才会写。。。首先，把0...Max+1的所有数以及数列中的数放在一起离散化，然后预处理出哪些区间里面缺少哪些数，然后把这些区间和查询按照左端点排序，扫描一遍。扫描中，对于当前区间[l,r],x表示区间[l,r]缺少x，在线段树的r位置加入x，维护最小值，对于每个查询区间，答案就是Min(r..n) 。复杂度O((n+m) log n)
代码：
写了半天，就懒得加常数优化了。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std ;
#define MAXN 800010
#define inf 0x7fffffff
struct SGT{
int L[ MAXN *4], R[ MAXN *4], Min[ MAXN *4];
void Build(int l ,int r ,int t ){
L[ t ]= l , R[ t ]= r , Min[ t ]= inf ;
if( l == r )return;
Build( l ,( l + r )>>1, t <<1);
Build((( l + r )>>1)+1, r ,( t <<1)^1);
}
void Change(int pos ,int k ,int t ){
if( L[ t ]== R[ t ]){
Min[ t ]= k ;return;
}
int mid =( L[ t ]+ R[ t ])>>1;
if( pos <= mid )Change( pos , k , t <<1)
;else Change( pos , k ,( t <<1)^1);
Min[ t ]=min( Min[ t <<1], Min[( t <<1)^1]);
}
int Query(int l ,int r ,int t ){
if( l == L[ t ]&& r == R[ t ])return Min[ t ];
int mid =( L[ t ]+ R[ t ])>>1;
if( r <= mid )return Query( l , r , t <<1);
if( l > mid )return Query( l , r ,( t <<1)^1);
return min(Query( l , mid , t <<1),Query( mid +1, r ,( t <<1)^1));
}
} sgt ;
struct saver{
int v , t ;
bool operator <(const saver &a )const{
return( v < a.v ||( v == a.v && t < a.t ));
}
} a[ MAXN ];
int n , m , Max =0, N =0;
struct rtype{
int l , r , x ;
bool flag ;
rtype *next ;
}*head[ MAXN ];
void Insert1(int l ,int r ,int x ){
rtype *p =new( rtype );
p -> l = l , p -> r = r , p -> x = x , p -> flag =true;
p -> next = head[ l ]; head[ l ]= p ;
}
void Insert0(int l ,int r ,int x ){
rtype *p =new( rtype );
p -> l = l , p -> r = r , p -> x = x , p -> flag =false;
p -> next = head[ r +1]; head[ r +1]= p ;
}
struct qtype{
int l ,r , t ;
bool operator <(const qtype &a )const{
return l < a.l ;
}
} Q[ MAXN ];
int ans[ MAXN ], S[ MAXN ];
int main( ){
scanf("%d%d",&n ,&m );
for(int i =0 ; i ++< n ;)scanf("%d",&a[ i ].v ), a[ i ].t = i , Max =max( Max , a[ i ].v );
++ Max ;
N = n ;
for(int i =0; i <= Max ; i ++){
a[++ N ].v = i ;
a[ N ].t =0;
a[++ N ].v = i ;
a[ N ].t = n +1;
}
sort( a +1, a + N +1);
memset( head ,0,sizeof( head ));
for(int i =1; i ++< N ;)if( a[ i ].t > a[ i -1].t +1&& a[ i ].v == a[ i -1].v ){
Insert1( a[ i -1].t +1, a[ i ].t -1, a[ i ].v );
Insert0( a[ i -1].t +1, a[ i ].t -1, a[ i ].v );
}
for(int i =0; i ++< n ;) S[ i ]= inf ;
for(int i =0; i ++< m ;)scanf("%d%d",&Q[ i ].l ,&Q[ i ].r ), Q[ i ].t = i ;
sort( Q +1, Q + m +1);
int q =1;
sgt.Build(1, n ,1);
for(int i =0; i ++< n ;){
for( rtype *p = head[ i ]; p ; p = p -> next ){
if( p -> flag ){
S[ p -> r ]=min( S[ p -> r ], p -> x );
}
sgt.Change( p -> r , S[ p -> r ],1);
}
for(; q <=m && Q[ q ].l == i ; q ++){
ans[ Q[ q ].t ]= sgt.Query( Q[ q ].r , n ,1);
}
}
for(int i =0; i ++< m ;)printf("%d\n", ans[ i ]);
return 0;
}
