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

· · 题解

发现平均值等于区间和除以区间长度，而每个居民可以看作一个区间，然后就发现就是区间增加 1，区间求和，考虑线段树，是个模板。

但是题目中存在这样一句话：“需注意，部分居民可能在前一天深夜开始观看电视（例如 23:45:30），并在次日结束观看（例如 01:15:00）。”

然后我们考虑将这些区间分成两块，一块是前一天，一块是后一天，然后问询的区间也可以分成两块。

最后一个难点是时间处理，我发现中间的冒号和杠是不会被整型变量读入，只会被字符变量读入的，于是我采用整型数和标志符分离的方式，具体可以看代码。我将一个时间哈希了一下，变成 H \times 60^2+M \times 60+S，这样保证不产生哈希冲突。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=300009,INF=2e9;
ll n,m,MOD;
struct Segment{
    ll l;
    ll r;
    ll len;
    ll sum;
    ll toAdd;
};
Segment tr[N*4];
void build(ll u,ll l,ll r){
    if(l==r){
        tr[u]=(Segment){l,r,r-l+1,0,0};
        return;
    }
    ll m=(l+r)/2; 
    build(u*2,l,m);
    build(u*2+1,m+1,r);
    tr[u]=(Segment){l,r,r-l+1,tr[u*2].sum+tr[u*2+1].sum,0};
}
void pushdown(ll u){
    if(tr[u].l==tr[u].r) return;
    ll A=tr[u].toAdd;
    tr[u].toAdd=0;
    tr[u*2].sum+=tr[u*2].len*A;
    tr[u*2+1].sum+=tr[u*2+1].len*A;
    tr[u*2].toAdd+=A;
    tr[u*2+1].toAdd+=A;
}
void add(ll u,ll l,ll r,ll delta){
    pushdown(u);
    if(r<tr[u].l||tr[u].r<l) return;
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].toAdd+=delta;
        tr[u].sum+=tr[u].len*delta;
        return;
    }
    add(u*2,l,r,delta);
    add(u*2+1,l,r,delta);
    tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
}
ll rsq(ll u,ll l,ll r){
    pushdown(u);
    if(r<tr[u].l||tr[u].r<l) return 0;
    else if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum;
    return rsq(u*2,l,r)+rsq(u*2+1,l,r);
}
int main(){
    ll n;
    cin>>n;
    build(1,1,86400);
    for(ll i=1;i<=n;i++){
        ll x,y,z,a,b,c;
        char op;
        cin>>x>>op>>y>>op>>z>>op>>a>>op>>b>>op>>c;
        ll l=x*3600+y*60+z;
        ll r=a*3600+b*60+c;
        l++;r++;
        if(l>r){
            add(1,l,86400,1);
            add(1,1,r,1);
        }
        else add(1,l,r,1); 
    }
    ll q;
    cin>>q;
    for(ll i=1;i<=q;i++){
        ll x,y,z,a,b,c;
        char op;
        cin>>x>>op>>y>>op>>z>>op>>a>>op>>b>>op>>c;
        ll l=x*3600+y*60+z;
        ll r=a*3600+b*60+c;
        l++;r++;
        if(l>r)
            cout<<fixed<<setprecision(10)<<((double)rsq(1,l,86400)+rsq(1,1,r))/(r+86400-l+1)<<endl;
        else
            cout<<fixed<<setprecision(10)<<((double)rsq(1,l,r))/(r-l+1)<<endl;
    }
    return 0;
}