题目大意

给出一个长度为N的非负整数序列A[i]，对于所有1 ≤ k ≤ (N + 1) / 2，输出A[1], A[3], …, A[2k - 1]的中位数。即前1，3，5，……个数的中位数。

题解

要找到中位数我们需要的序列是单调不减的，故可以用二叉平衡树解决。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAX_NODE = 100010;

struct SplayTree

{

private:

	struct Node

	{

		Node *LeftSon, *RightSon, *Father;

		int Key, Size, Count;

		Node(Node *fa, int key) : Father(fa), LeftSon(NULL), RightSon(NULL), Key(key), Size(1), Count(1){}

		bool IsLeftSon()

		{

			return Father->LeftSon == this;

		}

		void Refresh()

		{

			Size = (LeftSon ? LeftSon->Size : 0) + (RightSon ? RightSon->Size : 0) + Count;

		}

		bool IsRoot()

		{

			return Father == NULL || (Father->LeftSon != this && Father->RightSon != this);

		}

	}*Root;

	void Rotate(Node *cur)

	{

		Node *gfa = cur->Father->Father;

		Node **gfaSon = gfa ? (cur->Father->IsLeftSon() ? &gfa->LeftSon : &gfa->RightSon) : &Root;

		Node **faSon = cur->IsLeftSon() ? &cur->Father->LeftSon : &cur->Father->RightSon;

		Node **curSon = cur->IsLeftSon() ? &cur->RightSon : &cur->LeftSon;

		*faSon = *curSon;

		if (*faSon)

			(*faSon)->Father = cur->Father;

		*curSon = cur->Father;

		(*curSon)->Father = cur;

		*gfaSon = cur;

		(*gfaSon)->Father = gfa;

		(*curSon)->Refresh();

		cur->Refresh();

	}

	void PushDown() {}

	void Splay(Node *cur)

	{

		PushDown();

		while (cur->Father)

		{

			if (!cur->Father->IsRoot())

				Rotate(cur->Father->IsLeftSon() == cur->IsLeftSon() ? cur->Father : cur);

			Rotate(cur);

		}

	}

	int GetKeyByRank(Node *cur, int rank)

	{

		int rootSize, leftSize = (cur->LeftSon ? cur->LeftSon->Size : 0);

		if (rank <= leftSize)

			return GetKeyByRank(cur->LeftSon, rank);

		else if (rank <= (rootSize = leftSize + cur->Count))

			return cur->Key;

		else

			return GetKeyByRank(cur->RightSon, rank - rootSize);

	}

public:

	void Insert(int key)

	{

		Node **cur = &Root, *fa = NULL;

		while (*cur)

		{

			fa = *cur;

			if (key == (*cur)->Key)

			{

				(*cur)->Count++;

				Splay(*cur);

				return;

			}

			else if (key < (*cur)->Key)

				cur = &(*cur)->LeftSon;

			else if (key > (*cur)->Key)

				cur = &(*cur)->RightSon;

		}

		*cur = new Node(fa, key);

		Splay(*cur);

	}

	int GetKeyByRank(int rank)

	{

		return GetKeyByRank(Root, rank);

	}

}g;

int main()

{

	static int A[MAX_NODE];

	int n;

	scanf("%d", &n);

	for (int i = 1; i <= n; i++)

		scanf("%d", A + i);

	for (int i = 1; i <= n; i += 2)

	{

		g.Insert(A[i]);

		printf("%d\n", g.GetKeyByRank(i / 2 + 1));

		g.Insert(A[i + 1]);

	}

	return 0;

}

巴特西

luogu1168 中位数

题目大意

题解

最新文章

热门文章