洛谷解题日记14||前缀和，差分与离散化

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;  // 读取区间的个数 n
    
    vector<pair<int, int>> intervals(n);  // 存储区间的起点和终点，使用 pair 类型
    
    // 读取 n 个区间
    for (int i = 0; i < n; i++) {
        cin >> intervals[i].first >> intervals[i].second;  // 读取每个区间的起点和终点
    }
    
    // 按照区间的起点进行排序
    sort(intervals.begin(), intervals.end());  // 默认按照 pair 的第一个元素（即起点）排序
    
    long long totalLength = 0;  // 用来存储合并后的区间总长度
    int start = intervals[0].first, end = intervals[0].second;  // 初始化第一个区间的起点和终点
    
    // 从第二个区间开始遍历，进行区间合并
    for (int i = 1; i < n; i++) {
        int curStart = intervals[i].first, curEnd = intervals[i].second;  // 当前区间的起点和终点
        
        if (curStart <= end) {  // 如果当前区间的起点小于等于上一个区间的终点，说明两个区间有重叠
            // 合并区间，更新合并后的终点
            end = max(end, curEnd);  // 取当前区间和前一个区间的最大终点
        } else {  // 如果当前区间与前一个区间不重叠
            totalLength += (end - start);  // 累加前一个区间的长度
            start = curStart;  // 更新当前区间的起点
            end = curEnd;  // 更新当前区间的终点
        }
    }
    
    // 最后一个区间的长度要加上
    totalLength += (end - start);  // 最后一个区间的长度
    
    // 输出合并后的区间总长度
    cout << totalLength << endl;
    
    return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;

int r, c, a, b;  // r, c: 蛋糕的行数和列数；a, b: 要切割的行数和列数
int map[501][501], s[501][501], ans;  // map存储原始巧克力碎屑，s为前缀和矩阵，ans为答案

// check函数用于验证是否能保证每个奶牛切割后的区域至少有x块巧克力碎屑
bool check(int x) {
    int now = 0, num = 0;  // now表示当前处理的行，num表示已经切割的块数
    for (int i = 1; i <= r; i++) {
        int dis = 0, sum = 0;  // dis表示当前切割行的巧克力碎屑差值，sum表示切割次数
        for (int j = 1; j <= c; j++) {
            // 判断当前块的巧克力碎屑差值是否满足条件
            if (dis + (s[i][j] - s[i][j-1]) - (s[now][j] - s[now][j-1]) < x) {
                dis += (s[i][j] - s[i][j-1]) - (s[now][j] - s[now][j-1]);  // 更新差值
            } else {
                sum++;  // 如果不满足条件，说明需要切割
                dis = 0;  // 重置差值
            }
        }
        if (sum >= b) {  // 如果已经切割的块数大于等于B，记录当前行
            now = i; 
            num++;
        }
    }
    if (num >= a) return 1;  // 如果已经切割的块数大于等于A，说明切割成功
    return 0;
}

int main() {
    // 输入读取
    cin >> r >> c >> a >> b;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            cin >> map[i][j];

    // 计算前缀和
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            s[i][j] = s[i-1][j] + s[i][j-1] + map[i][j] - s[i-1][j-1];  // 计算前缀和

    // 二分查找答案，h为最小可能值，t为最大可能值（全体碎屑总和）
    int h = 0, t = s[r][c];  // h最小值为0，t最大值为整个蛋糕的碎屑和
    while (h <= t) {
        int mid = (h + t) / 2;  // 取中值进行判断
        if (check(mid)) {  // 如果能满足条件，说明可以更大一些
            h = mid + 1;
            ans = mid;  // 更新答案
        } else {  // 否则说明mid过大，减小范围
            t = mid - 1;
        }
    }

    cout << ans;  // 输出最终的答案
}

#include<bits/stdc++.h>  // 引入C++标准库，包含了所有常用的头文件
using namespace std;

int H[10005];  // 数组H用于记录每个横坐标位置的最高高度。数组大小足够覆盖所有横坐标（最大为10000）

int main() {
    register int i, a, b, h;  // 定义变量i用于遍历，a、b用于存储建筑物的左右坐标，h用于存储建筑物的高度
    // 不断读取建筑物的左坐标a、高度h和右坐标b
    while (scanf("%d%d%d", &a, &h, &b) != EOF)  // 直到输入结束
        // 对于每个建筑物，从其左边界到右边界之间的每个横坐标位置，更新该位置的最大高度
        for (i = a; i < b; ++i)  // 遍历每个横坐标
            H[i] = max(H[i], h);  // 更新该位置的高度，取当前高度和已有高度中的最大值
    // 对于所有横坐标（1到9999），检查每个位置的最大高度是否发生变化
    for (i = 1, h = 0; i < 1e4; ++i)  // 从横坐标1开始，遍历到9999
        if (h != H[i])  // 如果当前位置的最大高度与上一个位置的最大高度不同，表示轮廓发生变化
            h = H[i], printf("%d %d ", i, H[i]);  // 输出横坐标和对应的高度，并更新h为当前高度
    return 0;  // 程序结束
}

#include<iostream>
using namespace std;

char ch; // 全局变量，用于快读函数中存储当前读取的字符

template<class T>
inline void rd(T& x) { // 快速输入函数
    x = 0; int w = 1; // 初始化 x 为 0，w 为符号标志
    ch = getchar(); // 读取第一个字符
    while (ch < '0' || ch > '9') { // 跳过非数字字符
        if (ch == '-') w = -1; // 记录负号
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') { // 处理数字字符
        x = (x << 1) + (x << 3) + ch - '0'; // 等价于 x = x * 10 + (ch - '0')
        ch = getchar(); // 读取下一个字符
    }
    x = x * w; // 将符号应用到结果
}

int a[100001]; // 差分数组，用于记录每段铁路的使用次数
unsigned long long t, sum; // t 表示当前累积的使用次数，sum 表示总花费

int main() {
    int n, m, x, y, z; // n: 城市数, m: 城市访问顺序长度
    rd(n), rd(m); // 快速读入 n 和 m

    rd(x); // 读取第一个访问的城市编号
    for (int i = 2; i <= m; i++) { // 遍历后续访问的城市编号
        rd(y); // 读取下一个城市编号
        if (x < y) { 
            a[x]++;   // 正向行驶，当前城市 +1
            a[y]--;   // 终点城市 -1
        } else {
            a[x]--;   // 反向行驶，当前城市 -1
            a[y]++;   // 起点城市 +1
        }
        x = y; // 更新当前城市
    }
  
    for (int i = 1; i < n; i++) { // 遍历所有铁路段
        t += a[i]; // 累积当前段铁路的使用次数

        rd(x), rd(y), rd(z); // 读取当前铁路段的费用 A_i, B_i, C_i
        // 计算直接买票的费用：t * x
        // 计算购买 IC 卡的费用：t * y + z
        // 选择最小的费用并累加到总费用
        sum += t * y + z < t * x ? t * y + z : t * x; 
    }

    cout << sum; // 输出最小花费
    return 0;
}

 便于后面从1开始遍历差分数组

这个问题的目标是找到一个最小的连续区间，包含所有不同品种的奶牛，并且最小化区间的大小（即区间的最大坐标和最小坐标之差）。我们可以通过滑动窗口（双指针法）来解决这个问题，以下是详细的思路：

问题理解与思路

1. 基本问题分析：

   • 我们有 NNN 头奶牛，每头奶牛有一个位置和一个品种编号。目标是找到一个最小的区间，这个区间中包含每个品种的至少一头奶牛。
   • 这个区间的大小定义为区间两端坐标的差值，即 max(x) - min(x)。我们需要最小化这个差值。

2. 关键点：

   • 品种的多样性：我们需要确保在选定的区间内包含所有不同的品种编号。
   • 连续区间：必须是一个连续的区间，且没有跳过任何牛的位置。
   • 最小化区间大小：我们要在包含所有品种的区间中找出最小的一个。

3. 解题思路：使用滑动窗口（双指针方法）。

   • 滑动窗口的基本思想：我们使用两个指针，left 和 right，来维护一个区间。right 不断向右扩展区间，直到区间中包含所有品种的奶牛；当满足条件后，尝试通过移动 left 来缩小区间，同时保持区间内包含所有品种。
   • 如何维护品种的数量：使用一个哈希表（map）来记录当前区间内每个品种奶牛的数量。如果某个品种的奶牛数量为 0，说明当前区间没有包含该品种。
   • 更新最小区间：每当当前区间包含所有品种时，计算区间的大小并更新最小值。

4. 算法步骤：

   1. 预处理：统计所有奶牛的品种数量（sum），以确保我们知道需要包含的品种总数。
   2. 排序：将奶牛按位置 x 从小到大排序，这样可以方便地使用滑动窗口来处理。
   3. 滑动窗口：
      • 使用两个指针 left 和 right，初始化 left = 0，right = 0。
      • 扩展 right 指针，直到区间内包含所有不同的品种。
      • 当区间满足条件时，计算当前区间的大小，并更新最小值。
      • 然后尝试通过移动 left 指针来缩小窗口，直到区间不再满足条件为止。
   4. 返回结果：输出找到的最小区间大小。

5. 数据结构选择：

   • 使用 map<int, int> 来记录当前窗口内每个品种的奶牛数量。
   • 使用 map<int, bool> 来记录哪些品种已经出现在输入数据中，帮助我们计算需要包含的品种数量。

#include<bits/stdc++.h>
using namespace std;

// 定义一个结构体node，用来表示每头牛的坐标x和品种编号p
struct node {
    int x;  // 牛的坐标
    int p;  // 牛的品种编号
};

// s数组用于存储每头牛的坐标和品种编号
node s[70000];

// 一些变量初始化
int ans = 2e9, sum, n, z, tail;
map<int, int> t;  // 用map来统计当前窗口中各品种牛的数量
map<int, bool> pan;  // 用map来记录不同品种牛的种类是否已经出现过
// cmp函数用于按照坐标x从小到大排序牛
bool cmp(node a, node b) {
    return a.x < b.x;
}

int main() {
    cin >> n;  // 输入牛的数量
    // 读取每头牛的位置和品种编号
    for (int i = 1; i <= n; i++) {
        cin >> s[i].x >> s[i].p;
        if (pan[s[i].p] == false) {  // 如果该品种还没出现过
            sum++;  // 品种总数+1
            pan[s[i].p] = true;  // 标记该品种已经出现过
        }
    }

    // 按照坐标x从小到大排序奶牛
    sort(s + 1, s + n + 1, cmp);

    // 初始化滑动窗口
    tail = 1;  // 初始尾指针
    t[s[1].p]++;  // 第一个奶牛的品种加入窗口
    z = 1;  // 当前窗口内已包含的不同品种数量

    // 滑动窗口主循环
    for (int i = 1; i <= n; i++) {  // 遍历所有牛
        // 如果窗口内没有包含所有品种，则右指针tail向右扩展
        while (z < sum && tail < n) {
            tail++;  // 右指针右移
            t[s[tail].p]++;  // 当前品种数量+1
            if (t[s[tail].p] == 1) z++;  // 如果是新增品种，已包含的品种数量+1
        }

        // 如果窗口内包含了所有品种，更新最小成本
        if (z == sum) {
            ans = min(ans, s[tail].x - s[i].x);  // 计算当前区间的长度，并更新最小值
        }

        // 窗口左边界右移，更新品种数量
        t[s[i].p]--;
        if (t[s[i].p] == 0) z--;  // 如果当前品种的奶牛数为0，已包含的品种数量-1
    }

    cout << ans;  // 输出最小区间的长度
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

// 常量定义，最大矿石数量为200010
const int maxn = 200010;

// 矿石的重量、价值、区间的左右端点数组
int w[maxn], v[maxn], l[maxn], r[maxn];

// 前缀和数组，用于快速计算区间符合条件的矿石数量和价值之和
long long pre_n[maxn], pre_v[maxn];

// 用于存储计算的检验值 Y、标准值 s 和当前差值 sum
long long Y, s, sum;

// 矿石数量n，区间数量m，最大矿石重量mx，最小矿石重量mn
int n, m, mx = -1, mn = 2147483647;

// 检查函数，判断给定的W是否符合要求
bool check(int W) {    
    Y = 0;   // 重置检验值
    sum = 0; // 重置差值

    // 初始化前缀和数组
    memset(pre_n, 0, sizeof(pre_n));
    memset(pre_v, 0, sizeof(pre_v));

    // 计算前缀和，pre_n[i] 表示前i个矿石中，重量不小于 W 的矿石数量
    // pre_v[i] 表示前i个矿石中，重量不小于 W 的矿石的总价值
    for (int i = 1; i <= n; i++) {
        if (w[i] >= W) {
            pre_n[i] = pre_n[i - 1] + 1;   // 增加符合条件的矿石数量
            pre_v[i] = pre_v[i - 1] + v[i]; // 增加符合条件的矿石的总价值
        } else {
            pre_n[i] = pre_n[i - 1];        // 没有符合条件的矿石
            pre_v[i] = pre_v[i - 1];        // 矿石的总价值不变
        }
    }

    // 遍历所有区间，计算每个区间的检验值，并累加到 Y
    for (int i = 1; i <= m; i++) {
        // 当前区间[l[i], r[i]]的检验值
        Y += (pre_n[r[i]] - pre_n[l[i] - 1]) * (pre_v[r[i]] - pre_v[l[i] - 1]);
    }

    // 计算与标准值 s 的差值
    sum = llabs(Y - s);  // 使用llabs来计算Y与s的绝对差值

    // 如果Y大于s，返回true，表示需要进一步增大W值
    if (Y > s) return true;
    else return false;  // 否则返回false，表示可以减小W值
}

int main() {
    // 读入矿石数量n、区间数量m以及标准值s
    scanf("%d %d %lld", &n, &m, &s);

    // 初始化矿石的重量和价值，同时记录最大值和最小值
    for (int i = 1; i <= n; i++) {
        scanf(" %d %d", &w[i], &v[i]);
        mx = max(mx, w[i]);  // 更新最大重量
        mn = min(mn, w[i]);  // 更新最小重量
    }

    // 读入所有区间的左右端点
    for (int i = 1; i <= m; i++) {
        scanf(" %d %d", &l[i], &r[i]);
    }

    // 设定二分查找的左右边界
    int left = mn - 1, right = mx + 2, mid;

    // 初始化答案为一个非常大的数
    long long ans = 0x3f3f3f3f3f3f3f3f;

    // 二分查找W值，目的是使得检验值与标准值的差距最小
    while (left <= right) {
        mid = (left + right) >> 1;  // 计算当前区间的中点W值

        // 调用check函数检查当前W值是否满足条件
        if (check(mid)) {
            left = mid + 1;  // 如果当前W值满足条件，尝试增大W
        } else {
            right = mid - 1; // 否则，尝试减小W
        }

        // 更新最小差值
        ans = min(ans, sum);
    }

    // 输出最终最小的差值
    printf("%lld", ans);
    
    return 0;
}

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
using namespace std;

// 定义常量 t 和 n
int t, n, f[1000007], book[1000007 * 3];  // t表示数据组数，n表示每组数据的操作数，f[]是并查集数组，book[]用于离散化存储

// 定义结构体node，用于存储每个操作的三元组 (x, y, e)
struct node {
    int x, y, e;
} a[1000001];

// 排序比较函数，用于将e=1的操作排在前面
bool cmp(node a, node b) {
    return a.e > b.e;  // 使得e=1的操作排在前面，e=1表示相等约束，e=0表示不等约束
}

// 初始化并查集
inline void first(int kkk) {
    for (int i = 1; i <= kkk; i++) {
        f[i] = i;  // 初始时每个元素的父节点是自己
    }
}

// 并查集查找操作，使用路径压缩
int get(int x) {
    if (x == f[x]) return x;  // 如果x是根节点，直接返回
    return f[x] = get(f[x]);  // 否则递归查找父节点，并进行路径压缩
}

int main() {
    // 读取测试数据组数 t
    scanf("%d", &t);
    while (t--) {  // 对每一组数据进行处理
        int tot = -1;
        memset(book, 0, sizeof(book));  // 初始化book数组为0
        memset(a, 0, sizeof(a));        // 初始化操作数组a为0
        memset(f, 0, sizeof(f));        // 初始化并查集数组f为0
        int flag = 1;  // 标记当前问题是否可解，初始为1，表示可解

        // 读取每组数据的操作数 n
        scanf("%d", &n);

        // 读取每个操作的三个参数：x, y, e
        for (int i = 1; i <= n; i++) {
            scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].e);  // a[i].x是变量i的左侧变量，a[i].y是变量i的右侧变量，a[i].e是约束类型（1表示相等，0表示不等）
            book[++tot] = a[i].x;  // 将x变量加入book数组
            book[++tot] = a[i].y;  // 将y变量加入book数组
        }

        // 对book数组进行排序
        sort(book, book + tot);  // 排序后进行去重
        int reu = unique(book, book + tot) - book;  // 去重并返回去重后的元素个数

        // 离散化操作：将每个x和y映射到一个新的值
        for (int i = 1; i <= n; ++i) {
            a[i].x = lower_bound(book, book + reu, a[i].x) - book;  // 获取x在book中的位置
            a[i].y = lower_bound(book, book + reu, a[i].y) - book;  // 获取y在book中的位置
        }

        first(reu);  // 初始化并查集，size是去重后的元素个数
        sort(a + 1, a + n + 1, cmp);  // 按e的值排序，确保e=1的操作排在前面

        // 遍历每一个操作，进行并查集的合并或者判断冲突
        for (int i = 1; i <= n; i++) {
            int r1 = get(a[i].x);  // 获取a[i].x的根节点
            int r2 = get(a[i].y);  // 获取a[i].y的根节点
            if (a[i].e) {  // 如果是相等约束
                f[r1] = r2;  // 合并x和y所在的集合
            } else if (r1 == r2) {  // 如果是“不等”约束且x和y已经在同一个集合
                printf("NO\n");  // 输出NO，表示冲突
                flag = 0;  // 设置标记为不可解
                break;
            }
        }

        // 如果没有冲突，输出YES
        if (flag) {
            printf("YES\n");
        }
    }

    return 0;
}