2020工大杯题解-G

个人题解，和比赛官方无关，仅供参考

2020工大杯题解-G - L同学的睡眠

题目描述

L同学日理万机，睡眠非常不规律，最早下午7点就会睡觉，最晚早上7点才去睡觉。但规律的睡眠才会使L同学精力充沛，善良的你快关心一下L同学吧！

输入

第一行为空格分隔的3个整数$N,D,T$。在接下来的$N$天里，细心的你将记录L同学每天的睡眠时间，从第2天开始，如果在你所记录的过去$D$天内(包括当天)L同学最早和最晚睡眠时间差超过了$T$分钟，那么善良的你需要对L同学说句“辛苦了！”。

第二行为空格分隔的$N$个时间，依次表示$1\sim
N$天你所记录L同学的睡眠时间，采用HH:MM格式的24小时制表示。

$2\le N\le {10}^5,2\le D\le {10}^5,1\le T\le 719$

输出

输出一个整数表示你一共需要对L同学说多少次“辛苦了！”

样例输入

5 3 30
23:30 1:20 1:07 0:50 19:00

样例输出

3

题解

题目重述

$2\le N\le {10}^5,2\le D\le {10}^5,1\le T\le 719$

暴力查询的时间复杂度为$O(D\times N)$，肯定是不行的。因此，需要一种区间最值查询的数据结构。因此，这是一个RMQ问题。

RMQ是英文Range Maximum/Minimum Query的缩写，表示区间最大（最小）值。

可以使用线段树、ST表、单调栈解决问题。由于线段树和单调栈太简单了，没意思，这里介绍ST表。

ST表是用于解决 可重复贡献问题 的数据结构。

可重复贡献问题 是指对于运算 ，满足 ，则对应的区间询问就是一个可重复贡献问题。例如，最大值有 ，gcd有 ，所以RMQ和区间GCD就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这是我们所不愿意看到的。另外， 还必须满足结合律才能使用ST表求解。

ST表基于 倍增 思想，可以做到$\mathrm{\Theta }(n\log n)$预处理， $\mathrm{\Theta }(1)$回答每个询问。但是不支持修改操作。

基于倍增思想，我们考虑如何求出区间最大值。可以发现，如果按照一般的倍增流程，每次跳$2^i$步的话，询问时的复杂度仍旧是$\mathrm{\Theta }(\log n)$ ，并没有比线段树更优，反而预处理一步还比线段树慢。

我们发现$max(x,x)=x$ ，也就是说，区间最大值是一个具有“可重复贡献”性质的问题。即使用来求解的预处理区间有重叠部分，只要这些区间的并是所求的区间，最终计算出的答案就是正确的。

如果手动模拟一下，可以发现我们能使用至多两个预处理过的区间来覆盖询问区间，也就是说询问时的时间复杂度可以被降至$\mathrm{\Theta }(1)$ ，在处理有大量询问的题目时十分有效。

具体实现如下：

令$f(i,j)$表示区间$[i,i+2^j-1]$的最大值。

显然$f(i,0)=a_i$ 。

根据定义式，第二维就相当于倍增的时候“跳了$2^j-1$步”，依据倍增的思路，写出状态转移方程： $f(i,j)=max(f(i,j-1),f(i+2^{j-1},j-1))$ 。

以上就是预处理部分。而对于查询，可以简单实现如下：

对于每个询问$[l,r]$ ，我们把它分成两部分： $f[l,l+2^s-1]$与$f[r-2^s+1,r]$ 。

其中$s=\lfloor {\log }_2(r-l+1)\rfloor$ 。

根据上面对于“可重复贡献问题”的论证，由于最大值是“可重复贡献问题”，重叠并不会对区间最大值产生影响。又因为这两个区间完全覆盖了$[l,r]$ ，可以保证答案的正确性。

以上内容以 CC BY-SA 4.0 协议和 SATA 协议提供在 OI-WIKI。

贡献者：orzAtalod, Henry-ZHR, leoleoasd, Chrogeek, H-J-Granger, ouuan

题目解法

#include <iostream>
using namespace std;
const int logn = 17;
const int maxn = 100050;
int fmax[maxn][logn+1], fmin[maxn][logn+1], Logn[maxn];
void pre() {
    Logn[1] = 0;
    Logn[2] = 1;
    for (int i = 3; i < maxn; i++) {
        Logn[i] = Logn[i / 2] + 1;
    }
}
int querymax(int x,int y){
    return max(fmax[x][Logn[y - x + 1]], fmax[y - (1 << Logn[y - x + 1]) + 1][Logn[y - x + 1]]);
}
int querymin(int x,int y){
    return min(fmin[x][Logn[y - x + 1]], fmin[y - (1 << Logn[y - x + 1]) + 1][Logn[y - x + 1]]);
}
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,d,t;
    int a,b;
    int output = 0;
    char _;
    cin>>n>>d>>t;
    for (int i = 1; i <= n; i++){
        cin>>a>>_>>b;
        fmax[i][0] = (a + 5) % 24 * 60 + b;
        fmin[i][0] = (a + 5) % 24 * 60 + b;
    }
    pre();
    for (int j = 1; j <= logn; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++){
            fmax[i][j] = max(fmax[i][j - 1], fmax[i + (1 << (j - 1))][j - 1]);
            fmin[i][j] = min(fmin[i][j - 1], fmin[i + (1 << (j - 1))][j - 1]);
        }

    for (int i = 1; i <= n; ++ i){
        int mm = querymax( max(i - d + 1, 1), i);
        int mi = querymin( max(i - d + 1, 1), i);
        if (mm - mi  > t){
            output++;
        }
    }
    cout<<output<<endl;
    return 0;
}