题解：连续居住时间窗口的滑动检查

---

问题分析

本题要求找到一个最早的申请日期，使得在该日期之前的连续 $y$ 个年份（每个年份为365天周期）内，每一年在该国的居住天数都至少为 $d$ 天。

关键约束：

• 给出 $n$ 个出国时间段（包含首尾日期）
• 假设一年固定为365天（不考虑闰年）
• 需要找到最早满足条件的申请日期，且该日期必须在所有出国时间段之后

---

核心思路

1. 日期转换为天数

为了便于计算，将日期转换为从某个基准日开始的天数索引。代码中使用的方法：

• 年份加上20年偏移（避免负年份）
• 每月天数按题目给定
• 总天数 = 年份×365 + 之前月份天数之和 + 日期-1

2. 出国标记处理

使用差分数组 v[] 标记出国时间段：

• 出国开始日：v[day]++
• 出国结束日次日：v[day+1]-- 然后通过前缀和得到每天是否在国外的布尔值。

3. 国内居住天数统计

再次前缀和，使得 v[i] 表示从第0天到第i天在国内的总天数。这样，任意区间 $[l, r]$ 在国内的天数 = v[r] - v[l-1]。

4. 申请日期检查

对于候选申请日期 $T$，需要检查： 对于 $j = 0, 1, ..., y-1$：

• 第 $j$ 个年份区间：$[T - 365(j+1), T - 365j - 1]$
• 每个区间在国内的天数 ≥ $d$

如果某个区间不满足，则 $T$ 不可行。

---

算法框架

第一步：输入处理与转换

1. 读取 $n, y, d$
2. 对于每个出国时间段 $[L_i, R_i]$：
   • 将 $L_i$ 转换为天数 $l_i$，v[l_i]++
   • 将 $R_i$ 转换为天数 $r_i$，v[r_i+1]--

第二步：计算前缀和

1. 第一次前缀和：v[i] += v[i-1] → 得到每天是否出国（>0表示出国）
2. 转换为布尔值：v[i] = (v[i]==0) → 1表示在国内，0表示在国外
3. 第二次前缀和：v[i] += v[i-1] → 得到到第i天为止在国内的总天数

第三步：寻找最早申请日期

关键观察：申请日期 $T$ 的年份部分（模365）只有365种可能。

算法：

1. 对于每个余数 $i$（$0 \le i < 365$）：

   • 找到大于最后出国日的最小日期 $T$，使得 $T \mod 365 = i$
   • 检查以 $T$ 为申请日时，前 $y$ 个年份区间是否都满足条件
   • 如果不满足，根据最早不满足的区间调整 $T$

2. 调整策略：

   • 设第 $j$ 个区间 $[L_j, R_j]$ 不满足条件
   • 则 $T$ 必须至少推迟到 $L_j + 365 \times (y+1)$ 之后
   • 这样可以跳过当前不满足的窗口

3. 在所有候选 $T$ 中取最小值

---

关键实现细节

日期转换

• 年份加20偏移：确保年份为正，便于处理
• 每月天数固定数组：days[] = {31,28,31,30,31,30,31,31,30,31,30,31}
• 转换函数 getday() 和逆转换 getst()

区间检查优化

• 使用前缀和可以在 $O(1)$ 时间内计算任意区间的国内天数
• 检查 $y$ 个区间总复杂度 $O(y)$
• 总检查次数：最多 $365 \times O(y)$

边界处理

• 申请日期必须大于最后出国日 lim
• 区间左端点 $L_j$ 必须为正数（第0天开始）
• 当 $L_j \le 0$ 时，说明数据不足 $y$ 年，直接跳过

---

复杂度分析

• 时间复杂度：$O(D + 365 \cdot y)$

  • 日期转换和前缀和：$O(D)$，其中 $D$ 是时间范围（约5000年×365≈1.8M）
  • 候选日期检查：$O(365 \cdot y)$
  • 对于 $y \le 1000$，总操作约 $3.6 \times 10^5$，完全可行

• 空间复杂度：$O(D)$，约 $2 \times 10^6$ 的数组

---

正确性证明

1. 差分数组正确性

差分标记确保出国时间段被正确记录，经过两次前缀和后，v[i] 正确表示到第i天的国内总天数。

2. 检查策略正确性

对于候选日期 $T$，如果第 $j$ 个区间不满足，那么任何小于 $L_j + 365 \times (y+1)$ 的日期 $T'$ 都会包含这个不满足区间（可能平移）。因此必须跳到该日期之后。

3. 完备性

枚举所有365种余数确保了不会错过任何可能的申请日期，因为条件只依赖于日期的模365余数（由于检查的是365天的整周期）。

---

总结

本题是一道时间区间处理与前缀和优化的题目，主要考察：

1. 日期处理能力：将复杂日期计算转化为整数运算
2. 差分技巧：高效标记区间覆盖
3. 前缀和应用：快速查询区间和
4. 周期性分析：利用365天周期的性质减少枚举量

算法的核心技巧：

• 将日期转换为连续整数，简化计算
• 使用差分+前缀和高效处理区间覆盖查询
• 利用周期性只枚举365种余数，而非所有可能日期

这种"日期整数化+前缀和+周期性枚举"的方法在处理时间区间问题时非常有效，是解决此类问题的经典范式。