什么是前缀和？

• 数列的和时，Sn = a1+a2+a3+…an; Sn就是数列的前 n 项和。

• 前缀和就是新建一个数组，新建数组中保存原数组前 n 项的和。

前缀和有什么用？

• 快速求某个区间中所有元素的加和。例 S5 = a1 + a2 + a3 + a4 + a5; S2 = a1 + a2。所以可以通过 S5-S2 得到 a3+a4+a5 的值。

代码：

#include <iostream>
using namespace std;
const int N = 100010;
int a[N];//保存原数组
int s[N];//保存前缀和
int main(){
    int n, m;
    cin >> n >> m;
    //从a[1]开始保存。a[0]是0
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }

    s[0] = 0;
    //计算前缀和
    for(int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + a[i];

    for(int i = 0; i < m; ++i){
        int l, r;//保存区间
        cin >> l >> r;
        //s[r] = a[1]+ ··· + a[r]
        //s[l - 1] = a[1]+ ··· + a[l - 1]
        //s[r] - s[l - 1] = a[l] + ··· + a[r]
        cout << s[r] - s[l - 1] << endl;
    }
}

什么队列？

• 就是一个特殊的数组。这个数组，最前面叫队头，最后面叫队尾。只允许在最后面添加元素，只允许在最前面删除元素。

解题思路：

• 用一个数组 q 保存数据。

• 用 hh 代表队头，q[hh] 就是队头元素， q[hh + 1] 就是第二个元素。

• 用 tt 代表队尾， q[tt] 就是队尾元素， q[tt + 1] 就是下一次入队，元素应该放的位置。

• [hh, tt] 左闭右闭，代表队列中元素所在的区间。

• 出队pop：因为 hh 代表队头，[hh, tt] 代表元素所在区间。所以出队可以用 hh++实现，hh++后，区间变为[hh + 1, tt]。

• 入队push：因为 tt 代表队尾，[hh, tt] 代表元素所在区间。所以入出队可以用 tt++实现，hh++后，区间变为[hh, tt + 1], 然后在q[tt+1]位置放入入队元素。

• 是否为空empty：[hh, tt] 代表元素所在区间，当区间非空的时候，对列非空。也就是tt >= hh的时候，对列非空。

• 询问队头query：用 hh 代表队头，q[hh] 就是队头元素，返回 q[hh] 即可。

代码

#include <iostream>
using namespace std;
const int N = 100010;
int q[N];

//[hh, tt] 之间为队列（左闭右闭）
int hh = 0;//队头位置
int tt = -1;//队尾位置
//操作次数
int m;
//操作方式
string s;

//入队：队尾先往后移动一格，再放入要插入的数据
void push(int x){
    q[++tt] = x;
}
//出队：队头往后移动一格
void pop(){
    hh++;
}
//[hh, tt]表示队列区间，当tt >= hh时，区间为空
void empty(){
    if(tt >= hh) cout << "NO" << endl;
    else cout << "YES" << endl;
} 
//hh指向队头，q[hh]代表队头元素
void query (){
    cout << q[hh] << endl;
}

int main(){
    cin >> m;
    while(m--){
        cin >> s;
        //入队
        if(s == "push"){
            int x;
            cin >> x;
            push(x);
        }
        //出队
        if(s == "pop"){
            pop();
        }
        //问空
        if(s == "empty"){
            empty();
        }
        //问队头
        if(s == "query"){
            query();
        }
    }
}

<= 点个赞吧

递归想法很容易想到，现在提一个找规律的算法。

通过题意可以得出以下结论：

• 当把一个点染色后，他和它的儿子都被染色。

• 根节点开始的颜色是：0

• 因为目标颜色的范围是 1~n， 根节点肯定要染色。

再想一下：

• 根节点染色后，他所有儿子节点变为和根节点一样的颜色。

• 所以：只要儿子节点和父亲节点颜色不一样，就要染一次。

得出解题思路：只要数一数和父亲节点颜色不一样的节点有几个，答案就是几

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2e4 + 10;
//p保存父节点编号，t保存目标颜色
int p[N],t[N];
int main()
{
    int n;
    cin >> n;
    p[1] = 0;
    for(int i = 2; i <= n; ++i)
    {
        cin >> p[i];
    }
    for(int i = 1; i <= n; ++i)
    {
        cin >> t[i];
    }
    int res = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(t[i] != t[p[i]])//和父节点颜色不一样，就要染一次
        {
            res ++;
        }
    }
    cout << res << endl;
    return 0;
}

堆排序概念补充

1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序， 它的最坏、最好、平均时间复杂度均为 O(nlogn)， 它也是不稳定排序。

2. 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值， 这种情况称为大顶堆，注意:没有要求结点的左孩子的值和右孩子的值的大小关系。

3. 每个结点的值都小于或等于其左右孩子结点的值， 这种情况称为小顶堆。

4. 大顶堆举例说明:
   

5. 小顶堆举例说明:
   
6. 一般升序采用大顶堆， 降序采用小顶堆。

基本思想

1. 将待排序序列构造成一个大顶堆。

2. 此时，整个序列的最大值就是堆顶的根节点。

3. 将其与末尾元素进行交换， 此时末尾就为最大值。

4. 然后将剩余 n-1 个元素重新构造成一个堆， 这样会得到 n 个元素的次小值。 如此反复执行， 便能得到一个有序序列了。

可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了。

堆排序步骤图解

数组 {4,6,8,5,9},要求使用堆排序法，将数组升序排序(升序采用大顶堆，降序采用小顶堆)。

构造

1. 将给定无序序列结构如下。

2. 从最后一个非叶子结点开始，从右至左，从下至上进行调整。
   调整规则：找到该节点和他的所有儿子。如果该节点中存的值是找到节点值中的最大值，则不进行调整。如果不是，就将该节点的值和最大值进行交换，然后递归的调整和该节点交换值得那个节点。如下图：

• 最后一个非叶子结点开始（也就是下面的 6 结点），从左至右，从下至上进行调整。6 有两个儿子：5 和 9，这三个值中 9 最大。6 和 9 交换。

• 因为 6 和 9 交换了，递归处理现在保存 6 的那个节点，发现它没有儿子，停止递归。

• 找到第二个非叶节点4，由于[4,9,8]中9元素最大，4 和 9 交换。

• 因为 4 和 9 交换了，递归处理现在保存 4 的那个节点: 找到它的两个儿子：5, 6, 其中 6 最大，交换 4 和 6。

• 然后继续递归处理，发现现在保存4 的节点没有儿子，停止。

• 此时，我们就将一个无序序列构造成了一个大顶堆。

排序

1. 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。如下图：

• 将堆顶元素 9 和末尾元素 4 进行交换。

• 重新调整结构（规则如上），使其继续满足堆定义。

• 再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8。

• 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序。

总结

1. 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆。

2. 将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端。

3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

本题可以使用堆排序，构造小顶堆，然后输出堆顶，输出后把堆顶和堆尾交换。重复执行m次即可。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];//保存数组
int n, m;//n个点，求前m小
int r ;//堆得右边界
void down(int u)//调整函数
{
    //t记录最小点的编号
    int t = u;

    //有左儿子，并且左儿子比t节点的值小，更新t
    if(2 * u <= r && a[2 * u] < a[u]) t = 2 * u;

    //有右儿子，并且右儿子比t节点的值小，更新t
    if(2 * u + 1 <= r && a[2 * u + 1] < a[t]) t = 2 * u + 1;

    //如果待调整点不是最小的
    if(u != t)
    {
        //和最小的交换
        swap(a[u], a[t]);

        //递归处理
        down(t);
    }
}



int main()
{
    cin >> n >> m;
    r = n;//开始时，右边界是数组边界

    //读入数据
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        cin >> a[i];
    }

    //从第一个非叶节点开始，从右到左，从下到上处理每个节点
   for(int i = n /2 ; i >= 1; i--)
   {
       down(i);
   }

    //输出m个最小值
    while (m -- )
    {
        //堆顶保存的最小值，输出堆顶
        cout << a[1] << " ";

        //将堆顶和右边界交换
        swap(a[1], a[r]);

        //右边界左移
        r--;

        //从新处理堆顶
        down(1);
    }
}

<= 点赞支持一下吧~~

什么是并查集？

逐字拆解一下，并、查、集。这个三个字，其中前面两个字都是动词，第三个字是个名词。

先看名词，因为只有知道了这个东西是什么，才能去理解它能干什么。

集就是集合，中学时期就学过这个东西，集合用大白话说就是将一堆元素没有顺序地摆放在同一个地方。

其实并查集本质就是集合。

那它能做什么呢？这就要看前两个字 - “并” 和 “查”。

集合的一些操作，例如，交集，并集等等，这里的 “并” 其实就指的是并集操作，两个集合合并后就会变成一个集合。例如：

{1,3,5,7} U {2,4,6,8} = {1,2,3,4,5,6,7,8}

那 “查” 又是什么呢？集合本身只是容器，最终还是要知道里面存的是什么元素，因此这里的 “查” 是对于集合中存放的元素来说的，即要查找这个元素在不在集合中，还要确定这个元素是在哪个集合中。

好了，现在知道并查集是什么，以及它能干什么了，总结下来就是：

• 并查集可以进行集合合并的操作（并）
• 并查集可以查找元素在哪个集合中（查）
• 并查集维护的是一堆集合（集）

举个例子：

有8个元素：14, 35, 48, 87, 65, 20。

集：把个位相同的数字归在同一个集合。集合划分为如下：

{14}, {35, 65}, {48}, {87}, {20}

查：给定一个元素，得到这个元素属于哪个集合。例如：

• 给定元素14，可以得出：14 位于第一个集合。
• 给定元素65，可以得出：65 位于第二个集合。
• 给定元素20，可以得出：20 位于第五个集合。

并：将两个集合合并，例如将个位为偶数的集合合并的到第一个集合，个位为奇数的集合合并到第二个集合，结果如下：
{14, 48, 20}, {35, 65, 87}

相信通过上面的表述，已经知道，并查集维护的是一堆集合。用什么样的数据结构表示并查集？

对于并查集，有两个信息是必须要知道的：

• 元素的值。
• 集合的标号。

一个元素必须仅存在于一个集合中，一个集合中可以有多个元素。

元素对集合来说，是多对一的关系。这么看来可以用一个健值对的结构来表示并查集（键是元素，值时所属集合）。

但是如果对元素本身没有特定要求的话，可以使用数组，这样速度更快，使用起来也更加简单：

{0}, {1}, {2}, {3}, {4}, {5} => [0,1,2,3,4,5]

{0,1,2}, {3,4,5} => [0,0,0,3,3,3] or [1,1,1,4,4,4] 

在解释上面的数组表示方式之前，不知道有没有发现一个事实:

• 元素本身的值是固定不变的，但是元素所属的集合是可以变化的”

因此可以使用两个数组：

• 第一个数组保存所有元素
• 第二个数组使用数组的 下标 来代表数组一中元素，对应位置上 存放的值 表示元素所属的集合。

例如：{0,1,2}, {3,4,5} => [0,0,0,3,3,3]：第一个数组是0, 1, 2, 3, 4, 5，第二个数组是0, 0, 0, 3, 3, 3。第一个数组保存了所有元素，第二个数组保存了元素所属集合。

• 第二个数组中，第一个元素是0，含义是：第一个数组的第一个元素属于 0 号集合。
• 第二个数组中，第二个元素是0，含义是：第一个数组的第二个元素属于 0 号集合。
• 第二个数组中，第三个元素是0，含义是：第一个数组的第三个元素属于 0 号集合。
• 第二个数组中，第四个元素是3，含义是：第一个数组的第四个元素属于 3 号集合。
• 第二个数组中，第五个元素是3，含义是：第一个数组的第五个元素属于 3 号集合。
• 第二个数组中，第六个元素是3，含义是：第一个数组的第六个元素属于 3 号集合。

说完了集合的表示，来看看如何基于这种表示去实现 “并” 和 “查”，也就是集合的合并和元素的查找，这两个操作是相互影响的。合并其实就是改变第二个数组中存放的值，这个值表示的是第一个数组对应位置元素所在的集合。

上述实现并查集方法很直观。但是将连个集合合并的时候，需要修改其中一个集合中的所有元素对应的数组二中的值，有没有办法优化下呢？

这个问题的源是：第二个数组中保存的是第一个数组中各个元素所属集合，所以合并集合的时候，第二个数组中需要修改元素比较多。

可以为每个元素选出一个代表它的元素，数组二中存放代表元素

例如：{0,1,2}, {3,4,5} => [0,0,0,3,3,3]：第一个数组是0, 1, 2, 3, 4, 5，第二个数组是0, 0, 0, 3, 3, 3。第一个数组保存了所有元素，第二个数组保存了能代表该元素的元素。

• 第二个数组中，0号位置保存的是0，含义是：第一个数组的0号位置保存的元素和 第一个数组中的0号位置保存的元素属于同一个集合。

• 第二个数组中，1号位置保存的是0，含义是：第一个数组的1号位置保存的元素和 第一个数组中的0号位置保存的元素属于同一个集合。

• 第二个数组中，2号位置保存的是0，含义是：第一个数组的2号位置保存的元素和 第一个数组中的0号位置保存的元素属于同一个集合。

• 第二个数组中，3号位置保存的是3，含义是：第一个数组的3号位置保存的元素和 第一个数组中的3号位置保存的元素属于同一个集合。

• 第二个数组中，4号位置保存的是3，含义是：第一个数组的4号位置保存的元素和 第一个数组中的3号位置保存的元素属于同一个集合。

• 第二个数组中，5号位置保存的是3，含义是：第一个数组的5号位置保存的元素和 第一个数组中的3号位置保存的元素属于同一个集合。

这个时候，如果要合并两个集合，只需要修改代表元素即可。

例如：将{0,1,2}, {3,4,5} => [0,0,0,3,3,3]中的第二个集合合并到第一个集合中，。只需要修改第二个集合的代表元素集合，合并后为：{0,1,2,3,4,5} => [0,0,0,0,3,3]

这个时候，问：5这个元素位于哪个集合？查找过程如下：

1. 在数组一中找到 5 这个元素的位置下标是：5
2. 在第二个数组中查看下标5位置保存的元素是3。说明5这个元素和3这个元素在同一个集合。
3. 在数组一中找到 3 这个元素的位置下标是：3。在第二个数组中查看下标3位置保存的元素是0。说明5这个元素和0这个元素在同一个集合。
4. 在数组一中找到 0 这个元素的位置下标是：0。在第二个数组中查看下标0位置保存的元素是0，也就是找到了代表元素。得出结论5这个元素的代表元素是0，他们在同一个集合。

第二个数组保存代表元素，就能简化集合的合并。

总结：

• 用一个数组保存对应位置元素所属集合的代表元素。
• AB两个集合合并：将B集合代表元素的代表元素设置为A集合的代表元素。
• 查找C元素属于哪个集合：找C元素的代表元素，如果不是他自己，就重复查找代表元素的代表元素，知道查找到一个元素的代表元素是它自己，C就属于整个代表元素所代表的集合。（啊啊啊，绕口令吗！！！）

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int p[N];//存放代表元素

//查找 x 所属的集合，就是 x 元素的代表元素
int find(int x)
{
    //如果 x 的代表元素不是他自己，就递归的x的代表元素修改为代表元素的代表元素
    if(x != p[x]) p[x] = find(p[x]);

    return p[x];
}

//合并a b所在的两个集合
void merge(int a, int b)
{
    int pa = find(a);//找到 a 所在集合的代表元素
    int pb = find(b);//找到 b 所在集合的代表元素
    if(pa != pb)//如果不是同一个，则属于不同集合，需要合并
    {
        p[pa] = pb;//将a所在集合代表元素的代表元素设置为b所在集合的代表元素。
    }
}


void query(int a,int b)
{
    int pa = find(a);//找到 a 所在集合的代表元素
    int pb = find(b);//找到 b 所在集合的代表元素
    //判断 a 和 b 是否有同一个代表元素
    if(pa == pb) cout << "Yes" << endl;
    else cout << "No" << endl;
    return ;
}
int main()
{
    int n, m;
    cin >> n >> m;
    //初始化代表元素集合，开始的时候，各自属于一个集合，即每个元素的代表元素是他自己。
    for (int i = 1; i <= n; i ++ )
        p[i] = i;

    while (m -- )
    {
        char op;
        cin >> op;
        int a, b;
        cin >> a >> b;

        if(op == 'M')
        {//合并
            merge(a, b);
        }
        else
        {//查询
            query(a, b);
        }
    }
}

let buf = "";

process.stdin.on("readable", function() {
    let chunk = process.stdin.read();
    if (chunk) buf += chunk.toString();
});

process.stdin.on("end", function(){
    let nums = buf.split('\n').map(x => {
        return parseInt(x);
    });

    //循环终止条件如果是 i < nums.length, 调试代码是对的，提交时错的，
    //            如果是 i < nums.length - 1, 调试代码是错的，提交时对的。
    for(let i = 0; i < nums.length - 1; i++){
        if(nums[i] <= 0) nums[i] = 1;
        console.log(`X[${i}] = ${nums[i]}`);
    }
});

$\color{green}{<–画图不易，点下这里}$

分情况讨论

起点 a, 终点 b，传送门：c, d.

• 情况一：不使用传送门，abs(b - a)

• 情况二： a -> c 然后通过c传送到d, 再从d->b。总距离为abs(a - c) + abs(b - d)。

• 情况二： a -> d 然后通过d传送到c, 再从c->b。总距离为abs(a - d) + abs(b - c)。

三种情况取最小值即可。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int a, b, c, d;

int main(){
    cin >> a >> b >> c >> d;
    //3 种情况取最小值即可
    cout << min({abs(b - a), abs(a - c) + abs(d - b), abs(a - d) + abs(b - c)});
    return 0;
}

$\color{green}{<–画图不易，点下这里}$

思路

数据范围比较小模拟即可。

• 开辟一个二维数组。各个元素为0

• 先放割草机，割草机的位置放 1 。

• 再广告牌，广告牌的位置放0.

• 求雨布的上下左右边界

边界里面的面积即为雨布面积。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010;
int g[N][N];

int x1, y1, x2, y2;
int a1, b1, a2, b2;

int main(){
    cin >> x1 >> y1 >> x2 >> y2;
    x1 += 1000;
    x2 += 1000;
    y1 += 1000;
    y2 += 1000;
    cin >> a1 >> b1 >> a2 >> b2;
    a1 += 1000;
    a2 += 1000;
    b1 += 1000;
    b2 += 1000;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(i > x1 && i <= x2 && j > y1 && j <= y2) 
                g[i][j] = 1;
            if(i > a1 && i <= a2 && j > b1 && j <= b2)
                g[i][j] = 0;
        }
    }
    int u1, v1, u2, v2;
    for(int i = 0; i < N; i++){
        u1 = i;
        for(int j = 0; j < N; j++){//求雨布左下点的x的值
            if(g[i][j] == 1){
                u1--;
                break;
            }
        }
        if(u1 != i){
            break;
        }
    }

    for(int i = 0; i < N; i++){//求雨布左下点的y
        v1 = i;
        for(int j = 0; j < N; j++){
            if(g[j][i] == 1){
                v1--;
                break;
            }
        }
        if(v1 != i){
            break;
        }
    }

    for(int i = N - 1; i != 0; i--){
        u2 = i;
        for(int j = 0; j < N; j++){//求雨布右上点的x的值
            if(g[i][j] == 1){
                u2++;
                break;
            }
        }
        if(u2 != i){
            break;
        }
    }

    for(int i = N - 1; i >= 0; i--){//求雨布右上点的y的值
        v2 = i;
        for(int j = 0; j < N; j++){
            if(g[j][i] == 1){
                v2++;
                break;
            }
        }
        if(v2 != i){
            break;
        }
    }
    if(u1 > u2 || v1 > v2) cout << 0;//判断是否雨布坐标是否合法
    else
        cout << (u2 - u1 - 1)*(v2 - v1 - 1);
    return 0;
}

分情况讨论也是可以的~~

$\color{green}{<–画图不易，点下这里}$

思路

数据范围比较小模拟即可。

• 开辟一个二维数组。各个元素为0

• 先放两个广告牌，广告牌的位置放 1 。

• 再放卡车，卡车的位置放0.

求二维数组中1的个数，就是能看到的广告牌的范围。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010;
int g[N][N];

int x1, y1, x2, y2;
int a1, b1, a2, b2;
int u1, v1, u2, v2;
int main(){
    cin >> x1 >> y1 >> x2 >> y2;
    x1 += 1000;//数据中有负数，全部转换成整数
    x2 += 1000;
    y1 += 1000;
    y2 += 1000;
    cin >> a1 >> b1 >> a2 >> b2;
    a1 += 1000;//数据中有负数，全部转换成整数
    a2 += 1000;
    b1 += 1000;
    b2 += 1000;
    cin >> u1 >> v1 >> u2 >> v2;
    u1 += 1000;//数据中有负数，全部转换成整数
    u2 += 1000;
    v1 += 1000;
    v2 += 1000;   
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(i > x1 && i <= x2 && j > y1 && j <= y2) //放第一个广告牌
                g[i][j] = 1;
            if(i > a1 && i <= a2 && j > b1 && j <= b2)//放第二个广告牌
                g[i][j] = 1;

            if(i > u1 && i <= u2 && j > v1 && j <= v2)//放卡车
                g[i][j] = 0;
        }
    }
    int res = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            res += g[i][j];
        }
    }
    cout << res;
    return 0;
}