hdu4325-Flowers（树状数组-区间更新单点查询）Flowers

89 阅读 0 评论 59 点赞

我是靠谱客的博主陶醉白云，最近开发中收集的这篇文章主要介绍hdu4325-Flowers（树状数组-区间更新单点查询）Flowers，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=4325

题目原文：

Flowers
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3898 Accepted Submission(s): 1921

Problem Description

As is known to all, the blooming time and duration varies between different kinds of flowers. Now there is a garden planted full of flowers. The gardener wants to know how many flowers will bloom in the garden in a specific time. But there are too many flowers in the garden, so he wants you to help him.

Input

The first line contains a single integer t (1 <= t <= 10), the number of test cases.
For each case, the first line contains two integer N and M, where N (1 <= N <= 10^5) is the number of flowers, and M (1 <= M <= 10^5) is the query times.
In the next N lines, each line contains two integer Si and Ti (1 <= Si <= Ti <= 10^5), means i-th flower will be blooming at time [Si, Ti].
In the next M lines, each line contains an integer Ti, means the time of i-th query.

Output

For each case, output the case number as shown and then print M lines. Each line contains an integer, meaning the number of blooming flowers.
Sample outputs are available for more details.

Sample Input
 
2
1 1
5 10
4
2 4
1 4
4 8
1
4
6
9

Sample Output
 
Case #1:
0
Case #2:
1
2
1
0

题目大意：已知花有开发时间和凋谢时间，询问在某一时刻，有多少花是盛开状态。第一行给出T（测试样例数量），接下来一行n, m分别表示n行更新m行询问。

解题思路：使用树状数组区间更新单点查询方法，设a[i]为第i朵花盛开次数，dif[i]为a[i]-a[i-1]，那么求a[i]的值的时候a[i]=a[i-1]+dif[i]=a[i-2]+dif[i]+dif[i-1]=…..=dif[1]+dif[2]+…+dif[i]。针对dif[i]建立树状数组，更新[l, r]区间可以视作update(l, 1)即a[l]与之前的差值加1，并且update(r+1, -1)即a[r+1]与之前的差值都减少1.

AC代码：

/**
 * (树状数组)-区间更新-单点查询
 */
#include <cstdio>
#include <cstring>
using namespace std;

const int N = int(1e5 +5);

int g_n, g_m;
int g_difA[N]; // 表示a[i]与a[i-1]的差值，difA[i] = a[i] - a[i-1];

void init()
{
	memset(g_difA, 0, sizeof(g_difA));
}

int lowbit(const int &x)
{
	return x & (-x);
}

void update(int idx, const int &difVal)
{
	while (idx < N)
	{
		g_difA[idx] += difVal;
		idx += lowbit(idx);
	}
}

// 区间[l, r]更新difVal值
void update(const int &l, const int &r, const int &difVal)
{
	update(l, difVal); // a[l]与之前的差值都增加difVal
	update(r + 1, -difVal); // a[r+1]与之前的差值都减少difVal
}

int calcSum(int idx)
{
	int s = 0;
	while (idx > 0)
	{
		s += g_difA[idx];
		idx -= lowbit(idx);
	}
	return s;
}

int main()
{
	int T, a, b, i;
	scanf("%d", &T);
	int I = 0;
	while (T--)
	{
		init();
		printf("Case #%d:n", ++I);
		scanf("%d%d", &g_n, &g_m);
		for (i = 0; i < g_n; i++)
		{
			scanf("%d%d", &a, &b);
			update(a, b, 1);
		}
		for (i = 1; i <= g_m; i++)
		{
			scanf("%d", &a);
			printf("%dn", calcSum(a));
		}
	}
	return 0;
}