2013年7月17日 星期三

2013/7/17 HSNU OJ 183 排隊

#include<iostream>
#include<cstdio>
using namespace std;
int m[2][800000];
void update(int flag, int k)
{
   
 
    if( flag == 0 )
    {
        if( m[flag][k*2+1] == -1 || m[flag][k*2+2] == -1 )
        {
            m[flag][k] = m[flag][k*2+1]+m[flag][k*2+2]+1;      
        }
        else{ m[flag][k] = min( m[flag][k*2+1], m[flag][k*2+2]); }
       
    }else
    {
        m[flag][k] = max( m[flag][k*2+1], m[flag][k*2+2]);  
    }
    if( k != 0 ){ update(flag, (k-1)/2); }
}
int ask(int flag, int k, int L, int R, int l, int r)
{
    if( R <= l || r <= L ){ return -1; }
    else if( l <= L && R <= r ){ return m[flag][k]; }
    else
    {
        int v1 = ask(flag, k*2+1, L, (L+R)/2, l, r);
        int v2 = ask(flag, k*2+2, (L+R)/2, R, l, r);
        if( flag == 0 )
        {
            if( v1 == -1 || v2 == -1 ){ return v1 + v2 + 1; }
            else{ return min(v1, v2); }
           
        }else
        {
            return max(v1, v2);
        }
    }
}
int main()
{
    int N, Q; scanf("%d %d", &N, &Q);
   
    int P = 1; while( P < N ){ P *= 2; }
   
    for(int i = 0; i <= P*2; i++){ m[0][i] = m[1][i] = -1;  }
    for(int i = 0; i < N; i++)
    {
        int t; scanf("%d", &t);
        m[0][P-1+i] = m[1][P-1+i] = t;
        update(0,(P-2+i)/2); update(1,(P-2+i)/2);
    }
   
   
    for(int i = 0; i < Q; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b); a--;
        int t1 = ask(1, 0, 0, P, a, b);
        int t2 = ask(0, 0, 0, P, a, b);
        printf("%d\n", t1 - t2);
    }
}

沒有留言:

張貼留言