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

Re:水题,1A,附代码

Posted by 522413 at 2020-08-13 11:04:29 on Problem 3264
In Reply To:水题,1A,附代码 Posted by:bryant03 at 2014-09-26 20:54:03
> #include <cstdio>
> #include <algorithm>
> #include <cstring>
> using namespace std;
> int m_ax, m_in;
> int a[50010];
> struct node
> {
> 	int l, r, m_ax, m_in;
> }tree[200000];
> void build(int n, int l, int r)
> {
> 	tree[n].l = l;
> 	tree[n].r = r;
> 	if (l == r)
> 	{
> 		tree[n].m_ax = a[l];
> 		tree[n].m_in = a[l];
> 		return;
> 	}
> 	int mid = (l + r) / 2;
> 	build(n * 2, l, mid);
> 	build(n * 2 + 1, mid + 1, r);
> 	tree[n].m_ax = max(tree[n * 2].m_ax, tree[n * 2 + 1].m_ax);
> 	tree[n].m_in = min(tree[n * 2].m_in, tree[n * 2 + 1].m_in);
> }
> 
> void query(int n, int l, int r)
> {
> 	if (tree[n].l == l&&tree[n].r == r)
> 	{
> 		m_ax = max(m_ax, tree[n].m_ax);
> 		m_in = min(m_in, tree[n].m_in);
> 		return;
> 	}
> 	int mid = (tree[n].l + tree[n].r) / 2;
> 	if (r <= mid)
> 	{
> 		query(n * 2, l, r);
> 	}
> 	else if (l > mid)
> 	{
> 		query(n * 2 + 1, l, r);
> 	}
> 	else
> 	{
> 		query(n * 2, l, mid);
> 		query(n * 2 + 1, mid + 1, r);
> 	}
> }
> 
> int main()
> {
> 	int n, q, s, b;
> 	while (~scanf("%d%d", &n, &q))
> 	{
> 		memset(a, 0, sizeof(a));
> 		memset(tree, 0, sizeof(tree));
> 		for (int i = 1; i <= n; i++)
> 			scanf("%d", &a[i]);
> 		build(1, 1, n);
> 	/*	for (int i = 1; i <= 20; i++)
> 		{
> 			m_ax = 0;
> 			m_in = 1000000;
> 			printf_s("%d %d %d %d\n", tree[i].l, tree[i].r, tree[i].m_ax, tree[i].m_in);
> 		}*/
> 
> 
> 		for (int i = 1; i <= q; i++)
> 		{
> 			m_ax = 0;
> 			m_in = 1000000;
> 			scanf("%d%d", &s, &b);
> 			query(1,s,b);
> 			printf("%d\n",m_ax-m_in);
> 		}
> 	}
> 	return 0;
> }

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