#18421: 塊狀練表

#### a0905081237@gmail.com (哭哭饅頭)

School : No School
ID : 70032
2020-05-18 00:09:56
d801. SCOI2006 2.动态最值(minmax) -- | 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 ;
};
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 ;
head -> pre = NULL ;
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();
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);
}
else
{
scanf("%d %d",&b,&c);
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 -> length == 0 )//把兩側節點抓起來
{
if( p -> pre )

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