Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

贴个代码,并提示一下可能错的一个地方:不能用cin

Posted by a280920481 at 2018-11-29 22:11:17 on Problem 1769
#include <iostream>
using namespace std;


int dat[1 << 17];//线段树

int n_;//线段树最深一层的首元素下标

int init(const int & n);//将所有值初始化为足够大的数

void update(int s, int v);//将第 s 个数更新为 v

int query(int & left, int & right, int k, int begin, int end);//返回 [left, right] 的最小值

inline int getvalue(int & s);//返回第 s 个数的值

int main()
{
	int n, m, lb, rb, mina;

	cin >> n >> m;

	n_ = init(n);

	update(1, 0);//当只有 1 个数时只需要 0 个 Sorter

	for (int i = 0; i < m; i++)
	{
		//cin >> lb >> rb;//会导致超时

		scanf_s("%d%d", &lb, &rb);

		mina = query(lb, rb, 0, 0, n_);
		if (mina + 1 < getvalue(rb))
		{
			update(rb, mina + 1);
		}
	}

	cout << getvalue(n) << '\n';

	return 0;
}

int init(const int & n)
{
	int m = 1;

	while (m < n)
	{
		m <<= 1;
	}

	m = (2 * m) - 1;//此时 m 为树的节点个数

	for (int i = 0; i < m; i++)
	{
		dat[i] = 1 << 30;
	}

	return m >> 1;
}

void update(int s, int v)
{
	s += n_;
	dat[s] = v;

	do
	{
		s = (s - 1) >> 1;
		if (dat[s] > v)
		{
			dat[s] = v;
		}
		else
		{
			break;
		}
	} while (s);

	return;
}

int query(int & left, int & right, int k, int begin, int end)
{
	if ((end >= left) && (begin <= right))
	{
		if ((left <= begin) && (end <= right))
		{
			return dat[k];
		}
		else if (k < n_)
		{
			int mid = (begin + end) >> 1, lv, rv;
			lv = query(left, right, (k << 1) + 1, begin, mid);
			rv = query(left, right, (k << 1) + 2, mid + 1, end);
			if (lv < rv)
			{
				return lv;
			}
			else
			{
				return rv;
			}
		}
	}
	return 1 << 30;
}

inline int getvalue(int & s)
{
	return dat[s + n_];
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator