本篇文章着重介绍CSP认证第二题常见考点，以【202012-202206】6次真题的第二题为例，旨在帮助你我从70分（暴力模拟，运行超时）到100分（利用特定技巧，降低时间复杂度）。
此文参考了众多大佬的优秀文章和视频，感恩你们的分享。
考点 202009：常规模拟，不卡时间202012：前缀和&后缀和202104：二维前缀和202109：一维差分202112：分段&差值202203：一维差分202206：稀疏数组 前置知识学习前缀和与差分 图文并茂 超详细整理（全网最通俗易懂）林小鹿@的博客-CSDN博客_前缀和差分
【小白学算法】2. 稀疏数组 - 知乎 (zhihu.com)
真题 一、前缀和&后缀和 题干202012-2 期末预测之最佳阈值
代码（100分） #includeusing namespace std;const int MAX=1e5+5;pair pii[MAX]; //pair数组储存信息，每个pair存储一个同学的y和resultint pre0[MAX];//记录该位置及前面的result为0的个数（前缀和）int rear1[MAX]; //记录该位置及后面的result为1的个数（后缀和）int k = -1,ma = 0;//k用来记录最佳阈值，ma用来存储最佳阈值对应的预测成功的数目int main(){int m;cin>>m; //输入mpii[0] = pair(-1,-1);for(int i = 1;i >pii[i].first>>pii[i].second;sort(pii + 1,pii + 1 + m); //将所有学生信息按照阈值从小到大排序，方便后续前缀后缀和的操作for(int i = 1;i = 1;--i)//记录后缀1个数if(pii[i].second == 1)rear1[i] = rear1[i + 1] + 1;elserear1[i] = rear1[i + 1];for(int i = 1;i L>>r>>t;int g[MAX][MAX];for(int i=1;ig[i][j];g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];//前缀和预处理}for(int i=1;i=0;i--){for(int j=0;j>B[i][j];}int temp[52][52];int count=0;for(int i=1;i(L-S)) || (a[i].y>(L-S))){continue;}for(int x=S;x>=0;x--){//缩小查找的绿化图规模for(int y=0;y