hdu 4417(树状数组+离线算法)

60 阅读 0 评论 40 点赞

我是靠谱客的博主无聊砖头，最近开发中收集的这篇文章主要介绍hdu 4417(树状数组+离线算法)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

解题思路：这道题要求某区间内比h小的个数，其实这里可以类似于树状数组求逆序数那样。关键是如何转换成树状数组的模型，这才是本题的难点。

我们首先分析，如果知道h在该区间的哪个位置，那么剩下的就很好做了。我们还可以发现，如果找到了当前的比h小的所有点（大于的点我们先忽略掉），那么我们就可以用树状数组求它的[l,r]区间的和。这样就跟树状数组有了一点联系，但是还不够，因为我们发现，h的大小会影响我们所要找的区间。什么意思呢？就是我们先找到的是h1，再找h2，但h1>h2，就会出现这样的问题：h1所对应的区间找到了，但再找h2时，它对应的区间中可能会有比h2大的数，这样就不符合条件了。所以说这里有一个离线算法，就是先把所有的询问存下来，再按照h的大小进行从小到大排序，然后根据h的大小，从小到大地一个个插入所有区间内的数，这样就符合条件了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 1e5+5;
struct Query
{
	int l,r,h;
	int id;
	bool operator < (Query a)
	{
		return h < a.h;
	}
}q[maxn];
struct Node
{
	int num;
	int id;
	bool operator < (Node a)
	{
		return num < a.num;
	}
}a[maxn];
int n,m;
int tree[maxn<<2],ans[maxn];

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

void update(int x,int d)
{
	for(int i = x; i <= n; i += lowbit(i))
		tree[i] += d;
}

int getsum(int x)
{
	int sum = 0;
	for(int i = x; i > 0; i -= lowbit(i))
		sum += tree[i];
	return sum;
}

int main()
{
	int t,cas = 1;
	cin >> t;
	while(t--)
	{
		cin >> n >> m;
		for(int i = 1; i <= n; i++)
		{
			cin >> a[i].num;
			a[i].id = i;
		}
		for(int i = 1; i <= m; i++)
		{
			cin >> q[i].l >> q[i].r >> q[i].h;
			q[i].l++, q[i].r++;
			q[i].id = i;
		}
		sort(a+1,a+1+n);
		sort(q+1,q+1+m);
		memset(tree,0,sizeof(tree));
		int idx = 1;
		for(int i = 1; i <= m; i++)
		{
			while(q[i].h >= a[idx].num && idx <= n)
			{
				update(a[idx].id,1);
				idx++;
			}
			ans[q[i].id] = getsum(q[i].r) - getsum(q[i].l-1);
		}
		printf("Case %d:n",cas++);
		for(int i = 1; i <= m; i++)
			printf("%dn",ans[i]);
	}
	return 0;
}