Znzryb's Blog
0%

Posted on Edited on

题目大意

题目描述
给定一棵包含 nn 个节点的无根树。

Cyndaquil 起初位于一个非叶子节点 vv。在每一个回合中，他可以选择停留在当前节点，或者移动到相邻的一个节点。他的目标是到达树的任意一个叶子节点（度数为 11 的节点）。

Snorlax 试图阻止他到达叶子节点。Snorlax 可以选择在一条边上睡觉，此时 Cyndaquil 将无法通过这条边。同一时刻最多只有一条边会被阻塞（即只有最新选择的边会被阻塞）。

Snorlax 移动有冷却时间。初始时冷却时间为 00。当冷却时间 ≤0\le 0 时，Snorlax 可以选择一条新的边进行阻塞（他也可以选择暂不行动）。一旦他移动并选择了一条新边，冷却时间就会重置为 kk。

在 Cyndaquil 的每个回合之后（即使他选择停留），Snorlax 的冷却时间都会减少 11。

两人轮流行动，Snorlax 先手，且初始时没有任何边被阻塞。假设双方都采取最优策略，判断 Cyndaquil 是否一定能在有限的回合内到达某个叶子节点。

输入格式
第一行包含一个整数 tt (1≤t≤1041 \le t \le 10^4)，表示测试用例的数量。

每个测试用例的第一行包含三个整数 nn、kk 和 vv (3≤n≤5⋅1053 \le n \le 5 \cdot 10^5，1≤k,v≤n1 \le k, v \le n)，分别表示树的节点数、Snorlax 的冷却时间以及 Cyndaquil 的初始起点。

接下来 n−1n-1 行，每行包含两个整数 aa 和 bb (1≤a,b≤n1 \le a, b \le n，a≠ba \neq b)，表示树上连接节点 aa 和 bb 的一条边。

保证给定的图是一棵树，且起点 vv 不是叶子节点。所有测试用例的 nn 之和不超过 5⋅1055 \cdot 10^5。

输出格式
对于每个测试用例，输出一行 “YES” 或 “NO”（大小写不敏感），表示 Cyndaquil 是否一定能在有限回合内到达叶子节点。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
6
6 2 1
1 2
2 3
2 4
1 5
5 6
7 1 4
1 2
2 3
3 4
4 5
5 6
6 7
3 1 3
1 3
2 3
4 1 4
1 3
3 4
4 2
9 3 5
4 5
5 6
4 7
9 8
8 7
1 2
2 3
3 4
9 4 5
4 5
5 6
4 7
9 8
8 7
1 2
2 3
3 4

样例输出

1
2
3
4
5
6
YES
NO
YES
NO
NO
YES

样例解释
在第一个测试用例中：Cyndaquil 从节点 11 出发。如果 Snorlax 选择阻塞节点 11 到节点 22 的边，那么 Cyndaquil 可以在两个回合后走到叶子节点 66。否则，Cyndaquil 可以直接移动到节点 22，此时 Snorlax 无法同时阻止他前往叶子节点 33 或 44，Cyndaquil 必然能到达其中一个。

在第二个测试用例中：由于冷却时间 k=1k=1 极短，Snorlax 可以频繁移动，可以证明 Snorlax 能够无限期地阻止 Cyndaquil 到达树两端的叶子节点 11 或 77。

image

不难发现样例 2，移动者会被困在 3,4 之间，因为阻塞者冷却时间太快了，只有 1。

image

样例 5 到达不了叶子节点

暴力程序书写指导

暴力程序 bfs 的书写**，最重要的还是和做题的一样的，用什么代表一个状态。**

为什么要书写暴力 bfs 程序？因为以我的这个经验，这种图论题目，你想一遍写对，基本不可能，以类似题目 F 为例：

2025-沈阳站-区域赛-F. The Bond Beyond Time（友谊天长地久）（如何使用 bfs 找一个无弦环）（这种题目，我感觉啊，想要做出来的话，要么就是你的思路得比较好，要么就是还是得写个对拍）

这道题目有一个地方还是很难想到的，需要写一个对拍。

在写一个暴力程序之前（当然，特别暴力的除外啊，特别暴力的就不用想了，但是不是所有的题目都可以非常轻松的找到一个特别暴力的写法，特别是这种博弈题目），一定要想清楚这个状态转移图像。

我们不难得到这样的图像：

image

然后，我们来想如何具体实现，这种样子，我们非常容易想到这个记忆化 dfs。但是，有环的话，不能够使用记忆化 dfs，毕竟记忆化 dfs 就是 dp，只能够在 DAG 上使用。

于是我们想到记忆化 bfs。但是一次正向的记忆化 bfs 很难实现类似的这种可以计算前驱后驱的这个复杂运算。

但是一次不行，就跑两次呗。我们可以跑一次正向 bfs，记住这个出去的红色节点数量（即红色出度）和出去的这个蓝色节点数量（即蓝色出度）。（你也可以理解这次 bfs 就是在把这张反图建出来，毕竟不把图建出来，很难进行这个反向 bfs）然后再跑一次这个反向 bfs，从所有合法点一路往上推，通过减去红色计数器和蓝色计数器，实现类似于或的效果，把红色计数器和蓝色计数器并起来，实现红蓝 and 的效果。

当然我们也不知道对不对，试一试吧。

试过了，上面👆这种做法很难写对，也不是错吧，很难写对。我们不妨啊，一轮，拆成两个操作来看，这样可以避免红蓝之间转移的尴尬问题。

image

一定要把这个状态转移图设计为红蓝互不相交的情况，至少要把逃跑者选择和阻塞者选择分开。

好的暴力果然是非常优美啊，一次写对。

采用了朴素的，不动点式的更新方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool changed=true;
while (changed) {
    changed=false;
    for (const auto &[u,vec]:complex_g) {
        if (win[u]) continue;
        if (u.turn) {
            bool all_win=true;
            for (auto son:vec) {
                if (!win[son]) {
                    all_win=false;
                    break;
                }
            }
            win[u]=all_win;
            if (all_win) {
                changed=true;
            }
        }else {
            for (auto son:vec) {
                if (win[son]) {
                    win[u]=true;
                    changed=true;
                    break;
                }
            }
        }
    }
}

思路讲解

S 只要符合这个要求，就是 Yes，否则就是 No。

image

其实像上面👆这么想，有一个非常阴的地方，就是，阻塞者是动态的，且可以不操作的，阻塞者可能不急于操作，而是看你怎么操作以后，他再出手，逼你从优势位置移动出来。这么讲很抽象是吧？我们直接拿对拍出来的样例来说。

1
2
3
4
5
6
7
8
9
1
7 2 1
1 2
1 3
2 4
1 5
5 6
3 7

这个样例应该输出 no，原因和上面说的一样。阻塞者可能不急于操作，而是看你怎么操作以后，他再出手，逼你从优势位置移动出来。

image

所以说要怎么解决这个问题呢？还是挺难的。

像这种博弈题目，一定要想到的就是两者的最优策略是什么？一定要想两者的最优策略是什么。

Snorlax 试图阻止 Cyndaquil 到达叶子节点，他的最优策略是在 Cyndaquil 即将到达叶子节点（或必胜节点）前的最后一步进行封锁。我们其实已经通过对拍呀，通过什么方式找到了这个比较特殊的这个例子。但是我们没有总结出来，就是阻塞者他的这个策略是什么，就这种博弈题目一定要去想他们的最优策略是什么。

因此，其实我们就是看这个拉扯距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
auto dfs=[&](auto && go,ll u,ll fa) -> void {
    if (SZ(g[u])==1) {
        return;
    }
    vector<ll> rec;
    ll lans=INF;
    for (auto to:g[u]) {
        if (to==fa) {
            continue;
        }
        go(go,to,u);
        rec.push_back(dp[to]);
        lans=min(dp[to]+1,lans);
    }
    sort(all(rec));
    if (SZ(rec)>=2) {
      // rec[0]+rec[1]+2 是拉扯距离总长度
      // -1 是因为这个在最后一刻他卡你一下，你需要跑的距离就是总拉扯距离 -1
        if (rec[0]+rec[1]+2-1<=K) {
            lans=0;
        }
    }
    dp[u]=lans;
};
dfs(dfs,S,-1);
if (dp[S]==0) {
    cout<<"YES\n";
    return;
}
cout<<"NO\n";

AC代码

AC
https://codeforces.com/contest/2207/submission/366188285

心路历程（WA，TLE，MLE……）

Posted on

题目大意

题目描述

一共有 mm 个玩偶，初始危险值 d1,d2,…,dmd_1, d_2, \dots, d_m 均为 0。

整个过程持续 ℓ\ell 秒。在每一秒内，会有一个（且仅有一个）玩偶的危险值增加 1。你可以时刻观察到所有玩偶当前的危险值。

你有 nn 次使用手电筒的机会，分别在固定的时间点 a1,a2,…,ana_1, a_2, \dots, a_n（1≤a1<a2<⋯<an≤ℓ1 \le a_1 < a_2 < \dots < a_n \le \ell）秒后发生。
每次使用手电筒时，你可以选择恰好一个玩偶，将其危险值重置为 0。每次的选择是互相独立的。

最终的“总危险值”定义为 ℓ\ell 秒结束时，所有玩偶危险值的最大值，即 max⁡1≤j≤mdj\max_{1 \le j \le m} d_j。
你需要求出一个最小的整数 xx，使得无论每一秒是哪个玩偶的危险值增加，你都能通过合理地使用手电筒，保证最终的总危险值不超过 xx。

输入格式

第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试用例的数量。

每个测试用例的第一行包含三个整数 n,m,ℓn, m, \ell（1≤n,m,ℓ≤2⋅1051 \le n, m, \ell \le 2 \cdot 10^5，n≤ℓn \le \ell，1≤m⋅ℓ≤2⋅1051 \le m \cdot \ell \le 2 \cdot 10^5），分别代表手电筒使用次数、玩偶数量以及总时长。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n（1≤a1<a2<⋯<an≤ℓ1 \le a_1 < a_2 < \dots < a_n \le \ell），代表可以使用手电筒的时间点。

保证所有测试用例中 m⋅ℓm \cdot \ell 的总和不超过 2⋅1052 \cdot 10^5。

输出格式

对于每个测试用例，输出一个整数，即保证最终总危险值不超过的最小值 xx。

样例数据

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
7
1 2 10
10
5 1 32
1 4 9 16 25
2 3 40
13 37
2 2 7
6 7
8 5 60
3 17 20 28 36 44 45 50
6 7 1987
6 7 66 77 666 777
1 1 1
1

输出

1
2
3
4
5
6
7
5
7
19
1
19
1477
0

样例解释

在第一个测试用例中，有 22 个玩偶，总时长为 1010 秒，在第 1010 秒后可使用一次手电筒。可以证明 x=5x=5 总是可行的：1010 秒后，必定有一个玩偶的危险值至少为 55，另一个至多为 55。我们对着危险值较大的那个使用手电筒将其清零，那么最终的最大危险值至多为 55。可以证明 55 是 xx 的最小可能值。

在第二个测试用例中，只有 11 个玩偶，总时长为 3232 秒。由于只有 11 个玩偶，它的危险值每秒必定增加 11。在最后一次使用手电筒（第 2525 秒）时，我们将它的危险值清零。在这之后距离结束还有 77 秒，因此最终危险值必定为 77。

在第三个测试用例中，可以证明最小可能的值 xx 为 1919。

思路讲解

就是这个 B，哎，感觉基本上是想到了，但是没关注到一个关键的这个数据范围限制。

一定要关注数据范围限制。

image

你看到这个，基本就知道简单的贪心和这个二分答案是解决不了的。

其实这道题目，这个思路还是不难的，就是，我们想让我们的每一次操作都在最终的答案中贡献最大，是不是？

然后我们发现，如果说后面还有 N 个手电筒，我们如果给 N 个球加，我们其实对这个最终答案的贡献是 0。

image

那怎么办？我们可以给 N+1 个球加。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ll cnt=N;
while (SZ(st)>cnt+1) {
    pop();
}
for (int i=1;i<=L;++i) {
    add();
    if (incident[i]) {
        to_zero();
        --cnt;
    }
    while (SZ(st)>cnt+1) {
        pop();
    }
}
ll ans=*st.rbegin();

AC代码

AC

https://codeforces.com/contest/2207/submission/365942294

心路历程（WA，TLE，MLE……）

Posted on

基本情况

https://codeforces.com/contest/2207

image

两道题目，排 2705 还可以，还不赖，感觉。

当然还是有进步的这个空间的。

心得感悟

就是这个 B，哎，感觉基本上是想到了，但是没关注到一个关键的这个数据范围限制。

一定要关注数据范围限制。

image

你看到这个，基本就知道简单的贪心和这个二分答案是解决不了的。

题目 A. 1-1

题目描述
给定一个长度为 nn 的 01 字符串 ss。
在一次操作中，如果存在某个位置 ii（2≤i≤n−12 \le i \le n-1）满足其左右相邻的字符均为 1（即 si−1=si+1=1s_{i-1} = s_{i+1} = 1），则可以随意将 sis_i 修改为 0 或 1。
该操作可以执行任意次（包括零次）。你需要求出经过操作后，最终字符串中 1 的数量的最小值和最大值。

输入格式
第一行包含一个整数 tt（1≤t≤5001 \le t \le 500），表示测试数据的组数。
每组数据包含两行：
第一行为一个整数 nn（3≤n≤1003 \le n \le 100），表示字符串的长度。
第二行为一个长度为 nn 的 01 字符串 ss。

输出格式
对于每组数据，输出两个整数，分别表示最终字符串中包含 1 的数量的最小值和最大值。

样例输入

1
2
3
4
5
6
7
8
9
4
3
111
6
011011
7
1011101
9
100101101

样例输出

1
2
3
4
2 3
3 5
4 7
5 7

样例解释
在第一组样例中：

  • 最小数量为 22。操作过程：111 →\rightarrow 101。

  • 最大数量为 33。不进行任何操作即可。

在第二组样例中：

  • 最小数量为 33。操作过程：011011 →\rightarrow 011111 →\rightarrow 010111 →\rightarrow 010101。

  • 最大数量为 55。操作过程：011011 →\rightarrow 011111。

https://codeforces.com/contest/2207/problem/A

就是贪心，不难发现，就是能操作的就操作（变为 1），那么得到就是最多的答案。

接着在能操作的就操作（变为 1），变好的这个串的前提下，然后能操作的就操作（变为 0），得到的就是最少的答案。

想到这样的方法，一个是 leetcode 好像做过类似思想的题目（和父亲讨论过，没做），还有就是我发现这个进行这个 1 操作后，继续进行 0 操作，得到的答案总归不是不优的，至少是比直接进行 0 操作一样，或者更好。

https://codeforces.com/contest/2207/submission/365935923

题目 C. Where’s My Water?

题目描述
给定一个高度为 hh、列数为 nn 的网格。在第 ii 列中，最底部的 aia_i 个格子是泥土，其上方的格子全是水。
你可以在任意一个水格子上放置排水口，最多可以放置两个。
每个排水口可以排走所有能够通过仅向下、向左或向右移动（且不穿过任何泥土格子）到达该排水口的水格子。被两个排水口共同覆盖的水格子只会被计算一次。
求在最多放置两个排水口的情况下，能够排走的最大水格子总数。

image

输入格式
第一行包含一个整数 tt（1≤t≤1031 \le t \le 10^3），表示测试数据组数。
每组数据第一行包含两个整数 nn 和 hh（1≤n≤20001 \le n \le 2000，1≤h≤1091 \le h \le 10^9），分别表示网格的列数和高度。
第二行包含 nn 个整数 aia_i（1≤ai≤h1 \le a_i \le h），表示第 ii 列泥土格子的高度。
保证所有测试数据中 nn 的和不超过 20002000。

输出格式
对于每组数据，输出一个单行整数，表示最多能排走的水格子数量。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Input
6
7 4
1 3 1 2 3 1 1
8 10
7 5 1 3 2 5 6 8
1 1
1
10 20
5 2 1 2 1 3 6 7 1 1
5 1000000000
1 420420420 1 420420420 1
1 1000000000
1

Output
14
43
0
170
3738738738
999999999

样例解释
在第一组样例中，网格列数为 77，高度为 44。通过在合适的位置放置两个排水口，最多可以排走 1414 个水格子。
在第二组样例中，网格列数为 88，高度为 1010。通过合理放置两个排水口，可以排走网格中全部的 4343 个水格子。
在第三组样例中，网格大小为 1×11 \times 1，且唯一的格子是泥土，没有水格子，无法放置排水口，因此输出 00。

https://codeforces.com/contest/2207/problem/C

不难发现，这道题目，应该是直接枚举两个的这个抽水的位置，然后 O(1)O(1) 计算其所抽的水。

当然，为了实现这个常数级别的计算，前面需要进行一个 O(n2)O(n^2) 的预处理。

不难发现，就是抽水棒两边的这个计算（也就是图中绿色部分的计算）是非常容易的。但是中间蓝色问号部分的计算，是这道题目的难点。

image

如果说随意的，错误的进行计算，那么 9 格子就被漏掉了。

image

通过模拟，我们发现，如果两点之间是一个这个山，那么应该以山峰为界，互不干扰。

image

那么山峰是什么东西？就是最大值嘛，这两点之间的最大值的这个坐标就是山峰所在位置。

1
2
3
4
5
6
7
8
9
10
for (int i=1;i<=N;++i) {
    for (int j=i;j<=N;++j) {
        ll lans=0;
        // 最大值位置
        ll pos=dp[i][j];
        lans=pre_area[i][1]+suf_area[i][pos]+pre_area[j][pos]+suf_area[j][N];
        lans-=M-H[i]+M-H[pos]+M-H[j];
        ans=max(ans,lans);
    }
}

https://codeforces.com/contest/2207/submission/365935937

Posted on

题目大意

题目大意

有一张地图，可以通过若干次贯穿整张纸的水平方向和垂直方向的折叠，最终被折叠成一个 1×11 \times 1 的正方形单位。每次折叠都发生在距离纸张边缘为整数个单位的位置。

当把这张地图重新完全展开时，所有的折痕会把纸张划分成一个 r×cr \times c 的正方形网格。任意两个相邻正方形之间共享的边即为一条长度为 11 的折痕。根据折叠方向的不同，折痕可以分为两种：

  • 峰折（Mountain fold）：向观察者方向折叠而成的凸起折痕。

  • 谷折（Valley fold）：背离观察者方向折叠而成的凹陷折痕。

题目给定一个 (2r−1)×(2c−1)(2r - 1) \times (2c - 1) 的字符矩阵，用来编码展开后的地图折痕状态。矩阵中第 ii 行第 jj 列的字符含义如下：

  • 当 ii 和 jj 均为奇数时，字符为 .，表示一个 1×11 \times 1 的正方形。

  • 当 ii 和 jj 均为偶数时，字符为 +，表示四个正方形相交的角。

  • 其他情况下，字符表示两个相邻正方形之间的折痕：M 表示峰折，V 表示谷折。

任务：给定上述字符矩阵，判断是否能通过上述合法的折叠过程（每次水平或垂直折叠贯穿当前的整张纸，直到折成 1×11 \times 1 大小），在现实中精准复现该矩阵所描述的折痕图案。如果可以，输出 YES，否则输出 NO。

样例及解释

样例输入

1
2
3
4
5
6
7
8
9
10
11
2
3 4
.V.V.M.
M+M+M+M
.M.M.V.
V+M+V+M
.M.M.V.
2 2
.M.
M+M
.M.

样例输出

1
2
YES
NO

样例解释
输入包含两个测试用例：

  • 第一个测试用例给出了一个 (2×3−1)×(2×4−1)(2 \times 3 - 1) \times (2 \times 4 - 1) 即 5×75 \times 7 的字符矩阵，代表一个 3×43 \times 4 的网格。该图案是可以通过规定的折叠方法真实得到的折痕分布，因此输出 YES。

  • 第二个测试用例给出了一个 3×33 \times 3 的字符矩阵，代表一个 2×22 \times 2 的网格。其四周的折痕全为 M（峰折），而在这种必须贯穿整张纸面进行折叠的规则下，无法在现实中构造出这样的折痕组合，因此输出 NO。

image

给你一个这样的矩阵，问可不可能折纸做到？

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

Posted on

题目大意

P13825 【模板】线段树 1.5

题目描述

如题，已知一个长度为 nn

的数列 {ai}\{a_i\}（1≤i≤n1 \leq i \leq n），初始时 aa 序列满足 ai=ia_i = i。你需要进行下面两种操作：

  1. 将某区间每一个数加上 kk。

  2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 n,mn, m，分别表示该数列数字的个数和操作的总个数。

接下来 mm 行每行包含 33 或 44 个整数，表示一个操作，具体如下：

  1. 1 l r k：将区间 [l,r][l,r] 内每个数加上 kk。

  2. 2 l r：输出区间 [l,r][l,r] 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
5 5
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

输出 #1

1
2
3
9
9
18

说明/提示

对于 30%30\% 的数据，n≤8n \le 8，m≤10m \le 10。

对于 50%50\% 的数据，n≤105n \le {10}^5。

对于 100%100\% 的数据，1≤m,k≤1051 \le m,k \le {10}^5，1≤l≤r≤n≤1091 \leq l \leq r \leq n\leq 10^9。

思路讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

/* 
 * 2026-03-08  P13825 【模板】线段树 1.5 动态开点线段树
 * AC https://www.luogu.com.cn/record/266006147
 *
 */
struct Tag {
    // 在母串中的这个位置
    ll add=0;
    bool need_apply=false;
    void apply(const Tag &t) {
        add+=t.add;
        need_apply=true;
    }
};

struct Info {
    ll l=0,r=0;
    i128 sum=0;
    static Info merge(const Info &a,const Info &b) {
        Info res=a;
        res.r=b.r;
        res.sum+=b.sum;
        return res;
    }
    void apply(const Tag&t) {
        if (!t.need_apply) {
            return;
        }
        ll len=r-l+1;
        sum+=len*t.add;
    }
};

// 我认为还是用 C++14 的写法，把你要写的东西传进去比较好，不容易写错
template<class I=Info,class T=Tag>
struct SEG {
    // 如果不需要泛型，可以用下面的来替代
    // using I=Info;
    // using T=Tag;
    struct Node {
        I info;
        T tag;
        Node* rs=nullptr;
        Node* ls=nullptr;
    };

    void init_node(Node *u,ll l,ll r) {
        u->info.l=l;
        u->info.r=r;
        u->info.sum=i128(u->info.l+u->info.r)*(u->info.r-u->info.l+1)/2;
    }

    Node* root=nullptr;
    ll N;

    static bool isIntersect(ll l1, ll r1, ll l2, ll r2) {
        if (!(l1 > r2 || r1 < l2)) return true;
        return false;
    }

    SEG(ll N):N(N) {
        root=new Node();
        root->info.l=1;
        root->info.r=N;
        init_node(root,1,N);
    }

    void extend(Node *u) {
        if (u->ls==nullptr) {
            u->ls=new Node();
            init_node(u->ls,u->info.l,(u->info.l+u->info.r)>>1);
        }
        if (u->rs==nullptr) {
            u->rs=new Node();
            init_node(u->rs,((u->info.l+u->info.r)>>1)+1,u->info.r);
        }
    }

    void push(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        extend(u);
        if (u->tag.need_apply) {
            u->ls->info.apply(u->tag);
            u->rs->info.apply(u->tag);
            u->ls->tag.apply(u->tag);
            u->rs->tag.apply(u->tag);
            u->tag={};
        }
    }
    void pull(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        u->info=I::merge(u->ls->info,u->rs->info);
    }
    void modify(Node*u,ll l,ll r,const T& t) {
        if (u->info.l>=l && u->info.r<=r) {
            u->info.apply(t);
            u->tag.apply(t);
            return;
        }
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            modify(u->ls,l,r,t);
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            modify(u->rs,l,r,t);
        }
        pull(u);
    }

    Info query(Node *u,ll l,ll r) {
        if (u->info.l>=l && u->info.r<=r) {
            return u->info;
        }
        Info res;
        bool is_get=false;
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            res=query(u->ls,l,r);
            is_get=true;
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            if (!is_get) {
                res=query(u->rs,l,r);
            }else {
                res=I::merge(res,query(u->rs,l,r));
            }
        }
        return res;
    }
};

AC代码

AC
https://www.luogu.com.cn/record/266006147

心路历程（WA，TLE，MLE……）

不要忘记初始化这个根节点。

image