首页 > 编程语言 >hdu 4417(树状数组+离线算法)

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

时间:2023-05-29 19:38:31浏览次数:48  
标签:hdu 树状 4417 离线 h2 int num maxn include


解题思路:这道题要求某区间内比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("%d\n",ans[i]);
	}
	return 0;
}




标签:hdu,树状,4417,离线,h2,int,num,maxn,include
From: https://blog.51cto.com/u_16143128/6373647

相关文章

  • hdu 3681(bfs+dfs+状态压缩)
    解题思路:这道题属于图上来回走的问题,可以把重复走的过程弱化,即只强调从u->v的结果,中间经过的节点都不考虑。这道题里面'G','F','Y'是重要的节点,其余的点我们是可以忽略的,也就是说,假设从u->v,我们只需要知道最短路径是多少就可以了,至于是怎么走的,中间绕过了多少个'D'都不是我们关心的......
  • hdu 4012(bfs+位压缩)
    思路:每次涂色以后必有一个格子的颜色是最终的颜色,否则这次涂色根本没意义,所以我们把每次涂色后哪些格子成为最终颜色的所有可能都入队,入队的元素是一个struct包含步数和最终颜色已确定的木块集合,这个集合必须用整数表示,所以用到状态压缩,因为最多只有16个格子,所以用16位的二进制来表......
  • hdu 1593(数学)
    往相反的方面跑,但是,最理想的初始位置并不是圆点和圆上的某一点,应该还有更理想的初始逃跑状态.这里有一点需要注意,就是逃跑者极力想达到理想逃跑初态,而追赶者极力阻止逃跑者达到这一状态,所以,理想初态应该是无论追赶者如何阻止,逃跑者仍然可以达到的理想状态.最理想的......
  • hdu 3577(线段树区间更新)
    题意:输入一个t,表示有t组测试数据;         接下来一行,输入两个数,k,m,其中k表示这个辆车最多可以坐这么多人,m表示有m次询问能否上车;         每一次询问,输入两个数a,b,表示该乘客能否在a站台上车,b站台下车,乘车区间为(a,b--),先后次序;         即我每次询......
  • hdu 3172(并查集+hash)
    解题思路:典型的并查集,只是每个人的名字要转换成数字,可以用map,也可以用字典树,我最开始用的字典树结果爆内存了。。爆内存:#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintmaxn=200000;intn,fa[maxn],trie[maxn][52],cnt,id[2000000],nu......
  • hdu 2795(线段树)
    解题思路:这道题很难想到是用线段树,确实转化的很巧妙实际上,我们只需要利用线段树(记录1-h)维护哪个位置的剩余空间最大即可,即1,2,......,h是线段树的叶子节点,我们每次要找的就是叶子节点的剩余空间的最大值,只要能够想到这里就很容易啦。。另外如果h>n的话,就令h=n,否则就是类似于位置多......
  • hdu 1698(线段树区间更新)
    解题思路:线段树区间更新水题。#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintmaxn=100005;structseg{ intl,r,sum,lazy;}tree[maxn<<2];voidbuild(intl,intr,intu){ tree[u].l=l; tree[u].r=r; t......
  • hdu 1511(dp)
    解题思路:两次dp确实很巧妙,我只想到了一次dp算出最后那个数最小,其实题目要求还要保证第一个数尽可能大,一开始也没有注意到。。AC:#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<math.h>#include<stdlib.h>#include<time.h>usingnamesp......
  • hdu 5102(队列+节点扩展)
    TheK-thDistanceTimeLimit:8000/4000MS(Java/Others)    MemoryLimit:65536/65536K(Java/Others)ProblemDescriptionGivenatree,whichhasnnodeintotal.Definethedistancebetweentwonodeuandvisthenumberofedgeontheirunique......
  • hdu 5367(线段树+区间合并)
    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5367官方题解:对于求“高山脉”长度,可以利用线段树。树节点中保存左高度连续长度,左高度连续区间的高度,左高度连续区间的状态(即是否高于第一个高度不同的山),右高度连续长度,右高度连续区间的高度,右高度连续区间的状态,每段区间内的“......