记录46
#include<bits/stdc++.h> using namespace std; int main(){ int a[5010]={},c[5010]={}; int n,m,b,g,s,e,cnt=0,cnt_x=0; cin>>n>>m>>b>>g; while(b--){ cin>>s>>e; for(int i=s;i<=e;i++) a[i]=1; } while(g--){ cin>>s>>e; for(int i=s;i<=e;i++) c[i]=1; } for(int i=1;i<=n;i++){ if(a[i]==1) cnt+=m; else cnt_x++; } for(int i=1;i<=m;i++){ if(c[i]==1) cnt+=cnt_x; } cout<<cnt; return 0; }题目传送门https://www.luogu.com.cn/problem/P2692
突破点
每个男生负责打扫一些连续的行，
👉对行进行操作
每个女生负责打扫一些连续的列。
👉对列进行操作
思路
如果直接二维数组铺开，很显然会TLE超时，所以需要转换思路
- 标记出现的行数组跟列数组的编号
- 统计行数组，如果打扫过就加上列数
- 统计列数组，如果打扫过就加上未被打扫的行数（列行重复的部分不需要打扫）
注意：统计列数时，加上未被打扫的行数，是因为这一列中，有些被行打扫完毕
代码简析
#include<bits/stdc++.h> using namespace std; int main(){ int a[5010]={},c[5010]={}; int n,m,b,g,s,e,cnt=0,cnt_x=0; cin>>n>>m>>b>>g; while(b--){ cin>>s>>e; for(int i=s;i<=e;i++) a[i]=1; } while(g--){ cin>>s>>e; for(int i=s;i<=e;i++) c[i]=1; } ... ... return 0; }n（行）,m（列）,b（男生数）,g（女生数）,
s（开始打扫编号）,e（结束打扫编号）,
cnt=0（统计一共打扫的格子）,cnt_x=0（未被打扫的行数）
两个while()循环👉记录行列的打扫情况
#include<bits/stdc++.h> using namespace std; int main(){ int a[5010]={},c[5010]={}; int n,m,b,g,s,e,cnt=0,cnt_x=0; cin>>n>>m>>b>>g; while(b--){ cin>>s>>e; for(int i=s;i<=e;i++) a[i]=1; } while(g--){ cin>>s>>e; for(int i=s;i<=e;i++) c[i]=1; } for(int i=1;i<=n;i++){ if(a[i]==1) cnt+=m; else cnt_x++; } for(int i=1;i<=m;i++){ if(c[i]==1) cnt+=cnt_x; } cout<<cnt; return 0; }for(int i=1;i<=n;i++){}👉遍历行数
if(a[i]==1) cnt+=m;👉这一行被打扫，加上这一行的格子（即列数）
else cnt_x++;👉记录下来没被打扫的行数
for(int i=1;i<=m;i++){}👉遍历列数
if(c[i]==1) cnt+=cnt_x;👉这一列被打扫，统计除行打扫外的部分
补充
在CSP中遍历超大二维数组（如
10⁴×10⁴）时，O(n²)暴力遍历必然超时。以下是系统性优化思路，按优先级排序：1. 前缀和/差分（O(1)区间查询）
场景：频繁查询子矩阵和、最大值、最小值
暴力问题：
// 每次查询O(n²)，Q次查询O(n²Q) = 10¹²，必TLE for (int i = x1; i <= x2; i++) for (int j = y1; j <= y2; j++) sum += a[i][j];优化后：
// 预处理O(n²)，每次查询O(1) int pre[N][N]; // pre[i][j] = Σa[1..i][1..j] pre[i][j] = a[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]; // 查询子矩阵和O(1) int sum = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];时间：从
O(n²Q)降到O(n² + Q)2. 降维打击（转化为一维问题）
场景：二维DP、最值问题
暴力问题：
// 二维DP：O(n²m²) = 10⁸，边界 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int k = 0; k < i; k++) for (int l = 0; l < j; l++) dp[i][j] = max(dp[i][j], dp[k][l] + cost);优化后：
// 将每行/每列压缩，转化为一维线段树DP: O(n*m log m) // 或扫描线思想: O(n*m) for (int i = 1; i <= n; i++) { // 对每一行用单调队列/线段树维护最值 for (int j = 1; j <= m; j++) { dp[i][j] = query_max(i, j) + a[i][j]; } }3. 分块处理（BLock Decomposition）
场景：区间修改+区间查询，但数据不全是10⁴×10⁴
思想：将n×n矩阵分成√n×√n块，每块单独处理
int block = sqrt(n); for (int bx = 0; bx < n; bx += block) for (int by = 0; by < n; by += block) // 每块内部暴力，块间O(1)处理 process_block(bx, by);复杂度：
O(n²/block² × block²) = O(n²)，但常数降低，缓存友好4. 数据结构优化（树状数组/线段树）
场景：动态二维区间查询/修改
暴力问题：
// 单点更新+区间查询：每次O(n²)，Q次O(n²Q) = 10¹² update(x, y, val); query(x1, y1, x2, y2);优化后：
// 二维树状数组：每次O(log²n)，Q次O(Q log²n) = 10⁶ void update(int x, int y, int val) { for (int i = x; i <= n; i += i & -i) for (int j = y; j <= n; j += j & -j) bit[i][j] += val; } int query(int x, int y) { int sum = 0; for (int i = x; i > 0; i -= i & -i) for (int j = y; j > 0; j -= j & -j) sum += bit[i][j]; return sum; }5. 方向性优化（减少遍历范围）
场景：只关心特定方向（如右下、左上）
暴力问题：
// 四个方向遍历：4×n×m = 4×10⁸，超时 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int dir = 0; dir < 4; dir++) check(i+dx[dir], j+dy[dir]);优化后：
// 预处理每个方向的前缀：O(n×m) // 查询时O(1) for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { right[i][j] = right[i][j-1] + 1; // 向右连续1数量 down[i][j] = down[i-1][j] + 1; // 向下连续1数量 } } // 查询时直接读取，无需遍历6. 贪心/双指针（跳过无效遍历）
场景：单调性问题
暴力问题：
// 每行找最右0：O(n²) for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i][j] == 0) rightmost[i] = j; } }优化后：
// 从右往左一次扫描：O(n×m) for (int i = 1; i <= n; i++) { for (int j = m; j >= 1; j--) { // 从右往左 if (a[i][j] == 0) { rightmost[i] = j; break; // 找到后立即跳出 } } } // 或每行用二分：O(n log m)7. 缓存友好优化（空间换时间）
场景：行列交替访问，缓存命中率低
原始问题：
// 访问a[i][j]和a[j][i]，缓存抖动，速度慢3倍 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) sum += a[i][j] + a[j][i];优化后：
// 复制转置矩阵：O(n²)，但后续访问缓存友好 int b[N][N]; // b是a的转置 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) b[j][i] = a[i][j]; // 后续操作：连续内存访问，速度快 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) sum += a[i][j] + b[i][j];8. 竞赛通用决策树
是否需要遍历整个二维数组？ ├── 是 → 能否用前缀和/差分转为O(1)查询？ │ ├── 能 → 预处理O(n²) + O(1)查询 │ └── 否 → 降维/分块/数据结构优化 │ ├── 否 → 能否用贪心/双指针减少遍历范围？ │ ├── 能 → 局部遍历O(n)或O(n log n) │ └── 否 → 方向性优化或缓存优化9. 一句话总结
暴力遍历O(n²)是万恶之源，CSP-J/S中优先往前缀和、降维、数据结构三条路想，能O(1)不O(n)，能O(n)不O(n²)。
