19.CF803G Periodic RMQ Problem 线段树+分块+线段树标记

19.CF803G Periodic RMQ Problem 线段树+分块+线段树标记

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定序列 B B B和整数 K K K，要求对[ B B B复制 K K K次的序列]支持区间赋值、区间最小值操作。

我们发现初始序列复制 K K K次，于是想到初始就具有高度的重复性，可以用分块维护，但是发现普通分块难以支持区间赋值等操作。于是我们想到对每个块内分别建立一颗线段树，然后用再用一棵线段树维护各个块的信息。

洛谷传送门：CF803G Periodic RMQ Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：G. Periodic RMQ Problem (codeforces.com)

题目分析

给定序列 B B B和整数 K K K，要求对[ B B B复制 K K K次的序列]支持区间赋值、区间最小值操作。

我们发现初始序列复制 K K K次，于是想到初始就具有高度的重复性，可以用分块维护，但是发现普通分块难以支持区间赋值等操作。于是我们想到对每个块内分别建立一颗线段树，然后用再用一棵线段树维护各个块的信息。

那么我们直接维护一颗大树，表示每个循环节的最小值。

对每个重复区间维护一颗线段树，初始将 2 − k 2-k 2−k的树连接到第一棵树的儿子上(类似可持久化的操作)。

我们可以根据输入首先计算更新的块号和块内编号：

• 块号：
  • b l o c k l = ⌊ l n ⌋ + [ l m o d    n = = n ] block_l = \lfloor\frac{l}{n} \rfloor + [l \mod n == n] blockl​=⌊nl​⌋+[lmodn==n]
  • b l o c k r = ⌊ r n ⌋ + [ r m o d    n = = n ] block_r = \lfloor\frac{r}{n} \rfloor + [r \mod n == n] blockr​=⌊nr​⌋+[rmodn==n]
• 块内编号：
  • q u e r y l = l − ( b l o c k l − 1 ) × n ; query_l = l - (block_l - 1) \times n; queryl​=l−(blockl​−1)×n;
  • q u e r y r = r − ( b l o c k r − 1 ) × n ; query_r = r - (block_r - 1) \times n; queryr​=r−(blockr​−1)×n;

我们考虑更新的两种情况：

即为查询完全位于某一段内、查询跨过若干个段的两种情况：

1. 对于更新完全位于某个段内的情况：

   1

   此时显然 b l o c k l = b l o c k r block_l = block_r blockl​=blockr​，我们直接找到 b l o c k l block_l blockl​所在的线段树，然后执行区间修改(修改的方式在后面讲)。

   更新完块内的线段树，我们需要单点更新管辖所有块的那课线段树，即对当前块对应的叶节点更新当前块内最小值：

   先对块内线段树查询全局最小值，再在全局线段树上单点更新即可。

2. 对于更新跨区间的情况：

   2

   我们分别找到左侧不完整修改所在的块，对块内线段树的 [ q u e r y l , n ] [query_l, n] [queryl​,n]执行区间更新；再找到右侧不完整修改所在的块，对块内线段树的 [ 1 , q u e r y r ] [1, query_r] [1,queryr​]执行区间更新。然后同样类似 1 1 1，分别在两个块查询最小值，并在管辖所有块的全局线段树上分别对这两个块对应的叶节点做单点更新，更新块内的最小值。

   然后问题来到了中间部分的完整块。我们真的要将这些线段树全部覆盖掉吗？

   我们不妨回想 L a z y Lazy Lazy标记是干啥的：将更新阻滞在某一节点，当不需要该节点管辖区间内的信息时就不下放标记，而是直接返回这个节点的值。我们发现，我们所设的管辖所有块的线段树的叶节点非常符合这个特性：

如上图所示，上面的线段树是管辖所有块的，叶节点对应一个块。然后下面有一堆线段树。

如果我们修改 [ 1 , 3 ] [1,3] [1,3]区间(也就是跨区见的情况的图示情况)。我们修改 r o o t [ 1 ] , r o o t [ 3 ] root[1], root[3] root[1],root[3]的线段树后，发现中间的完成块也要覆盖掉。但是这是非常耗时的，我们不妨在管辖所有块的线段树的叶节点上打一个标记，表示叶节点所对应的块是否被区间覆盖。并直接更新掉这个叶节点的最小值值。

当下次更新，如果还是覆盖这个块的话，我们就直接更新叶节点…直到某次更新需要用到这个块内的信息(也就是在这个块上进行不完整覆盖的更新)，我们才将这个标记下放给块内的线段树，让块内的线段树去执行全覆盖操作( n l o g n nlogn nlogn覆盖)

那么块内的线段树如何更新呢？我们一开始是为了节省空间，而将所有根节点全部搞到了一棵线段树上。但是我们更新时不能影响第一个线段树，这样会发生信息重叠。

针对这个问题，我们可以记录第一个块内的编号最大值，然后从要更新的根结点出发，每次遇到要更新的点位于第一棵线段树内，就动态开新点，否则就继续用第一颗线段树上的点，这个过程非常类似可持久化的节省空间的思想。

对于查询操作，实际上与更新非常相似，同样按照上面的两种情况进行讨论，然后检查是否需要跨树下放标记，并查询即可。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10, MOD = 1e9 + 7;

namespace ffastIO {
	const int bufl = 1