HDU 4325

95 阅读 0 评论 63 点赞

我是靠谱客的博主精明灯泡，最近开发中收集的这篇文章主要介绍HDU 4325，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目很简单

一共 T 组数据每次输入 n 个花的花期 S --- T 然后输入 m 次查询，输入时间 t ，问 t 时间有几朵花是开着的

简单的树状数组解决，输入开花时间时我们把开花时间后边的全部向上更新 +1 一下，然后输入结束时间再更新一次 -1.。

这道题就出来了。。这道题。。很不错。。更好的了解了树状数组 add 函数更新的特点。（注意输出格式）

以下为 AC 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100005;
int n,m;
int sum[maxn];
int lowbit(int x)
{
    return x&(-x);
}
void add(int id, int val)
{
    while(id<=maxn)
    {
        sum[id] += val;
        id += lowbit(id);
    }
}
int query(int id)
{
    int res = 0;
    while(id>0)
    {
        res += sum[id];
        id -= lowbit(id);
    }
    return res;
}
int main()
{
    int t;
    int a,b,c;
    scanf("%d",&t);
    int i=1;
    while(t--)
    {
        printf("Case #%d:n",i++);
        memset(sum,0,sizeof(sum));
        scanf("%d%d",&n,&m);
        while(n--)
        {
            scanf("%d%d",&a,&b);
            add(a,1);
            add(b+1,-1);
        }
        while(m--)
        {
            scanf("%d",&c);
            printf("%dn",query(c));
        }
    }
    return 0;
}