题目链接:Click here~~
今天弄懂了这道被很多人称为水题的题。
题意:
给你一个数列{An},然后有m次查询,每次查询一段区间 [l,r] 内不大于 h 的值的个数。
解题思路:
稍加分析不难发现,问题的解满足区间减法的性质,即 ans[l,r] = ans[1,r] - ans[1,l-1] 。
于是想到可以用树状数组来存储前缀和。
然后,对数列{An} 和 所有查询的 h 排序,各自给它们一个指针 i 和 j 。 ( i 和 j 初始都指向数组排序后的第一个元素 )
接着,从前向后遍历每个查询(即 j 不断向后移),对于每个 i ,判断 A[i].h 与 Q[j].h 的关系。
1、若 A[i].h > Q[j].h,则从 i 以后的 A[i].h 也不会再对这个查询的解有影响。此时我们可以得到这个查询的解 sum(r) - sum(l-1) 。
2、若 A[i].h <= Q[j].h,则它会且仅会对从 j 以后的每个 Q[j].h 产生影响。于是我们需要在区间中对这个位置加1,然后让 i 向后移动。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100005
struct TT
{
int h,id;
bool operator < (const TT& s)const
{
return h < s.h;
}
}A[N];
struct QQ
{
int l,r,h,id;
bool operator < (const QQ& s)const
{
return h < s.h;
}
}Q[N];
int c[N],ans[N],n;
int lowbit(int x)
{
return x & -x;
}
void add(int loc,int val)
{
while(loc <= n)
{
c[loc] += val;
loc += lowbit(loc);
}
}
int sum(int loc)
{
int ans = 0;
while(loc > 0)
{
ans += c[loc];
loc -= lowbit(loc);
}
return ans;
}
int main()
{
int z,m,ncase = 0;
scanf("%d",&z);
while(z--)
{
memset(c,0,sizeof(c));
printf("Case %d:\n",++ncase);
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",&A[i].h);
A[i].id = i+1;
}
for(int j=0;j<m;j++)
{
scanf("%d%d%d",&Q[j].l,&Q[j].r,&Q[j].h);
Q[j].id = j;
}
sort(A,A+n);
sort(Q,Q+m);
for(int j=0,i=0;j<m;j++)
{
while(i<n && A[i].h <= Q[j].h)
{
add(A[i].id,1);
i++;
}
ans[Q[j].id] = sum(Q[j].r+1) - sum(Q[j].l);
}
for(int j=0;j<m;j++)
printf("%d\n",ans[j]);
}
return 0;
}
分享到:
相关推荐
离线OJ题库(HDU ZJU等,部分有答案),需联网。
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
杭州电子科技大学 oj离线版
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
算法-确定比赛名次(HDU-1285).rar
HDUOJ离线版(目前最新的版本),ACMER 的好帮手来啦啊!呵呵。。。版本也是目前最新的哦!
华为HLR相关资料,介绍了HLR中的HDU数据库单元原理
为了方便广大没有网络的朋友.......
HDU 1010-2500解题报告,ACMer可以借鉴一下
hdu2000-2014ac代码,虽然只有几道,但都是简单的
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
杭州电子科技大学OJ分类,很适合刚入门的新手哦,分类很详细,是不可多得的资料
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
hdu 期末考试复习资料 计算机网络 编译原理 计算机图形学 编译原理 信息安全与技术 数据库应用系统开发
ACM入门的课件适合于那些想要学习的ACM,提高自己编程能力的。
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器