「题解」优美序列 sequence(未完待续)

题目链接:JZOJ 6202/JZOJ 6279

#include<cstdio>
#include<algorithm>
using std::min;
using std::max;
int n,Log2[262144],T,Q;
struct Interval{
    int x,y;
    Interval(void){
        x=0;
        y=-1;
        return;
    }
    Interval(int a,int b){
        x=a;
        y=b;
        return;
    }
    bool operator !=(const Interval &a)const{
        return x!=a.x||y!=a.y;
    }
}ans;
Interval CP(const Interval &a,const Interval &b){
    return Interval(min(a.x,b.x),max(a.y,b.y));
}
struct ST{
    Interval a[18][262144];
    void Init(void){
        register int t,i;
        for(t=0;n>>(t+1);++t)
            for(i=1;i<=n;++i)
                a[ t+1 ][ i ]=CP( a[ t ][ i ],a[ t ][ i+( 1<<t ) ] );
    }
    Interval check(Interval x){
        int t=Log2[x.y-x.x+1];
        return CP(a[t][x.x],a[t][x.y-(1<<t)+1]);
    }
}a,p;
inline Interval Link(const Interval &x,const Interval &y){
    register Interval v=CP(x,y),s;
    while((s=p.check(a.check(v)))!=v){
        v=s;
    }
    return s;
}
struct VST{
    Interval a[18][ 262144 ];
    void Init(void){
        for ( register int t=0;n>>( t+1 );++t )
            for ( register int i=1;i<=n;++i )
                a[ t+1 ][ i ]=Link( a[ t ][ i ],a[ t ][ i+( 1<<t ) ] );
        /*register int t,i;
        for(t=0;n>>(t+1);++t)
            for(i=1;i<=n;++i)
                a[t+1][i]=Link(a[t][i],a[t][i+(1<<t)]);*/
    }
    inline Interval check( const int &l,const int &r ) {
        int t=Log2[ r-l+1 ];
        return Link( a[ t ][ l ],a[ t ][ r-( 1<<t )+1 ] );
    }
}ss;
int main(){
    //freopen("sequence.in","r",stdin);
    //freopen("sequence.out","w",stdout);
    register int i;
    scanf("%d",&n);
    for(i=2;i<=n;++i)
        Log2[i]=Log2[i>>1]+1;
    T=Log2[n];
    for(i=1;i<=n;++i){
        static int temp;
        scanf("%d",&temp);
        putchar('!');
        a.a[0][i]=Interval(temp,temp),
        p.a[0][Q]=ss.a[0][i]=Interval( i,i );
    }
    a.Init();
    printf("g");
    p.Init();
    printf("g");
    ss.Init();
    printf("g");
    scanf("%d",&Q);
    while(Q--){
        static int x,y;
        scanf("%d%d",&x,&y);
        ans=ss.check(x,y);
        printf("%d %d\n",ans.x,ans.y);
    }
    return 0;
}