//why memory exceed???

#include<iostream>
using namespace std;

const int N=1000000;
int n, k, a[N];
struct Node
{
	short mx, mn;
	struct Node *lc, *rc;
	/*Node()
	{
		lc = NULL;
		rc = NULL;
	}*/
} *mx;

void creatmx(Node *&p, int &ii, int &jj)
{
	if(ii>jj)
		return;
	p = new Node;
	p->lc = NULL;
	p->rc = NULL;
	if(ii==jj)
		p->mx = p->mn = a[ii];
	else
	{
		int x;
		int mid = (ii+jj)/2;
		creatmx(p->lc, ii, mid);
		x = mid+1;
		creatmx(p->rc, x, jj);
		p->mx = __max(p->lc->mx, p->rc->mx);
		p->mn = __min(p->lc->mn, p->rc->mn);
	}
}

int findm(Node *&p, int &ii, int &jj, int &k, int &l)
{
	if(ii==k && jj==l)
		return p->mx;
	else 
	{
		int mid = (ii + jj)/2;
		if(l<=mid)
			return findm(p->lc, ii, mid, k, l);
		else if(k>mid)
		{
			int x = mid+1;
			return findm(p->rc, x, jj, k, l);
		}
		else// if(k<=mid && l>=mid)
		{
			int x = mid+1;
			int m1 = findm(p->lc, ii, mid, k, mid);
			int m2 = findm(p->rc, x, jj, x, l);
			if(m1 > m2)
				return m1;
			else
				return m2;
		}
	}
}
/*
void creatmn(Node *&p, int ii, int jj)
{
	if(ii>jj)
		return;
	p = new Node;
	if(ii==jj)
		p->mx = a[ii];
	else
	{
		int mid = (ii+jj)/2;
		creatmn(p->lc, ii, mid);
		creatmn(p->rc, mid+1, jj);
		p->mx = __min(p->lc->mx, p->rc->mx);
	}
}
*/

int findm1(Node *&p, int &ii, int &jj, int &k, int &l)
{
	if(ii==k && jj==l)
		return p->mn;
	else 
	{
		int mid = (ii + jj)/2;
		if(l<=mid)
			return findm1(p->lc, ii, mid, k, l);
		else if(k>mid)
		{
			int x = mid+1;
			return findm1(p->rc, x, jj, k, l);
		}
		else// if(k<=mid && l>=mid)
		{
			int x = mid+1;
			int m1 = findm1(p->lc, ii, mid, k, mid);
			int m2 = findm1(p->rc, x, jj, x, l);
			if(m1 < m2)
				return m1;
			else
				return m2;
		}
	}
}
int main()
{
	int i, st, en, ii, jj;
	scanf("%d%d", &n, &k);
	for(i=0; i<n; i++)
		scanf("%d", &a[i]);
	st = 0;
	en = n-1;
	creatmx(mx,st, en);

	for(i=0; i<n-k; i++)
	{
		ii=i,jj=i+k-1;
		printf("%d ", findm1(mx, st, en, ii, jj));
	}
	ii = n-k, jj = n-1;
	printf("%d\n", findm1(mx, st, en, ii, jj));
	for(i=0; i<n-k; i++)
	{
		ii = i, jj=i+k-1;
		printf("%d ", findm(mx, st, en, ii, jj));
	}
	ii = n-k, jj=n-1;
	printf("%d\n", findm(mx, st, en, ii, jj));

	return 0;
}

• Re:为什么超内存 ，用链表写的线段树，，求解 (15) wangyaoxuan 2010-08-13 21:25:08