2511616_mle.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
#define INIT (seg_tree *)malloc(sizeof(seg_tree))

int k, n;
int num[1000001];
typedef struct node
{
	int max, min;
}Ans;

typedef struct seg_tree
{
	Ans v;
	int L, R;
	struct seg_tree *l, *r;
}seg_tree;

seg_tree *root;

seg_tree *creat_seg_tree(seg_tree *s,int l,int r)
{
	int mid;
	seg_tree *p, *q;

	
	mid = (l+r)/2;
	s->L = l,s->R = r;
	if(l==r)
	{
		s->v.max = s->v.min = num[mid];
		s->l = NULL;
		s->r = NULL;
		return s;
	}
	p = INIT,q = INIT;
	s->l = creat_seg_tree(p,l,mid);
	s->r = creat_seg_tree(q,mid+1,r);
	s->v.max = Max(s->l->v.max,s->r->v.max);
	s->v.min = Min(s->l->v.min,s->r->v.min);
	return s;
}

int get_max(seg_tree *s,int l,int r)
{
	int mid;

	mid = (s->L+s->R)/2;
	if(s->L==l&&r==s->R)
		return s->v.max;
	if(l>mid)
		return get_max(s->r,l,r);
	else
		if(r<=mid)
			return get_max(s->l,l,r);
	return Max(get_max(s->l,l,mid),get_max(s->r,mid+1,r));
}

int get_min(seg_tree *s,int l,int r)
{
	int mid;

	mid = (s->L+s->R)/2;
	if(s->L==l&&r==s->R)
		return s->v.min;
	if(l>mid)
		return get_min(s->r,l,r);
	else
		if(r<=mid)
			return get_min(s->l,l,r);
	return Min(get_min(s->l,l,mid),get_min(s->r,mid+1,r));
}

int main()
{
	int i, tt;

	scanf("%d%d",&n,&k);
	for(i = 0; i < n; i++)
		scanf("%d",&num[i]);
	root = INIT;
	creat_seg_tree(root,0,n-1);
	for(i = 0; i <= n-k; i++)
	{
		num[i] = get_max(root,i,i+k-1);
		tt = get_min(root,i,i+k-1);
		printf("%d ",tt);
	}
	printf("\n");
	for(i = 0; i <= n-k; i++)
		printf("%d ",num[i]);
	printf("\n");
	return 0;
}