#18421: 塊狀練表


a0905081237@gmail.com (哭哭饅頭)

School : Not Student
ID : 70032
IP address : [42.73.231.18]
Last Login :
2019-09-21 00:19:32
d801. SCOI2006 2.动态最值(minmax) -- SCOI2006第二题 | From: [111.82.153.116] | Post Date : 2019-07-11 21:53

這題正常人應該都用線段樹, 不過我還是試了塊狀練表, 這東西我不太熟, 求高人指點出可改進的部分

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
# define MIN -1000000001
# define MAX 1000000001

typedef struct data
{
int arr[2100], length, min, max ;
data *link, *pre ;
};
void ins(data *p, int num, int loc);
void update(data *p);
void cmp(data *p, int i);
void del(data *p, int loc);
void que(data *p, int left, int right);
data *make();
int min_ans = MAX ;
int max_ans = MIN ;
int size ;

int main()
{

    int n, m ;
    scanf("%d %d",&n,&m);
    size = sqrt(n)+4;
    size *= 2 ;
    data *head = make() ;
    head -> link = NULL ;
    head -> pre = NULL ;
    data *run = head ;
    for(int i = 0 ; i < n ; i++)
   {
         int a ;
         scanf("%d",&a);
         if( run -> length < size/2 )//建立塊狀練表
        {
             run -> arr[run -> length] = a ;
             cmp(run,run -> length);
             run -> length++;
        }
        else
        {    
              data *node = make();
              node -> link = run -> link ;
              run -> link = node ;
              node -> pre = run ;
              run = run -> link ;
              run -> arr[run -> length] = a ;
              cmp(run,run -> length);
              run -> length++;
        }
    }
    for(int i = 0 ; i < m ; i++)
   {
         int a, b, c ;
         scanf("%d",&a);
         if( a == 1 )
        {
             scanf("%d",&b); 
             del(head,b-1);
        }
        else
       {
             scanf("%d %d",&b,&c);
             que(head,b-1,c-1);
             printf("%d %d\n",min_ans,max_ans);
             min_ans = MAX ;
             max_ans = MIN ;
      }
   }
}
data *make()
{
    data *node = (data*)malloc(sizeof(data));
    node -> min = MAX ;
    node -> max = MIN ;
    node -> length = 0 ;
    return node ;
}
void cmp(data *p, int i)
{
    if( p -> arr[i] > p -> max )
        p -> max = p -> arr[i] ;
    if( p -> arr[i] < p -> min )
        p -> min = p -> arr[i] ;
}
void update(data *p)
{
    p -> min = MAX ;
    p -> max = MIN ;
    for(int i = 0 ; i < p -> length ; i++)
        cmp(p,i) ;
}
void del(data *p, int loc)
{

    for(int cnt = 0 ; cnt <= loc ; cnt += p->length, p = p->link)
    {
        if( cnt + p -> length > loc )//找到位置
        {
            int num = p -> arr[loc-cnt] ; // deleted number
            for(int i = loc-cnt ; i < p -> length ; i++)
            p -> arr[i] = p -> arr[i+1] ;

            p -> length--;
            if( num == p -> min || num == p -> max )
                update(p);

           if( p -> link && p -> length + p -> link -> length <= size/2 )// 兩個小節點合併
          {
              for(int i = p -> length, j = 0 ; j < p -> link -> length ; i++,j++)
             {
                   p -> arr[i] = p -> link -> arr[j] ;
                   cmp(p,i);
             }
             p -> length += p -> link -> length ;
             if( p -> link -> link )
                 p -> link -> link -> pre = p ;
             p -> link = p -> link -> link ;
         }
         if( p -> length == 0 )//把兩側節點抓起來
        {
             if( p -> pre )
                 p -> pre -> link = p -> link ;

             if( p -> link )
                 p -> link -> pre = p -> pre ;
        }
        break ;
        }

     }
}
void que(data *p, int left, int right)
{
    for(int cnt = 0 ; cnt <= right ; p = p -> link)
    {
    if( cnt + p -> length < left )//這節點完全不在範圍內
        cnt += p -> length ;

    else if( cnt >= left && cnt + p -> length <= right )//全在範圍內
    {
        if( p -> min < min_ans )
            min_ans = p -> min ;
        if( p -> max > max_ans )
            max_ans = p -> max ;
        cnt += p -> length ;
    }
    else //部分在範圍內,掃過去,如果在範圍內就比較大小
    {
    for(int i = 0 ; i < p -> length ; i++)
    {
        if( cnt >= left && cnt <= right )
        {
            if( p -> arr[i] < min_ans )
                min_ans = p -> arr[i] ;
            if( p -> arr[i] > max_ans )
                max_ans = p -> arr[i] ;
       }
       cnt++;
    }
}
}
}

 
ZeroJudge Forum