2024 YAC Round 3 题解

A. 爱丽丝的 Sweet Magic

题目描述

给定一个数组 $a$，对其中某一个元素 $+1$，使得 $\prod_{i=1}^n a_i$ 尽可能大。「YAC Round 3」爱丽丝的 Sweet Magic

解法一 暴力枚举

数据量比较小，每组数据数组大小不超过 $10$，我们可以直接暴力枚举 $+1$ 的元素 $a_i$，计算对应的累乘结果，取最大值输出。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        int n; cin >> n;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i ++ ) cin >> a[i];
        ll res = 0;
        for(int i = 1; i <= n; i ++ ){
            ll prod = a[i] + 1;
            for(int j = 1; j <= n; j ++ )
                if(i != j) prod *= a[j];
            res = max(res, prod);
        }
        cout << res << '\n';
    }

    return 0;
}

解法二 贪心

我们可以假设进行 $+1$ 的元素为 $a_k$ （$1 \le k \le n$），显然当前元素 $+1$ 对答案的贡献为 $a_1 + \ldots + a_{k-1} + a_{k + 1} + \ldots + a_n $，我们记为 $\text{sum}$，即剩余元素之和。所以我们的问题转换为选择一个元素 $a_k$ 使得 $\text{sum}$ 尽可能大，那么基于贪心的思想，我们只要选择数组 $a$ 中最小的元素作为 $a_k$，就可以使得剩余元素之和最大了。选取最小值进行 $+1$ 后，再计算数组元素累乘并输出即可。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        int n; cin >> n;
        vector<int> a(n + 1, 10);
        int mn = 0;  // 记录最小下标
        for(int i = 1; i <= n; i ++ ){
            cin >> a[i];
            if(a[i] < a[mn]) mn = i;
        }
        a[mn] ++ ;

        ll res = 1;
        for(int i = 1; i <= n; i ++ ) res *= a[i];
        cout << res << '\n';
    }

    return 0;
}

B. 迷途竹林的月色

题目描述

给定一个起点和一个终点，问网格图中是否可以从起点到达终点。（非常简单且典型的搜索模板题）「YAC Round 3」迷途竹林的月色

解法一 BFS

广度优先搜索。标准的模板题，内容较为简单，如有不熟悉该模板的可自行查找资料等进行学习。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define MP make_pair
typedef pair<int, int> pii;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const int N = 110;

int n, m, sx, sy, tx, ty;
char g[N][N];
bool vis[N][N];

bool bfs(){
    if(g[sx][sy] == '#' || g[tx][ty] == '#') return false; // 注意起点终点合法
    queue<pii> q;
    q.push(MP(sx, sy)), vis[sx][sy] = true;

    while(q.size()){
        auto [x, y] = q.front();
        q.pop();

        if(x == tx && y == ty) return true;

        for(int k = 0; k < 4; k ++ ){
            int nx = x + dx[k], ny = y + dy[k];
            if(nx < 1 || nx > n || ny < 1 || ny > m) continue; // 出界
            if(g[nx][ny] == '#' || vis[nx][ny]) continue; // 无法通行或访问过
            q.push(MP(nx, ny)), vis[nx][ny] = true;
        }
    }

    return false;
}

int main(){
    ios;

    cin >> n >> m >> sx >> sy >> tx >> ty;
    for(int i = 1; i <= n; i ++ ) cin >> (g[i] + 1);

    cout << (bfs() ? "Marisa" : "Alice") << '\n';

    return 0;
}

解法二 DFS

深度优先搜索

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define MP make_pair
typedef pair<int, int> pii;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const int N = 110;

int n, m, sx, sy, tx, ty;
char g[N][N];
bool vis[N][N];

bool dfs(int x, int y){
    if(x < 1 || x > n || y < 1 || y > m) return false; // 出界
    if(g[x][y] == '#' || vis[x][y]) return false; // 无法通行或访问过

    vis[x][y] = true;
    if(x == tx && y == ty) return true; // 到达终点

    for(int k = 0; k < 4; k ++ ){
        int nx = x + dx[k], ny = y + dy[k];
        if(dfs(nx, ny)) return true; // 搜索成功
    }

    return false; // 搜索失败
}

int main(){
    ios;

    cin >> n >> m >> sx >> sy >> tx >> ty;
    for(int i = 1; i <= n; i ++ ) cin >> (g[i] + 1);

    cout << (dfs(sx, sy) ? "Marisa" : "Alice") << '\n';

    return 0;
}

C. 某科学的炫彩呱太

题目描述

给定一个长度为 $n$ 的数组 $a$，共有 $q$ 次询问，每次询问一个区间 $[l, r]$，判断区间 $[l, r]$ 内所有元素是否互不相同。「YAC Round 3」某科学的炫彩呱太

解题思路 思维

我们可以倒过来思考这个问题，把问题转换为：判断一个区间中是否存在一个数，其 前一个 相等的数的位置是否在当前的区间中。

可以注意到，元素大小不超过 $10^5$。我们可以开一个 $\text{idx}$ 数组，用于记录每个数出现的前一个位置，即 $\text{idx}[x]$ 表示数值为 $x$ 的元素出现的前一个下标。

我们再开一个数组 $\text{mx}$，用于记录到下标 $i$ 之前所有 $\text{idx}$ 的前缀最大值（这里实际上也有点贪心的思想在里面，显然最右边的下标是最有可能改变答案的）。

对于每个询问的区间 $[l, r]$，我们只需要判断 $\text{mx}[r]$ 是否 小于 $l$，即可。如果满足 $\text{mx}[r] < l$，此时表明区间内出现的数的前一个位置都在 $l$ 之前，故区间内的数互不相同；否则，表明区间内存在至少一对相同的数。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

int main(){
    ios;

    int n, q; cin >> n >> q;
    vector<int> a(n + 1), mx(n + 1), idx(n + 1);
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
        mx[i] = max(mx[i - 1], idx[a[i]]); // 前缀最大值
        idx[a[i]] = i; // 记录下标
    }

    while(q -- ){
        int l, r; cin >> l >> r;
        cout << (mx[r] < l ? "Yes" : "No") << '\n'; 
    }

    return 0;
}

PS: 此题也可以用莫队解决，属于进阶内容，不要求掌握，感兴趣的可以去了解了解。

D. 芙莉莲的冒险

题目描述

给定一个长度为 $n$ 的数组 $a$，和一个长度为 $n$ 的数组 $t$。对于每个位置 $i$，将 $a_1, a_2, \ldots , a_i$ 中所有元素都减去 $t_i$（如果减去后小于 $0$，则减去元素本身，即减去 $\min(a_k, t_i)$，$1 \le k \le i$）。对于每个位置 $i$ ，求出减去的值之和，最后判断和的最小值和最大值之差是否小于 $k$。「YAC Round 3」芙莉莲的冒险

解题思路 模拟 + 前缀和 + 二分 + 差分

对于数组 $a$ 中的每个元素 $a_i$，根据题意只有当前位置 $i$ 及其后面的位置的 $t$ 可以使得 $a_i$ 减小直至变为 $0$（当然也有可能到最后依然不会变为 $0$）。显然，我们可以先预处理一下数组 $t$ 的 前缀和 $pre$，然后在模拟过程中用 二分 查找得到每个 $a_i$ 会变为 $0$ 的位置（二分的区间为 $[i, n]$）。

对于数组 $t$ 的每个位置 $j$，假设当前数组 $a$ 的 $[1, j]$ 区间内，有 $p$ 个元素大于等于 $t_j$，故当前位置减去元素之和 $sum_j$ 就是： $p \times t_j$ 加上 当前数组 $a$ 的 $[1, j]$ 区间内剩下 $< t_j$ 的元素之和。

我们可以反过来思考，看每个元素 $a_i$ 的对 $sum_j$ 贡献。对于每个 $t_j$，我们可以统计有多少个元素 $a_i$ 能够在 $j$ 位置依旧 $\ge t_j$。如果此时的 $a_i < t_j$，那么我们累加一下剩余部分对当前位置 $sum_j$ 的贡献。

对于统计每个元素 $a_i$ 的对 $sum_j$ 贡献，我们可以用 差分 来记录，差分数组记为 $diff$。假设二分找到 $a_i$ 会变为 $0$ 的位置为 $pos$，我们需要分情况讨论：

• 如果 $pre[pos] - pre[i - 1] < a[i]$，表明当前 $a_i$ 到最后都不会变为 $0$，故 $diff[i] ++ $，区间 $[i, n]$ 所有都 $+1$，表示 $a[i]$ 对区间 $[i, n]$ 的位置都贡献了对应的 $1$ 个 $t_j$（$i \le j \le n$）。

• 如果 $pre[pos] - pre[i - 1] = a[i]$，表明当前 $a_i$ 正好在位置 $pos$ 变为 $0$，故 $diff[i] ++ , diff[pos + 1] – $，区间 $[i, pos]$ 都 $+1$，表示 $a[i]$ 对区间 $[i, pos]$ 的位置都贡献了对应的 $1$ 个 $t_j$（$i \le j \le pos$）。

• 如果 $pre[pos] - pre[i - 1] > a[i]$，表明 $pos$ 位置当前 $a_i$ 不满 $t_{pos}$，那么我们要单独累加一下这个剩余部分。故 $diff[i] ++ , diff[pos] --$，区间 $[i, pos - 1]$ 都 $+1$，同时把剩下的 $a_i - (pre[pos - 1] - pre[i - 1])$ 累加到贡献剩余部分的一个新的数组 $lft$ 中。

处理完差分后，求一下 $diff$ 的前缀和就可以还原得到每个位置的贡献满 $t_j$ 的数量。对于每个 $sum_j$，其计算公式为 $sum_j = t_j \times diff[j] + lft[j]$（此处的 $diff$ 为求前缀和还原后的，$lft$ 为剩余部分）。

遍历所有的 $sum$，分别记录一下最小值和最大值，最后判断一下是否 小于 $k$ 即可。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 1e5 + 10;

ll pre[N];   // 吸收魔力值前缀和
ll lft[N];   // a_i 会减为 0 那个时间剩余部分的魔力 
int diff[N]; // 差分 统计每个 a_i 对 sum_j 的贡献

int main(){
    ios;

    int n, k; cin >> n >> k;
    vector<int> a(n + 1), t(n + 1);

    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 1; i <= n; i ++ ) cin >> t[i];
    for(int i = 1; i <= n; i ++ ) pre[i] = pre[i - 1] + t[i]; // t 的前缀和

    for(int i = 1; i <= n; i ++ ){
        int l = i, r = n; // [i, n] 内二分找到每个 a_i 会变为 0 的位置
        while(l < r){
            int mid = l + r >> 1;
            if(pre[mid] - pre[i - 1] >= a[i]) r = mid;
            else l = mid + 1;
        }
        if(pre[r] - pre[i - 1] < a[i]) diff[i] ++ ; // 到最后都不会变为 0
        else if(pre[r] - pre[i - 1] == a[i]) diff[i] ++ , diff[r + 1] -- ; // 正好变为 0
        else {
            diff[i] ++ , diff[r] -- ; // 在pos变为0，但是不满当前 t_pos
            lft[r] += a[i] - (pre[r - 1] - pre[i - 1]);  // 累加当前剩余部分
        }
    }

    for(int j = 1; j <= n; j ++ ) diff[j] += diff[j - 1]; // 差分求前缀和 每个 sum_j 满 t_j 的个数
    
    ll mx = 0, mn = 2e18; // 最大 最小
    for(int j = 1; j <= n; j ++ ){
        ll sum = (ll)t[j] * diff[j] + lft[j]; // 每个sum_j
        mx = max(mx, sum), mn = min(mn, sum);
    }

    ll d = mx - mn;
    cout << (d > k ? "YES" : "NO") << '\n';
    cout << d << '\n';
 
    return 0;
}

E. 星屑幻想 Stardust Reverie

题目描述

给定一颗无向树，任选三个点 $A, B, C$，求 $\max{(dist_{AB} + \min{(dist_{CA}, dist_{CB})})}$ 。星屑幻想 Stardust Reverie

解题思路 贪心 + 树的直径 + 枚举

我们不妨假设 $A$ 距离 $C$ 比 $B$ 距离 $C$ 更近，也就是 $dist_{CA} \le dist_{CB}$，那么我们最终的答案为 $dist_{CA} + dist_{AB}$。

对于路径 $dist_{CA} + dist_{AB}$，我们有以下两种情况：

• $C \rightarrow A$ 的路径和 $A \rightarrow B$ 的路径中间部分存在交点。

  假设交点为 $D$，由于是一颗树，任意两点之间的路径是唯一的，故 $C \rightarrow A$ 中的 $D \rightarrow A$ 部分与 $A \rightarrow B$ 中 $A \rightarrow D$ 的部分是完全重合的。所以当前情况下的路径只有可能如下图所示：

  

  显然，$dist_{CA}$ 具有限制，但是我们可以发现 $dist_{AB}$ 并没有任何限制，故基于贪心的思想，我们可以 让 $dist_{AB}$ 尽可能长。由于是一棵树，最长的两点之间距离，当为 树的直径，因此，我们基于贪心思想得到的 $A$ 和 $B$ 就是树的直径的两个端点。（这里暂且先不证明选取 $A$ 和 $B$ 为树的直径端点的正确性，后面有相关证明）

  所以当前情况下的答案为 $dist_{CA}$ + 树的直径

• $C \rightarrow A$ 的路径和 $A \rightarrow B$ 的路径中间部分没有交点。

  当前情况，表明路径就是 $C \rightarrow A \rightarrow B$，此时路径形成一条链。然而树中一条链最长长度也就是树的直径，此时最多只能取 $dist_{CB}$ 为树的直径。

  所以当前情况下的答案为 树的直径，显然不如前面有交点的情况。

因此，我们需要先求出树的直径，得到树的直径对应的端点 $A$ 和 $B$。此处我们不再假设 $A$ 距离 $C$ 更近了，对于剩下的 $\min{(dist_{CA}, dist_{CB})}$，我们可以反过来考虑，枚举树中的每个节点作为点 $C$，取最大的 $\min{(dist_{CA}, dist_{CB})}$ 加上即可。

对于求树的直径，一般有两种方法，分别为 两次 $dfs$ 和 树形DP。题解中将采用 两次 $dfs$ 求得树的直径长度及其两个端点。（关于树的直径球阀及求法正确性可以看 OI Wiki 树的直径）

对于枚举的部分，我们可以从两个端点开始求出各自到其他点的树上距离，可以采用 $dfs$ 或者 $bfs$ 等等。题解中，我用了 双源 $bfs$（名字大概是我自己取的）的技巧，就是将两个端点 $A$ 和 $B$ 同时入队，定义数组 $d[u]$ 为 $\min{(dist_{CA}, dist_{CB})}$，在双源 $bfs$ 的过程中，第一次访问到点 $u$，其更新得到的距离就是 $\min{(dist_{CA}, dist_{CB})}$。最后枚举得到最大的 $d[u]$，加上树的直径的长度即为答案。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 2e5 + 10, M = (N << 1);

int h[N], e[M], ne[M], w[M], idx;
// 链式前向星
void add(int a, int b, int c){
    e[ ++ idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx;
}

ll dist[N];  // 两次dfs求树的直径
int a, b, f; // a, b 树的直径端点 f 为从当前根节点向下搜索得到的最远点
// dfs求树的直径
void dfs(int u, int fa){
    for(int i = h[u]; i; i = ne[i]){
        int v = e[i];
        if(v == fa) continue;
        dist[v] = dist[u] + w[i];    // 自顶向下更新
        if(dist[v] > dist[f]) f = v; // 更新最远点
        dfs(v, u);
    }
}

ll d[N];
// 双源bfs求d[u]，即 \min(dist_{CA}, dist_{CB})
void bfs(){
    memset(d, 0x3f, sizeof d);
    queue<int> q;
    q.push(a), d[a] = 0;
    q.push(b), d[b] = 0;  // 同时入队

    while(q.size()){
        int u = q.front();
        q.pop();

        for(int i = h[u]; i; i = ne[i]){
            int v = e[i];
            if(d[v] > d[u] + w[i]) q.push(v), d[v] = d[u] + w[i];
        }
    }
}

int main(){
    ios;

    int n, m; cin >> n >> m;
    while(m -- ){  // 题目确定是一个树，m其实没用，这里甚至for[1...n]都可以
        int u, v, c; cin >> u >> v >> c; 
        add(u, v, c), add(v, u, c);
    }

    f = 1;
    dfs(1, -1); // 从节点1搜索得到最远点 一定是树的直径的端点之一
    a = f;      // A 选取为树的直径端点

    dist[f] = 0;
    dfs(f, -1); // 从当前端点第二次搜索，得到最远点，即树的直径的另一个端点
    b = f;      // B 选取为树的直径另一个端点，第二次dfs求得的dist[f]即树的直径

    bfs();      // 双源bfs求d[u]

    ll res = 0; // 枚举C点
    for(int i = 1; i <= n; i ++ ) res = max(res, dist[f] + d[i]);
    cout << res << '\n';

    return 0;
}

选取 $A, B$ 为树的直径端点的正确性

我们可以通过反证法来证明选取 $A，B$ 为树的直径端点这一贪心思路的正确性。

假设我们选取的 $A，B$ 不是树的直径的端点，而 $D，E$ 为树的直径端点。由于树的直径的特性，$A$ 和 $B$ 一定有交点在树的直径 $DE$ 上，交点之间的路径是完全重复的，对后期的证明没有什么影响，故我们完全可以认为交点是同一个，我们记为 $F$。如下图所示：

由于 $DE$ 为树的直径，而 $AB$ 不是，故我们需要满足以下关系：

$$a + b < d + f$$

同时，我们还不能让 $AD$，$AE$，$BD$，$BE$ 的路径长度为树的直径，故需要还满足以下关系：

$$a + d < d + f \rightarrow a < f$$

$$a + f < d + f \rightarrow a < d$$

$$b + d < d + f \rightarrow b < f$$

$$b + f < d + f \rightarrow b < d$$

我们可以再假设 $a < b$ 且 $d > f$，对于此时我们选取的 $A, B$，我们可以选取 $D$ 作为 $C$，即选择路径 $D \rightarrow F \rightarrow A \rightarrow F \rightarrow B$，此时得到最长长度为 $d + 2 \times a + b$ 。

但是，我们可以发现，如果任意选取路径 $B \rightarrow F \rightarrow E \rightarrow F \rightarrow D$，那么路径长度为 $b + 2 \times f + d$ 。根据前面需要满足的关系 $a < f$，显然 $d + 2 \times a + b < d + 2 \times f + b$ 。所以，如果选取 $A，B$ 不是树的直径的端点，那么必有一条路径比此时选取 $A, B$ 能够得到的最长路径长度更长。

因此，我们反证法可以得到，选取 $A, B$ 为树的直径端点这一贪心策略是最优的。

关于存在多对树的直径端点的问题

还是和前面类似的一张图，如下图所示：

我们假设 $A, B$ 和 $D, E$ 是两对树的直径端点。显然我们需要满足以下关系：

$$a + b = d + f$$

因为 $A$ 和 $D$ 各自都是树的直径端点，而且两点之间的路径长度还必须满足 $\le$ 树的直径长度，所以此时只有 $AD$ 路径距离长度也是树的直径长度才能同时满足这两个条件。也就是满足如下关系：

$$a + d = a + b = d + f$$

由此，我们可以得出 $b = d$ 且 $a = f$。

类似上面的证明，我们还可以得到 $a = d$ 且 $b = f$，故我们可以发现：

$$a = b = d = f$$

所以，对于存在多对树的直径端点的情况，我们可以发现，最长的路径长度一定是在 $A, B, C$ 选取为三个不同的树的直径的端点时得到的，此时的答案就是 两倍的树的直径长度（选取 $C$ 为非树的直径端点显然不会更长）。

因此，完全不用担心出现多对树的直径的情况，任意选取 $A, B$ 为一对树的直径端点后，枚举到最后的 $C$ 一定会是另一个树的直径的端点，且答案就是两倍树的直径。

F. 欢迎来到雾雨魔法店

题目描述

初始情况下有 $n$ 个点，每个点对应一个下标 $a_i$ 和 一个值 $b_i$。给 $m$ 次操作：

对于操作 1 l r，则输出 $[l, r]$ 区间范围内前缀和的期望（平均值，即 $\frac{\sum_{i=l}^r s_i}{r - l + 1}$，其中 $s_i$ 为前缀和）。

对于操作 2 x y，将下标为 $x$ 的值 增加 $y$。

「YAC Round 3」欢迎来到雾雨魔法店

解题思路 动态开点线段树 + 维护前缀和区间和

根据数据范围，采用一般线段树无疑会内存超限。因此我们需要进行离散化，但是本题在两种操作中都会出现先前未出现过的下标（对应题中的等级）。故如果采用离散化的技巧，我们还必须把操作中所有的下标也存起来再进行离散化，而操作又涉及区间询问，区间的离散化显然会比较繁琐，因此我们可以转而采用另外一种技巧 动态开点。（动态开点线段树）

因为下标数据范围，达到了 $32$ 位带符号整数，所以，我们定义 $\text{INF} = 2147483647$，即 $2^{31} - 1$，$[1, \text{INF}]$ 为我们的操作区间。

动态开点线段树开的空间大小需要关注的是 操作次数 和 区间范围，注意操作次数还包括了前面初始的 $n$ 次，也就是说操作次数的上限为 $2\times 10^5$。对于每次操作的区间，我们最多涉及到 $\log(v)$ 个节点（$v$ 就是区间范围大小），根据题中所给数据范围显然我们只需要开 $32$ 倍的操作次数大小空间即可。

解决了空间问题，那么如何处理操作 $1$ 中的前缀和期望值呢？

如果每次处理操作 1 l r，把范围内的 $sum_i$ 全部求出来再累加，最后再除以区间长度 $r - l + 1$，很明显是会超时的。

我们可以 维护前缀和的区间和，因此，我们需要将 单点修改操作转换为区间修改操作。比如下标 $x$ 上的值要加上 $y$，下标 $x$ 对应的前缀和为 $sum_x$（即 $[1, x]$ 范围内的对应数值之和）。那么基于前缀和的性质，下标 $x$ 后面的位置也都需要加上 $y$，即对区间 $[x, \text{INF}]$ 范围内每个数都要加上 $y$。由此，我们将单点修改操作转变为了区间修改操作。

也就是说，对于操作 1 l r，我们只需要输出 $[l, r]$ 范围内的前缀和区间和再除以区间长度即可；对于操作 2 x y 以及初始化操作，我们则需要进行区间修改，将 $[x, \text{INF}]$ 范围内所有数加上 $y$ 即可。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 2e5 + 10, INF = 2147483647; 

struct node{int ls, rs; ll sum, lazy;}tr[N * 32]; // 动态开点线段树
int root, tot; // root为根节点 tot为涉及节点个数

void pushup(int u){
    tr[u].sum = tr[tr[u].ls].sum + tr[tr[u].rs].sum;
}

void pushdown(int u, int l, int r){
    if(tr[u].lazy){ // 懒标记
        int mid = l + r >> 1;
        if(!tr[u].ls) tr[u].ls = ++ tot;
        if(!tr[u].rs) tr[u].rs = ++ tot; // 动态开点
        tr[tr[u].ls].lazy += tr[u].lazy;
        tr[tr[u].ls].sum += tr[u].lazy * (mid - l + 1);
        tr[tr[u].rs].lazy += tr[u].lazy;
        tr[tr[u].rs].sum += tr[u].lazy * (r - mid);   
        tr[u].lazy = 0;     
    }
}

void modify(int &u, int l, int r, int ql, int qr, ll x){
    if(!u) u = ++ tot;  // 动态开点
    if(ql <= l && r <= qr){
        tr[u].lazy += x, tr[u].sum += x * (r - l + 1); 
        return;
    }
    pushdown(u, l, r);
    int mid = l + r >> 1;
    if(ql <= mid) modify(tr[u].ls, l, mid, ql, qr, x);
    if(qr > mid) modify(tr[u].rs, mid + 1, r, ql, qr, x);
    pushup(u);
}

ll query(int u, int l, int r, int ql, int qr){
    if(!u) return 0ll;
    if(ql <= l && r <= qr) return tr[u].sum;
    pushdown(u, l, r);
    int mid = l + r >> 1; ll res = 0;
    if(ql <= mid) res += query(tr[u].ls, l, mid, ql, qr);
    if(qr > mid) res += query(tr[u].rs, mid + 1, r, ql, qr);
    return res;
}

int n, m;

int main(){
    ios;

    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){  
        int x, y; cin >> x >> y;
        modify(root, 1, INF, x, INF, y); // 维护前缀和区间和 从当前位置加到末尾
    }

    while(m -- ){
        int op, x, y; cin >> op >> x >> y;
        if(op == 1) {
            double res = query(root, 1, INF, x, y);
            printf("%.4lf\n", res / (y - x + 1));
        }else{
            modify(root, 1, INF, x, INF, y); // 区间修改
        }
    }

    return 0;
}