NC23054 华华开始学信息学

题目链接

题目描述

因为上次在月月面前丢人了，所以华华决定开始学信息学。十分钟后，他就开始学树状数组了。这是一道树状数组的入门题：

给定一个长度为 NN 的序列 AA ，所有元素初值为 00 。接下来有 MM 次操作或询问：
操作：输入格式：1 D K，将 ADAD 加上 KK 。
询问：输入格式：2 L R，询问区间和，即 ∑Ri=LAi∑i=LRAi 。

华华很快就学会了树状数组并通过了这道题。月月也很喜欢树状数组，于是给华华出了一道进阶题：
给定一个长度为 NN 的序列 AA ，所有元素初值为 00 。接下来有 MM 次操作或询问：
操作：输入格式：1 D K，对于所有满足 1≤i≤N1≤i≤N 且 i≡0(modD)i≡0(modD) 的 ii ，将 AiAi ​加上 KK 。
询问：输入格式：2 L R，询问区间和，即 ∑Ri=LAi∑i=LRAi 。
华华是个newbie，怎么可能会这样的题？不过你应该会吧。

输入描述

第一行两个正整数 NN 、MM 表示序列的长度和操作询问的总次数。
接下来M行每行三个正整数，表示一个操作或询问。

输出描述

对于每个询问，输出一个非负整数表示答案。

示例1

输入

输出

3526

备注

1≤N,M≤1051≤N,M≤105 ， 1≤D≤N1≤D≤N ， 1≤L≤R≤N1≤L≤R≤N ， 1≤K≤1081≤K≤108

知识点：树状数组，根号分治。

显然，这道题的修改并不能转化为可懒标记的区间修改，也没有很好的方法转化为单点修改。

我们可以考虑暴力优化的一种，根号分治。将修改操作的 DD 分为两部分，按阈值 BB 划分：

1. D≤BD≤B 时，采用标记法， 用 addadd 数组表示某个 DD 加了多少，复杂度 O(1)O(1) 。
2. D>BD>B 时，采用暴力修改法，倍增修改树状数组 x≡0(modD)x≡0(modD) 的点，复杂度 O(nBlogn)O(nBlog⁡n) 。

修改总体复杂度为 O(nBlogn)O(nBlog⁡n) 。

同时，查询操作也要随之改变：

1. D≤BD≤B 部分，暴力累和每个 DD 的贡献，即 ∑i=1Baddi⋅(⌊ri⌋−⌊l−1i⌋)∑i=1Baddi⋅(⌊ri⌋−⌊l−1i⌋) ，复杂度 O(B)O(B)。
2. D>BD>B 部分，直接查询树状数组即可，复杂度 O(logn)O(log⁡n) 。

查询总体复杂度为 O(B+logn)O(B+log⁡n) 。

我们尝试平衡查询和修改的复杂度。假设 BB 能使 lognlog⁡n 被忽略，则需要满足 nBlogn=BnBlog⁡n=B ，解得 B=nlogn−−−−−√B=nlog⁡n 。因此， B=nlogn−−−−−√B=nlog⁡n 是我们所需要的阈值，其能使总体复杂度为 O(nlogn−−−−−√)O(nlog⁡n) 。

实际上，这道题用理论最优阈值时间不是最优的，用 B=n−−√B=n 快将近一倍，可能由于数据的 DD 普遍较小，使得查询代价上升较明显。

这里采用 B=n−−√B=n 阈值。

时间复杂度 O(mn−−√logn)O(mnlog⁡n)

空间复杂度 O(n)O(n)

#include <bits/stdc++.h>using namespace std;using ll = long long; template<class T>class Fenwick { int n; vector<T> node;public: Fenwick(int _n = 0) { init(_n); } void init(int _n) { n = _n; node.assign(n + 1, T::e()); } void update(int x, T val) { for (int i = x;i <= n;i += i & -i) node[i] += val; } T query(int x) { T ans = T::e(); for (int i = x;i >= 1;i -= i & -i) ans += node[i]; return ans; } T query(int l, int r) { return query(r) - query(l - 1); }}; struct T { ll sum; static T e() { return { 0 }; } T &operator+=(const T &x) { return sum += x.sum, *this; } friend T operator-(const T &a, const T &b) { return { a.sum - b.sum }; }}; ll add[100007]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m; cin >> n >> m; Fenwick<T> fw(n); for (int i = 1;i <= m;i++) { int op; cin >> op; if (op == 1) { int d, k; cin >> d >> k; if (d * d <= n) add[d] += k; else for (int i = d;i <= n;i += d) fw.update(i, { k }); } else { int l, r; cin >> l >> r; ll ans = fw.query(l, r).sum; for (int i = 1;i * i <= n;i++) ans += add[i] * (r / i - (l - 1) / i); cout << ans << '\n'; } } return 0;}