AcWing 算法基础课week 1 总结(万字长文)
AcWing 算法基础课week 1 总结
总结点 1：快速排序（分治思想）
题1：从小到大排序
主体思路：定义一个数x属于数组s，利用双指针，将数组分为大于等于x和小于等于x的两部分，然后递归处理。（具体步骤如下）
1.
如上图所示，我们定义一个数组s用来储存n个数据，然后定义两个指针i j,分别指向数组的左右两端，同时i指针逐个向右移动扫描数组，j指针同理向左。
2.
当i,j指针扫描的过程中，当s[i]>x时，指针i就停止移动，同理当s[j]<x时，指针j就停止移动，然后交换s[i]与s[j]，那么就使得大于x的s[i]去到了右边的数组，小于x的s[j]去到了左边的数组。
while(i<j)
{
do i++;while(s[i]<x);//i指针向右移动，当s[i]>x,移动停止，j同理
do j--;while(s[j]>x);
if(i<j)swap(s[i],s[j]);//如果i<j说明s[j]<x<s[i],就进行交换
}
3.
重复以上操作，直到i>=j为止。然后相同的方式利用递归处理左右两半边的数组，直到子数组长度等于1。
quick_sort(s,l,j);
quick_sort(s,j+1;r);
完整代码如下
int n;
int s[1000010];
void quick_sort(int s[], int l, int r)//将s[]数组的l-r区间内的数据排序
{
if (l >= r)return;
//以中点数据值作为分界值，避免边界问题。
//注意：以s[l],s[r]作为分界值时需要考虑边界问题，所以直接取中点値
int x = s[l + r >> 1], i = l - 1, j = r + 1;
while (i < j)
{
do i++; while (s[i] < x);//指针移动直到遇到不符合条件的值
do j--; while (s[j] > x);
if (i < j)swap(s[i], s[j]);//交换两值
}
quick_sort(s, l, j);//递归处理左右两边
quick_sort(s, j + 1, r);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s[i];
}
quick_sort(s, 0, n - 1);//将s[]数组的l-r区间内的数据排序
for (int i = 0; i < n; i++)
{
cout << s[i] << ' ';
}
return 0;
}
题2：找到第k小的数（快速排序的拓展）
主体思路与快排相同，只是递归方式不同。
扫描方式与快排相同，我们直接说不同点（递归）；
当我们利用双指针i,j扫描一个区间时，肯定会将一个区间分成两部分，而我们需要找到第k个数，这个数可能在前半部分或者后半部分，所以我们分情况递归。
1.如果k在前一部分，就只递归前一部分
2.如果在后一部分，就递归后面
int sl = j-l+1;//sl记录的是前一部分有多少个数
if(k<=sl) return quick_sort(s,l,j,k);
else return quick_sort(s,j+1,r,k-(j-l+1));
//注意我们这里输入的第四个变量是指所求数在某一区间的相对位置。
//如果在右边，因为左边部分已经有j-l+1个数了，所以我们应该找这一区间的第k-(j-l+1)个数
完整代码：
int n, k;
vector<int> s;
int quick_sort(vector<int> s, int l, int r, int k)
{
if (l >= r)return s[l];//如果区间长度为1,返回0
int i = l - 1, j = r + 1, x = s[l + r >> 1];
while (i < j)
{
do i++; while (s[i] < x);
do j--; while (s[j] > x);
if (i < j)swap(s[i], s[j]);
}
int sl = j - l + 1;//计算左边部分有多少个数
if (k <= sl)return quick_sort(s, l, j, k);//递归左边
else return quick_sort(s, j + 1, r, k - (j - l + 1));//递归右边
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
s.push_back(x);
}
cout << quick_sort(s, 0, n - 1, k) << endl;
return 0;
}
总结点2：归并排序（分治思想）
题1：排序
主体思路：将数组均分为两半部分，分别有序化，然后合并两个数组
1.
将数组均分为两半部分，利用递归分别有序化。
int mid = l+r>>1;
merge_sort(s,l,mid);
merge_sort(s,mid+1,r);
2.
合并两个数组。利用两个指针i,j分别指向两个数组的起始位置，如果s[i]<s[j]就将s[i]放入新数组，反之放入s[j]。
int temp[1000010];//新数组
int k = 0,i = l,j = mid+1;//k负责控制新数组的下标
while(i<=mid&&j<=r)
{
if(s[i]<s[j]) temp[k++] = s[i++];
else temp[k++] = s[j++];
}
3.
因为我们上面使用的循环条件时while(i<=mid&&j<=r)，所以当一个数组中的全部元素全部放入新数组时，另一个数组可能会还有剩余的数据，所以我们需要将这些数据也放入新数组中。
while(i<=mid) temp[k++] = s[i++];
while(l<=r) temp[k++] = s[j++];
4.
最后需要将新数组中的数据储存回原数组中，因为递归的过程中需要再次用到原数组，所以必须储存回去。
for(int i = l,j = 0;i<=r;i++,j++) s[i] = temp[j];//i控制原数组，j控制临时数组
完整代码如下：
int n;
int s[1000010];
void a(int s[], int l, int r)
{
if (l >= r)return;
int temp[1000010];
int mid = l + r >> 1;
a(s, l, mid);
a(s, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
{
if (s[i] < s[j])temp[k++] = s[i++];
else temp[k++] = s[j++];
}
while (i <= mid) temp[k++] = s[i++];
while (j <= r)temp[k++] = s[j++];
for (int i = l, j = 0; i <= r; i++, j++)
{
s[i] = temp[j];
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)cin >> s[i];
a(s, 0, n - 1);
for (int i = 0; i < n; i++)cout << s[i] << ' ';
return 0;
}
题2：逆序对的数量
主体思想：利用归并排序的将两个数组分别有序化后合并的特点，递归计算逆序对的数量
1.
因为思路同归并排序，我们直接讲不同点。
对于一组逆序对，可以分为图中的三种情况：
1.同时在左侧数组
2.同时在右侧数组
3.分别在左右两侧数组
发现对于1,2种情况，当我们将数组进行递归排序时，总有一个区间可以使得两个数分别在数组中点的左右两侧，从而转化为第3种情况，所以我们只考虑第三种情况。
2.
考虑图中的情况，因为两个数组都已经有序化，所以对于s[j]发现有s[i]到s[mid]的部分（图中红色部分）都大于s[j]，所以后面的所有数都可与s[j]构成第三种逆序对，逆序对的数量为mid-i+1。
3.
完整代码实现：
const int N = 100010;
int n;
int a[N];
long long ans;
long long merge_sort(int l, int r)
{
if (l >= r)return 0;
int mid = l + r >> 1;//中点
merge_sort(l, mid);//递归处理左右两边，是左右两边有序化
merge_sort(mid + 1, r);
int temp[N];//临时数组
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
{
if (a[i] <= a[j])temp[k++] = a[i++];//将小的数放入临时数组
else
{
temp[k++] = a[j++];
//如果s[i]>s[j],说明s[i]-s[mid]的数都与s[j]构成逆序对
//个数为mid-i+1
ans += mid - i + 1;
}
}
while (i <= mid) temp[k++] = a[i++];
while (j <= r)temp[k++] = a[j++];
for (int i = l, j = 0; i <= r; i++, j++)a[i] = temp[j];
return ans;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << merge_sort(0, n - 1) << endl;
return 0;
}
总结点3：二分
直接讲整数二分，浮点数二分只需要修改细节就好，后面会讲
1.
每次找到区间的中点，将s[mid]与x的值相比较。如果是图中的这种情况，x>s[mid] ，所以x存在于右区间。那么调整区间，将区间的左端点调整为mid+1（为什么是mid+1后面会讲），再去循环处理右区间。另一种情况同理。
2.
因为存在边界问题，所以这里的二分需要分情况讨论，对应的代码也有两种。
首先是边界调整的问题。重要的就是那边可以取到最后的值x，就将哪边的边界调整为mid。直接看代码讲。(代码题目是找到x在数组中的位置)
先看第一种
int l = 0,r = n-1//设置左右端点
while(l<r)
{
int mid = l+r>>1;//设置中点
if(s[mid]<=x) r = mid;
//注意此时x可以在这个判断条件中取到，所以这个条件对应的边界调整为mid
else l = mid+1;
//另一个对应的调整为mid+1或mid-1；
}
再看第二种
int l = 0,r = n-1;
while(l<r)
{
int mid = l+r+1>>1;
if(s[mid]<=x) l = mid;
//这时x可以在新的条件中取到，所以对应边界调整为mid,其余同理。
else r = mid-1;
}
3.
另外的，两种情况所移动的方向不同。
当用第一种模版时，将会从数组左向右去找x的值，直到从左向右找到第一个数为止，此时的边界l就是第一个x的位置。
当用第二种模版时，将会从右向左，直到找到一个数为止，l代表找到的第一个x的位置,注意使用这个模版时，mid = l+r+1>>1。
我们下面看例题
题1：找到一个数的范围
主体思路：利用第一种模版找到左边界，然后利用第二种去找右边界
看代码：
int main()
{
int n, q;//n是数组长度，注意默认是升序排列，然后q个查询
cin >> n >> q;
vector<int> s(n);
for (auto& n : s)
{
cin >> n;
}
while (q--)
{
int x;
cin >> x;
int l = 0, r = n - 1;//设置左右边界
while (l < r)//找到左边界
{
int mid = l + r >> 1;
if (s[mid] >= x)r = mid;
else l = mid + 1;
}
if (s[l] != x)//如果没有X就输出-1 -1
{
cout << "-1 -1" << endl;
}
else
{
cout << l << ' ';
l = 0; r = n - 1;
while (l < r)//找到右边界
{
int mid = l + r +1>> 1;//注意+1的细节
if (s[mid] <= x)l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}
题2：数的三次方根
这个题就是浮点数二分，浮点数二分比整数二分简单，因为没有边界条件，两个值都去调整为mid。
不多说，直接看代码：
double n;
bool check(double x)//利用check函数去判断条件
{
return x * x * x < n;
}
int main()
{
cin >> n;
double l = -10000, r = 10000;//题目中给的左右边界的范围
while (fabs(r - l) > 1e-8)//浮点数相等的判断
{
double mid = (l + r) / 2;
if (check(mid)) l = mid;//两个都去调整为mid
else r = mid;
}
cout << fixed << setprecision(6) << l;//输出6位小数
return 0;
}
总结点4：高精度
所有的高精度都是利用数组去储存一个数，然后通过模拟手算的方式去计算。（之前有发过一期高精度，但是看了y神的代码之后，决定去学习一下y神的代码，很美观）
1.高精度加法
高精加的主体思路就是将两个数组的相同位置上的数字相加，如果大于10就进位。
核心代码看一下：
vector<int > c;
int t= 0;
for(int i = 0;i<max(a.size(),b.size());i++)
{
if(i<a.size()) t+=a[i];
if(i<b.size()) t+=b[i];
c.push_back(t%10);
t/=10;
}
if(t) c.push_back(t);
return c;
完整代码如下：
string x, y;
vector<int> add(vector<int > a, vector<int> b)
{
vector<int> c;
int t = 0;
for (int i = 0; i < max(a.size(), b.size()); i++)
{
if (i < a.size())t += a[i];//如果a有这位数字，就加上
if (i < b.size())t += b[i];
c.push_back(t % 10);//每次将t的个位数输入到c中
t /= 10;//保留t的10位进行下一次计算
}
if (t)c.push_back(t);//因为加法可能有进位，所以最后检查一下进位
return c;
}
int main()
{
cin >> x >> y;
vector<int> a, b;
//两个字符串倒序输入到数组中
for (int i = x.size() - 1; i >= 0; i--)a.push_back(x[i] - '0');
for (int i = y.size() - 1; i >= 0; i--)b.push_back(y[i] - '0');
auto c = add(a, b);
//倒序输出
for (int i = c.size() - 1; i >= 0; i--)cout << c[i];
return 0;
}
2.高精度减法
1.两个数相减，如果小于0，就进位。
vector<int> c;
int t = 0;
for (int i = 0,t = 0; i < a.size(); i++)
{
t = a[i] - t;//t储存的是上一位的借位，先减去。
if (i < b.size())t -= b[i];//如果b存在这位数，就减去
c.push_back((t + 10) % 10);
//减去之后，t有可能是负数需要借位，所以利用(t+10)%10,输出借位后的结果
if (t < 0) t = 1;//如果t<10，就借位
else t = 0;
}
while (c.size() > 1 && c.back() == 0)c.pop_back();//除前导0
return c;
2.那么到这里就有问题了，上面的代码我们只考虑了A>B的情况，那么A-B<0时怎么办？
很简单，只要用B-A，然后提起输出一个负号就好啦。
那我们先判断A是否大于B;
bool check(vector<int> a,vector<int> b)
{
//如果位数不一样，位数多的大
if(a.size()!=b.size()) return a.size()>b.size();
//如果位数一样，就从高位到低位逐位判断
//因为我们倒序将字符串转化为了数组，所以高位在最后面
for(int i = a,size()-1;i>=0;i--)
{
if(a[i]!=b[i]) return a[i]>b[i];
}
}
下面是完整代码：
string x, y;
bool cmp(vector<int> a, vector<int> b)//判断大小
{
if (a.size() != b.size())return a.size() > b.size();
for (int i = a.size() - 1; i >= 0; i--)
{
if (a[i] != b[i])return a[i] > b[i];
}
return true;
}
vector<int> sub(vector<int> a, vector<int> b)
{
vector<int> c;
for (int i = 0,t = 0; i < a.size(); i++)
{
t = a[i] - t;
if (i < b.size())t -= b[i];
c.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (c.size() > 1 && c.back() == 0)c.pop_back();
return c;
}
int main()
{
cin >> x >> y;
vector<int > a, b;
for (int i = x.size() - 1; i >= 0; i--)a.push_back(x[i] - '0');
for (int i = y.size() - 1; i >= 0; i--)b.push_back(y[i] - '0');
if (cmp(a, b))//如果a>b，正常计算
{
auto c = sub(a,b);
for (int i = c.size() - 1; i >= 0; i--)cout << c[i];
}
else//如果b>a
{
auto c = sub(b, a);
cout << '-';//先输出’-‘
//然后输出b-a
for (int i = c.size() - 1; i >= 0; i--)cout << c[i];
}
}
3.高精度乘法（大数乘小数）
如图示（利用的就是乘法与c[i]的规律，具体证明省略，如想看，请评论区提问），直接就得到核心代码：
vector<int> mul(vector<int> a, int b)
{
vector<int> c;
//注意循环条件
for (int i = 0, t = 0; i < a.size() || t; i++)//注意乘法时，当a被执行完后，t不一定为0，但还需要继续将t输入到c中
{
if (i < a.size())t += a[i] * b;//如果a有这位数，就t+=a[i]*b;
c.push_back(t % 10);//将t的个位输入到c中
t /= 10;
}
while (c.size() > 1 && c.back() == 0)c.pop_back();//去除前导0
return c;
}
完整代码如下：
string x;
int b;
vector<int> mul(vector<int> a, int b)
{
vector<int> c;
for (int i = 0, t = 0; i < a.size() || t; i++)
{
if (i < a.size())t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while (c.size() > 1 && c.back() == 0)c.pop_back();
return c;
}
int main()
{
cin >> x >> b;
vector<int> a;
for (int i = x.size() - 1; i >= 0; i--)a.push_back(x[i] - '0');
auto c = mul(a, b);
for (int i = c.size() - 1; i >= 0; i--)cout << c[i];
return 0;
}
4.高精度除法
如图，我们设定b数组为被除数，a为除数，r为余数。
我们从b高位到低位进行计算，那么第一个商c0就应该等于b[4]/a的商，然后余数r就等于b[4]%a;
下一次的除数就等于r*10+b[i]，反复计算。
下面看代码实现：（因为我们要保证加减乘除的输入方式统一，所以在输入a数组时依旧是倒序输入）
//代码中的a与b与图中的a,b相反。
vector<int> div(vector<int> &a, int &b,int &r)
{
vector<int> c;
for (int i = a.size() - 1; i >= 0; i--)//因为a是倒序输入，但是除法需要从高位到低位进行计算，所以i = a.size()-1
{
r = r * 10 + a[i];//每一次的被除数等于r*10+a[i]
c.push_back(r / b);//商等于r/b;
r %= b;余数等于r%b
}
reverse(c.begin(), c.end());//反转之后消除前导0
while (c.size() > 1 && c.back() == 0)c.pop_back();
return c;
}
完整代码如下：
vector<int> div(vector<int> &a, int &b,int &r)
{
vector<int> c;
for (int i = a.size() - 1; i >= 0; i--)
{
r = r * 10 + a[i];
c.push_back(r / b);
r %= b;
}
reverse(c.begin(), c.end());
while (c.size() > 1 && c.back() == 0)c.pop_back();
return c;
}
int main()
{
string x;
int b;
cin >> x >> b;
vector<int> a;
for (int i = x.size() - 1; i >= 0; i--)a.push_back(x[i] - '0');
int r = 0;
auto c = div(a, b,r);
for (int i = c.size() - 1; i >= 0; i--)
{
cout << c[i];
}
cout << endl << r << endl;
return 0;
}
总结点5：前缀和与差分
前缀和与差分互为逆运算。
1.前缀和
首先我们先介绍前缀和。先去定义一个数组a，储存n个数据，然后定义一个数组b，去储存前缀和。
那么b[0] = a[0]，b[1] = a[0] + a[1]，b[2] = a[0] + a[1] + a[2]，.......;
以上的b数组就是a的前缀和数组，
前缀和就是将前k个数相加，这个和就是前缀和。
然后我们根据b数组的特点，可以得出以下的递推公式：
b[i] = b[i-1] + a[i];
有了这个特点之后，我们就可以递推计算出b数组的全部初始值，代码如下：
vector<int> s(n + 1);
s[0] = 0;//注意两个数组的边界问题
for (int i = 1; i < n + 1; i++)
{
cin >> s[i];
}
vector<int> a;
a.push_back(0);//由于递推公式中有a[i-1],所以我们的循环从i = 1开始，以避免边界问题，对应的s也从i= 1开始储存。
for (int i = 1; i <= n; i++)
{
a.push_back(a[i - 1] + s[i]);
}
那么我们有了初始化之后的前缀和数组之后，就可以很快的计算出一个区间内所有元素的和，
我们输入所求期间的左边界l，和右边界r，那么这一段区间的和就可以表示为，b[r]-b[l-1];
完整代码实现如下：
int main()
{
int n, m;//数组长度为n,询问个数为m
cin >> n >> m;
vector<int> s(n + 1);
s[0] = 0;
for (int i = 1; i < n + 1; i++)
{
cin >> s[i];
}
vector<int> a;
a.push_back(0);
for (int i = 1; i <= n; i++)
{
a.push_back(a[i - 1] + s[i]);
}
while (m--)//m个询问
{
int l, r;
cin >> l >> r;
cout << a[r] - a[l - 1] << endl;
}
return 0;
}
2.差分
那么前缀和和差分是分不开的，所以我们下面去介绍差分。
差分和前缀和是互为逆运算，那么我们先给出一个前缀和数组a，然后定义一个原数组b；
所以这个a叫做b的前缀和，b叫做a的差分。
那么我们根据两者的关系，就可以根据前缀和数组求出原数组，然而我们其实并不需要掌握求原数组的方法，重要的是掌握它的性质。
我们去看一个例题：
1.首先我们将a,b,数组的全部元素全部初始化为0,
2.我们要进行的操作是在l-r之间的每个数＋c，其实我们初始时输入的数组可以看成在i-i之间插入元素a[i],所以将两种操作合并为一种。
下面是重点思路：我们将要进行操作的数组看做前缀和数组a，然后假想一个原数组b。
要想在l-r之间的每个数+c，可以将原数组中的b[l]+=c;
那么在a[l]之后所有的a[]将都加上一个c，（因为图中红色部分和绿色部分所有的a[]都含有b[l]这一项）；
但我们最终是要在l-r之间的数＋c，所以需要打一个补丁（即将a[r+1]-=c，只有绿色部分含有a[r+1]，而红色部分不含有）,那么这样就使得a[r]之后的所有a[]回归正常。
总结以上的思路，可以得出核心代码：
void insert(int l, int r, int x)
{
a[l] += x;
a[r + 1] -= x;
}
完整代码如下：
const int N = 100010;
int a[N];
void insert(int l, int r, int x)//插入函数
{
a[l] += x;
a[r + 1] -= x;
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
insert(i, i, x);//初始化数组可以看做在i-i之间插入x
}
while (m--)//m组操作
{
int l, r, c;
cin >> l >> r >> c;
insert(l, r, c);
}
for (int i = 1; i <= n; i++)//利用差分求出前缀和数组
{
a[i] += a[i - 1];
}
for (int i = 1; i <= n; i++)
{
cout << a[i] << ' ';
}
return 0;
}
3.二维前缀和
那么有了以上的基础，我们将前缀和拓展到2维，求一下二维前缀和；
同样的道理，我们定义两个二维数组a,b，a为前缀和数组，b为原数组；
我们要计算前缀和a[i,j];可以看出a[i,j]由两个红色部分，一个绿色部分和一个棕色部分组成。
那可以得出表达式:a[i,j] = a[i-1,j]->(一个绿色+一个红色)+a[i,j-1]->（一个绿色+一个红色）+b[i,j]->（棕色部分）-a[i-1,j-1]->(减去多余的绿色部分)
由此得出核心代码：
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];
}
}
那么我们得到一个已经初始化的前缀和数组，就可以求出图形中任意一个矩阵中的元素和;
例如上图，我们要求白色矩阵中所有的元素和，可以用金色边框内所有的元素减去绿色部分，再减去蓝色部分，最后将两部分重叠的部分加回来，就得到了所求。
代码如下：
cout << b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1]<<endl;
完整代码：
const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
int main()
{
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
}
}
while (q--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1]<<endl;
}
return 0;
}
3.二维差分
同样的不需要掌握如何求差分，只需要掌握它的性质。
直接看一道题
将数组(x2,y2),(x1,y1)构成的矩阵中的所有元素＋c
我们还是将要操作的数组看做前缀和数组a，假想一个原数组b。
当我们给b[i,j]+c之后，四个涂色部分将全部+c；
然后我们去打补丁：将b[x1,y2+1]-=c，黄色和蓝色部分将-=c;将b[x2+1,y1]-=c，红色部分和蓝色部分将-=c;
然后发现蓝色部分多-=c，所以我们让b[x2+1,y2+1]+=c，那么蓝色部分将+=c;
大功告成，完整代码如下：
const int N = 1010;
int n, m, q;
int a[N][N];
void insert(int x1, int y1, int x2, int y2,int r)
{
a[x1][y1] += r;
a[x2 + 1][y2 + 1] += r;
a[x1][y2 + 1] -= r;
a[x2 + 1][y1] -= r;
}
int main()
{
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
int x;
cin >> x;
insert(i, j, i, j, x);
}
}
while (q--)
{
int x1, y1, x2, y2,r;
cin >> x1 >> y1 >> x2 >> y2 >> r;
insert(x1, y1, x2, y2, r);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
cout << a[i][j] << ' ';
}
cout << endl;
}
return 0;
}
以后将不定时更新这个系列，如果对你有帮助的话请点赞支持一下！