题解：P14233 [COI 2011] 收视率 / TELKA

· · 题解

思路

当看到区间加法（居民持续观看电视）与区间查询（特别关注时间区间内的平均收视热度）时就可以意识到这是一道线段树板子题了。

我们以一天 86400 秒开一个对应 4 倍空间的线段树，初始赋值为 0。对于每一个居民的持续观看时间，我们可以将对应区间内每秒的人数都加一。对于每一次询问，为防止精度丢失，我选择在查询操作时返回一个 pair 类型，分别记录总人数与总秒数，最后相除后输出就行。

对于跨天的特殊情况，我们可以将其拆分为两次进行增加/查询，分别为 l 时间到最大 86399 秒与 0 秒到 r 时间。（最后别忘了开 long long。）

参考代码

#include<bits/stdc++.h>
#define int long long//不开long long最后2个点会爆
using namespace std;
const int inf=0x3f3f3f3f;
const int N=86405;
const int furina=86400;
inline int rd()
{
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s<='9'&&s>='0'){x=x*10+(s^48);s=getchar();}
    return x*f;
}
int n,q;
struct op{
    int num,l,r,lazy;
}tree[N*4]={0};
void push_down(int p)
{
    tree[p*2].lazy+=tree[p].lazy;
    tree[p*2].num+=tree[p].lazy*(tree[p*2].r-tree[p*2].l+1);
    tree[p*2+1].lazy+=tree[p].lazy;
    tree[p*2+1].num+=tree[p].lazy*(tree[p*2+1].r-tree[p*2+1].l+1);
    tree[p].lazy=0;
    return;
}
void build(int p,int l,int r)
{
    tree[p].num=0;
    tree[p].l=l;
    tree[p].r=r;
    if(l==r)
    {
        return;
    }
    build(p*2,l,(l+r)/2);
    build(p*2+1,(l+r)/2+1,r);
    return;
}
void add(int p,int l,int r,int l1,int r1)
{
    if(l>=l1&&r<=r1)
    {
        tree[p].lazy++;
        tree[p].num+=tree[p].r-tree[p].l+1;
        return;
    }
    push_down(p);
    int mid=(l+r)/2;
    if(mid>=l1)add(p*2,l,mid,l1,r1);
    if(mid<r1)add(p*2+1,mid+1,r,l1,r1);
    tree[p].num=tree[p*2].num+tree[p*2+1].num;
    return;
}
pair<long long,int>sum(int p,int l,int r,int l1,int r1)
{
    if(l>=l1&&r<=r1)
    {
        return make_pair((long long)tree[p].num,tree[p].r-tree[p].l+1);
    }
    push_down(p);
    int mid=(l+r)/2;
    pair<long long,int>fufu1(0LL,0),fufu2(0LL,0);
    if(mid>=l1)
    {
        fufu1=sum(p*2,l,mid,l1,r1);
    }
    if(mid<r1)
    {
        fufu2=sum(p*2+1,mid+1,r,l1,r1);
    }
    return make_pair(fufu1.first+fufu2.first,fufu1.second+fufu2.second);
}
signed main()
{
    build(1,0,furina-1);//初始赋值为0
    n=rd();
    for(int i=1;i<=n;i++)
    {
        int fufu3,fufu4,fufu5,fufu6,fufu7,fufu8;
        scanf("%lld:%lld:%lld - %lld:%lld:%lld",&fufu3,&fufu4,&fufu5,&fufu6,&fufu7,&fufu8);
        if(fufu3<fufu6||(fufu3==fufu6&&fufu4<fufu7)||(fufu3==fufu6&&fufu4==fufu7&&fufu5<=fufu8))
        {
            add(1,0,furina-1,fufu3*3600+fufu4*60+fufu5,fufu6*3600+fufu7*60+fufu8);//注意时间是从0到86399
        }
        else
        {
            add(1,0,furina-1,fufu3*3600+fufu4*60+fufu5,furina-1);
            add(1,0,furina-1,0,fufu6*3600+fufu7*60+fufu8);
        }
    }
    q=rd();
    while(q--)
    {
        pair<long long,int>funingna1;
        pair<long long,int>funingna2;
        int fufu3,fufu4,fufu5,fufu6,fufu7,fufu8;
        scanf("%lld:%lld:%d - %lld:%lld:%lld",&fufu3,&fufu4,&fufu5,&fufu6,&fufu7,&fufu8);
        if(fufu3<fufu6||(fufu3==fufu6&&fufu4<fufu7)||(fufu3==fufu6&&fufu4==fufu7&&fufu5<=fufu8))
        {
            funingna1=sum(1,0,furina-1,fufu3*3600+fufu4*60+fufu5,fufu6*3600+fufu7*60+fufu8);
            long double ans=1.00000000*funingna1.first/funingna1.second;
            printf("%.6Lf\n",ans);
        }
        else
        {
            funingna1=sum(1,0,furina-1,fufu3*3600+fufu4*60+fufu5,furina-1);
            funingna2=sum(1,0,furina-1,0,fufu6*3600+fufu7*60+fufu8);
            long double ans=1.00000000*(funingna1.first+funingna2.first)/(funingna1.second+funingna2.second);//最后再计算防止精度损失
            printf("%.6Lf\n",ans);
        }
    }
    return 0;
}