Catshao

用户名：Catshao

访问量：28890

签　名：

stO KHIN Orz

等　　级
排　　名	160
经　　验	7140
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2020年第十一届省赛真题-整数小拼接
浏览：1475

蓝桥杯2020年第十一届省赛真题-BST插入节点问题
浏览：548

蓝桥杯2020年第十一届省赛真题-八次求和
浏览：556

你可能喜欢

值域分块题解

　　作者: Catshao　　　　发表时间：2022-02-15 14:41:23 浏览：221　|　评论：0　

原题链接：值域分块

这个有什么用：[[Ynoi2019 模拟赛] Yuno loves sqrt technology II](https://www.luogu.com.cn/problem/P5047) 。

O(1) 区间求和，考虑维护前缀和。使用树状数组做显然是 log 的，于是考虑值域分块。

维护两个信息：以块为单位的前缀和，块内前缀和。

放下代码

```cpp
//
// Created by Cat-shao on 2022/2/15.
//

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

const int MAX_N = 100010;

class block {
public:
    static const int MAX_LEN = 320;
    int b[MAX_N], pre[MAX_LEN], pre2[MAX_N], n, len;

block(int _n) {
        n = _n;
        len = sqrt(n);
        for (int i = 1; i <= n; ++i) {
            b[i] = (i - 1) / len + 1;
        }
        memset(pre, 0, sizeof(pre));
        memset(pre2, 0, sizeof(pre2));
    }

void add(int x, int v) {
        for (int i = x; i <= min(n, b[x] * len); ++i) {
            pre2[i] += v;
        }
        for (int i = b[x]; i <= b[n]; ++i) {
            pre[i] += v;
        }
    }

int sum(int l, int r) {
        return pre[b[r] - 1] + pre2[r] - pre[b[l - 1] - 1] - pre2[l - 1];
    }
};

namespace naive {
    int n, m, a[MAX_N];
    void main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        cin >> n >> m;
        int op, x, y;
        for (int i = 1; i <= m; ++i) {
            cin >> op >> x >> y;
            if (op == 1) {
                a[x] += y;
            } else {
                cout << accumulate(a + x, a + y + 1, 0) << '\n';
            }
        }
    }
}

namespace test {
    void main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n, m, op, l, r;
        cin >> n >> m;
        block b(n);
        for (int i = 1; i <= m; ++i) {
            cin >> op >> l >> r;
            if (op == 1) {
                b.add(l, r);
            } else {
                cout << b.sum(l, r) << '\n';
            }
        }
    }
}

int main()
{
    test::main();
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-统计字符（C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C++代码）

C二级辅导-阶乘数列（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

值域分块题解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

三角形（C语言代码）

关于float，double变量的几点说明

模拟计算器（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

DNA （C语言代码）

勾股数（C语言代码）

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-统计字符 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C++代码）

C二级辅导-阶乘数列 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

值域分块题解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）万恶的long long

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

三角形 （C语言代码）

关于float，double变量的几点说明

模拟计算器 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

DNA （C语言代码）

勾股数 （C语言代码）

C二级辅导-统计字符（C语言代码）

C二级辅导-阶乘数列（C语言代码）

　　评论区

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

三角形（C语言代码）

模拟计算器（C++代码）

勾股数（C语言代码）