Problem
CodeChef FNCS - Chef and Churu
Analysis
下文令 $n,m$ 同阶。
感觉不是很好套线段树等数据结构，那就考虑暴力分块吧。
设块长为 $B$。
首先考虑对 $n$ 个区间分块，预处理出 $f_{i,j}$ 为第 $j$ 个数在第 $i$ 个块中出现次数，这个可以利用差分解决，复杂度为 $O(\frac{n^2}{B})$。
令 $ans_i$ 为第 $i$ 个块所有区间值的和。
然后考虑操作：
- 修改操作：枚举每个块，更新答案 $ans_i\gets ans_i-f_{i,x}a_x+f_{i,x}y$，复杂度为 $O(\frac{n^2}{B})$。
- 查询操作：
- 对于整块，直接累加 $ans_i$ 就行，复杂度为 $O(B)$。
- 对于散块，无法直接计算，需要在块上建立线段树求区间和，复杂度为 $O(B\log B)$。
- 总复杂度为 $O(nB\log B)$，$10^8$ 级别，较难通过。
在查询遇到问题，继续优化，多加一个原序列上分块，然后每个值维护原序列上的前缀和 $s_i$。
此时预处理复杂度不变，考虑操作：
- 修改分在序列块和区间块：在序列块上就修改 $[x,n]$ 中块的值 $s_i$；在区间块上与之前的做法一样。复杂度为 $O(\frac{n^2}{B})$。
- 查询整块就直接加区间块上的 $ans_i$，散块在序列块上做差分，复杂度为 $O(nB)$。
于是总复杂度为 $O(nB+\frac{n^2}{B})$，当 $B=\sqrt{n}$ 时有最小值 $O(n\sqrt{n})$。
AC Code
// Problem: Chef and Churu
#include <bits/stdc++.h>
#define fi first
#define se second
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
using namespace std;const int N = 1e5 + 10, M = 350;int n, q;
int a[N];
int L[N], R[N];
int diff[N];
int blen, id[N], bl[N], br[N];
ull s[N], tag[M]; // 序列块
ull f[M][N], ans[M]; // 区间块void build(int n) {blen = sqrt(n);for (int i = 1; i <= blen; i ++) {bl[i] = br[i - 1] + 1, br[i] = i * blen;}if (br[blen] < n) {blen ++;bl[blen] = br[blen - 1] + 1, br[blen] = n;}for (int i = 1; i <= blen; i ++) {for (int j = bl[i]; j <= br[i]; j ++) {id[j] = i;diff[L[j]] ++, diff[R[j] + 1] --;}for (int j = 1; j <= n; j ++) {diff[j] += diff[j - 1];diff[j - 1] = 0;f[i][j] = diff[j];ans[i] += 1ll * diff[j] * a[j];}diff[n] = 0;}
}void modify(int ql, int qr, int w) {int p = id[ql], q = id[qr];// cout << p << " " << q << '\n';if (p == q) {for (int i = ql; i <= qr; i ++) s[i] += w;}else {for (int i = p + 1; i <= q - 1; i ++) tag[i] += w;for (int i = ql; i <= br[p]; i ++) s[i] += w;for (int i = bl[q]; i <= qr; i ++) s[i] += w;}for (int i = 1; i <= blen; i ++) {ans[i] += f[i][ql] * w;}
}ull query(int ql, int qr) {ull sum = 0;int p = id[ql], q = id[qr];if (p == q) {for (int i = ql; i <= qr; i ++) {sum += s[R[i]] + tag[id[R[i]]] - (s[L[i] - 1] + tag[id[L[i] - 1]]); }}else {for (int i = p + 1; i <= q - 1; i ++) sum += ans[i];for (int i = ql; i <= br[p]; i ++) {sum += s[R[i]] + tag[id[R[i]]] - (s[L[i] - 1] + tag[id[L[i] - 1]]);}for (int i = bl[q]; i <= qr; i ++) {sum += s[R[i]] + tag[id[R[i]]] - (s[L[i] - 1] + tag[id[L[i] - 1]]);}}return sum;
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i ++) {cin >> a[i];s[i] = s[i - 1] + a[i];}for (int i = 1; i <= n; i ++) {cin >> L[i] >> R[i];}build(n);cin >> q;while (q --) {int opt, x, y;cin >> opt >> x >> y;if (opt == 1) {modify(x, n, y - a[x]);a[x] = y;}else {cout << query(x, y) << '\n';}}return 0;
}