poj 2823 线段树

赤裸裸的线段树，数据量很大，加了IO优化函数。

 

#include <stdio.h>

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define MIN(a, b) (a) < (b) ? (a): (b)
#define MAX(a, b) (a) > (b) ? (a): (b)

#define inf 20000000
#define N 1000001

struct tree_node
{
	int min, max;
};

struct tree_node tree[2097152];
int 	n, M;
int 	max[N], min[N];

/* IO优化 */
inline void put(int x){
	static char 	s[20];
	int				bas;

	if(x< 0) {
		putchar('-');
		x = -x;
	}
	if(x == 0) {
		putchar('0');
		return;
	}
	bas = 0;
	for(;x;x/=10) s[bas++] = x%10+'0';
	for(;bas--;) putchar(s[bas]);
}

inline void build_tree()
{
	int		i;

	//不用的叶子节点
	for (i = n+1; i%M != 1; i++) {
		tree[(i%M)+M].min = inf;
		tree[(i%M)+M].max = -inf;
	}
	//分支节点
	for (i = M-1; i > 0 ; i--) {
		tree[i].min = MIN(tree[i<<1].min, tree[(i<<1)+1].min);
		tree[i].max = MAX(tree[i<<1].max, tree[(i<<1)+1].max);
	}
}

inline void query(int s, int t)
{
	int 	i;

	i = s;
	max[i] = -inf;
	min[i] = inf;

	for (s = s+M-1, t = t+M+1; (s^t) != 1; s >>= 1, t >>= 1) {
		if (~s&1) {
			max[i] = MAX(max[i], tree[s^1].max);
			min[i] = MIN(min[i], tree[s^1].min);
		}
		if (t&1) {
			max[i] = MAX(max[i], tree[t^1].max);
			min[i] = MIN(min[i], tree[t^1].min);
		}
	}
}

int main()
{
	int		i, k;

	scanf("%d %d", &n, &k);
	for (M = 1; M < (n+2); M <<= 1);
	for (i = M+1; i <= n+M; i++) {
		scanf("%d", &tree[i].min);
		tree[i].max = tree[i].min;
	}

	build_tree();

	for (i = 1; i <= (n-k+1); i++) {
		query(i, i+k-1);
	}
	put(min[1]);
	for (i = 2; i <= (n-k+1); i++) {
		putchar(' ');
		put(min[i]);
	}
	putchar('\n');
	put(max[1]);
	for (i = 2; i <= (n-k+1); i++) {
		putchar(' ');
		put(max[i]);
	}
	putchar('\n');
	return 0;
}