BZOJ-3339: Rmq Problem（离散化+线段树（O

题目：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;

}