前缀和差分

一维前缀和int n, m, l, r; int a[N], s[N]; cin n; for (int i 1; i n; i) { cin a[i]; s[i] s[i-1] a[i]; // 构建前缀和 } cin m; while (m--) { cin l r; cout s[r] - s[l-1] endl; // O(1) 查询区间和 }注意1.N值一定要够大。或者用vectorint a(N,0)初始化。2.数组从1开始遍历。一维差分int n, q, l, r, x; int a[N], b[N]; // b为差分数组 cin n q; for (int i 1; i n; i) { cin a[i]; b[i] a[i] - a[i-1]; // 构建差分 } while (q--) { cin l r x; b[l] x; b[r1] - x; // 区间修改 } for (int i 1; i n; i) { a[i] a[i-1] b[i]; // 还原数组 cout a[i] ; }1.差分构建还原熟练。二维前缀和int n, m, q, x1, y1, x2, y2; int a[N][N], s[N][N]; // 构建二维前缀和 s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j]; // 查询子矩阵和 int sum s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1];二维差分int n, m, x1, y1, x2, y2; int b[N][N]; // 差分矩阵 // 对子矩阵 (x1,y1) 到 (x2,y2) 进行 c 操作 void add(int x1, int y1, int x2, int y2, int c) { b[x1][y1] c; b[x1][y21] - c; b[x21][y1] - c; b[x21][y21] c; } // 最后求二维前缀和还原原矩阵 for(int i1;in;i){ for(int j1;jn;j){ a[i][j]d[i][j]a[i-1][j]a[i][j-1]-a[i-1][j-1]; couta[i][j]; } cout\n; }重新排序问题描述给定一个数组 和一些查询,, 求数组中第至第个元素之和。小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可 以增加多少?输入格式输入第一行包含一个整数。第二行包含个整数1,2,⋯,, 相邻两个整数之间用一个空格分隔。第三行包含一个整数表示查询的数目。接下来 行, 每行包含两个整数 、, 相邻两个整数之间用一个空格分 隔。输出格式输出一行包含一个整数表示答案。样例输入51 2 3 4 521 32 5样例输出4样例说明原来的和为 61420, 重新排列为 (1,4,5,2,3)后和为 101424, 增 加了 4。思路问题转化要最大化所有查询结果的总和等价于让“值大的数字”尽量出现在“被查询次数多的位置”上。因为无论数组顺序如何每个位置被查询的总次数是固定的。2. 统计次数差分我们需要一个高效的方法计算出数组的每个位置被查询了多少次。如果对每个查询区间 [Li, Ri] 都遍历一遍加1复杂度是 O(n * m)在 n,m ≤ 1e5 的规模下会严重超时。◦ 解法使用差分数组。diff[l] 1, diff[r1] - 1。处理完所有查询后对 diff 求一次前缀和就得到了每个位置被查询的次数 cnt[i]。这个过程将区间更新优化到了 O(n m) 的时间复杂度-11-16。3. 重新排序贪心 排序不等式既然想让“大数”配“大次数”那很简单把原始数组 A 和被查询次数的数组 cnt都按非递增顺序排序然后将对应位置相乘并求和就能得到重新排序后的最大可能总和-5-17。这背后用到了“排序不等式”的原理。4. 计算答案最终的答案 最大可能总和 - 原数组总和。#include bits/stdc.h using namespace std; typedef long long LL; const int N 100010; int n, m; int a[N], cnt[N]; // a存储原数组cnt存储每个位置被查询的次数 int main() { // 1. 输入数据 cin n; for (int i 1; i n; i) cin a[i]; // 2. 差分统计查询次数 (区间修改) cin m; while (m--) { int l, r; cin l r; cnt[l]; // 差分标记区间开始1 cnt[r1]--; // 差分标记区间结束后-1 } // 3. 前缀和还原真实次数 for (int i 1; i n; i) { cnt[i] cnt[i-1]; } // 4. 计算原数组的查询总和 LL original_sum 0; for (int i 1; i n; i) { original_sum (LL)a[i] * cnt[i]; } // 5. 排序让大的数字去对应大的查询次数 sort(a 1, a n 1); // 升序 sort(cnt 1, cnt n 1); // 升序 // 6. 计算重新排序后的最大可能总和 LL max_sum 0; for (int i 1; i n; i) { max_sum (LL)a[i] * cnt[i]; } // 7. 输出最多能增加的值 cout max_sum - original_sum endl; return 0; }