校门外的树

/*
 * 容斥原理
 * 方法原理：利用容斥原理计算多个区间的并集大小（奇加偶减规则），总树数减去并集大小得到剩余数量；
 *          通过格雷码遍历区间子集，避免重复计算重叠区域的树的数量。
 * 时间复杂度：O(M×2^M)
 * 空间复杂度：O(M)
 * 适用场景：L极大（如1e9）、M极小（≤15）的场景（无法开辟大数组存储标记）
 */
#include <stdio.h>

int main() {
    int L, M;
    if (scanf("%d %d", &L, &M) != 2 || L < 1 || L > 10000 || M < 1 || M > 100) {
        return 1;
    }
    // 总树数（0~L共L+1棵）
    int T = L + 1;
    // ls/rs存储各砍伐区间的左右端点，p用于格雷码遍历子集
    int ls[100], rs[100], p = 1;
    // 遍历每个砍伐区间
    for (int i = 0; i < M; i += 1) {
        int l, r;
        if (scanf("%d %d", &l, &r) != 2 || 0 > l || l > r || r > L) {
            return 1;
        }
        // 先减去当前区间的树数（假设无重叠）
        T -= r - l + 1;
        // 保存当前区间端点
        ls[i] = l;
        rs[i] = r;

        // 容斥原理核心：遍历前i个区间的所有非空子集，修正重叠区域的重复减法
        for (int j = 1; j < p; j += 1) {
            // lc/rc暂存当前子集与当前区间的交集端点
            int lc = l, rc = r;
            // 格雷码转换：j ^ (j>>1) 高效遍历所有子集
            for (int g = j ^ (j >> 1), k = 0; g > 0 && k < i; k += 1, g /= 2) {
                if (g % 2 == 1) {
                    // 计算交集：左端点取大，右端点取小
                    if (lc < ls[k]) {
                        lc = ls[k];
                    }
                    if (rc > rs[k]) {
                        rc = rs[k];
                    }
                    // 无交集则退出当前子集计算
                    if (rc < lc) {
                        break;
                    }
                }
            }
            // 有交集时，按子集大小奇偶性调整（奇加偶减）
            if (rc >= lc) {
                if (j % 2 == 1) {
                    T += rc - lc + 1; // 奇数子集：补回重复减去的交集
                } else {
                    T -= rc - lc + 1; // 偶数子集：再减去多补的部分
                }
            }
        }
        // p翻倍，为下一次遍历所有子集做准备
        p *= 2;
    }
    printf("%d", T);
    return 0;
}

/*
 * 数组标记
 * 方法原理：用数组标记树的状态（0=未砍伐/-1=被砍伐），通过memset批量标记砍伐区间；
 *          最后累加数组值统计剩余未砍伐树的数量（0不影响，-1则总数量减1）。
 * 时间复杂度：O(L+M)
 * 空间复杂度：O(L)
 * 适用场景：L适中（≤1e4）、追求代码简洁性的场景，新手易理解
 */
#include <stdio.h>
#include <string.h>

int main() {
    int L,M;
    if (scanf("%d %d", &L, &M) != 2 || L < 1 || L > 10000 || M < 1 || M > 100) {
        return 1;
    }
    // 总树数（0~L共L+1棵）
    int T = L + 1;
    // t数组：标记树的状态（0=未砍伐，-1=被砍伐）
    int t[T];
    // 初始化：所有树未被砍伐
    for (int i = 0; i < T; i += 1) {
        t[i] = 0;
    }
    // 遍历所有砍伐区间，批量标记被砍伐的树
    for (int i = 0; i < M; i += 1) {
        int l, r;
        if (scanf("%d %d", &l, &r) != 2 || 0 > l || l > r || r > L) {
            return 1;
        }
        // memset按字节赋值：0xff对应int的-1，4*(r-l+1)是区间总字节数（int占4字节）
        // 批量将t[l]~t[r]设为-1（标记为被砍伐）
        memset(t + l, 0xff, 4 * (r - l + 1));
    }
    // 统计剩余树数：未砍伐（+0），被砍伐（-1）
    for (int i = 0; i <= L; i += 1) {
        T += t[i];
    }
    printf("%d", T);
    return 0;
}

/*
 * 跳跃标记
 * 方法原理：通过数组标记每个位置的“下一个未被砍伐的位置”，初始化后遍历砍伐区间完成标记；
 *          再跳跃式遍历标记数组，快速计算剩余未砍伐树的数量，避免重复遍历已标记区间。
 * 时间复杂度：O(L+M)
 * 空间复杂度：O(L)
 * 适用场景：L适中（≤1e4）、M任意的常规场景，效率高且逻辑直观
 */
#include <stdio.h>

int main() {
    int L,M;
    if (scanf("%d %d", &L, &M) != 2 || L < 1 || L > 10000 || M < 1 || M > 100) {
        return 1;
    }
    // 总树数（0~L共L+1棵）
    int T = L + 1;
    // R数组：标记每个位置的「下一个未被砍伐的位置」
    int R[T + 1];
    // 初始化：所有位置未被砍伐，下一个未砍伐位置为自身
    for (int i = 0; i <= T; i += 1) {
        R[i] = i;
    }
    // 遍历所有砍伐区间，完成标记
    for (int i = 0; i < M; i += 1) {
        int l, r;
        if (scanf("%d %d", &l, &r) != 2 || 0 > l || l > r || r > L) {
            return 1;
        }
        // 优化：避免重复标记已处理的区间
        if (r + 1 > R[l]) {
            // 标记[l, r]区间：所有位置的下一个未砍伐位置设为r+1
            for (int i = l; i < r + 1; i += 1) {
                R[i] = r + 1;
                printf("R[%d]=%d\n", i, R[i]);
            }
        }
    }
    // 跳跃遍历：快速计算剩余未砍伐树的数量
    int i = 0;
    while (i <= L) {
        // 找到第一个被砍伐的位置（R[i]≠i）
        for (; i <= L; i += 1) {
            if (i != R[i]) {
                printf("i=%d R[i]=%d\n", i, R[i]);
                break;
            }
        }
        // 减去当前被砍伐区间的长度，然后跳到区间终点继续遍历
        T -= R[i] - i;
        printf("T=%d\n", T);
        i = R[i];
    }
    printf("%d", T);
    return 0;
}

/*
 * 区间合并
 * 方法原理：先通过插入排序将所有砍伐区间按左端点升序排列，再遍历合并重叠/包含区间；
 *          仅计算实际被砍伐的总长度（避免重复减重叠区域），总树数减去该长度得到剩余数量。
 * 时间复杂度：O(M²+M)
 * 空间复杂度：O(M)
 * 适用场景：L极大（如1e9）、M适中（≤1000）的场景，无大数组内存压力
 */
#include <stdio.h>

int main() {
    int L,M;
    if (scanf("%d %d", &L, &M) != 2 || L < 1 || L > 10000 || M < 1 || M > 100) {
        return 1;
    }
    // 总树数（0~L共L+1棵）
    int T = L + 1;
    // ls/rs存储区间的左右端点
    int ls[M], rs[M];
    // 读取区间并插入排序（按左端点升序），为合并区间做准备
    for (int i = 0; i < M; i += 1) {
        int l, r;
        if (scanf("%d %d", &l, &r) != 2 || 0 > l || l > r || r > L) {
            return 1;
        }
        // 插入排序核心：将当前区间插入到已排序的位置
        int j = i - 1;
        // 向前遍历已排序区间，左端点更小则后移区间
        while (j >= 0 && l < ls[j]) {
            ls[j + 1] = ls[j];
            rs[j + 1] = rs[j];
            j -= 1;
        }
        // 将当前区间插入到正确位置
        ls[j + 1] = l;
        rs[j + 1] = r;
    }
    // 合并区间：R为当前合并区间的右端点（初始为第一个区间的右端点）
    int R = *rs;
    // 先减去第一个区间的长度
    T -= R - *ls + 1;
    // 遍历剩余区间，合并重叠/包含区间
    for (int i = 1; i < M; i += 1) {
        // 情况1：区间重叠且右端点超出当前合并区间 → 只减超出部分
        if (ls[i] <= R && rs[i] > R) {
            T -= rs[i] - R;
            R = rs[i]; // 更新合并区间右端点
        }
        // 情况2：区间无重叠 → 减去整个区间长度
        else if (ls[i] > R) {
            T -= rs[i] - ls[i] + 1;
            R = rs[i]; // 更新合并区间右端点
        }
        // 情况3：区间被包含 → 无需处理（避免重复减）
    }
    printf("%d", T);
    return 0;
}

这是我的答案，虽然跟使一样但是我觉得很好理解也很直接
#include <stdio.h>

int main() {
    int L,M;
    scanf("%d %d",&L,&M);
    int tree[20000]={0};
    for(int i=0;i<=L;i++){
        tree[i]=1;
    }
    int l[M];
    int r[M];
    for(int i=0;i<M;i++){
        scanf("%d %d",&l[i],&r[i]);
    }
    for(int i=0;i<M;i++){
        for(int j=l[i];j<=r[i];j++){
            tree[j]=-1;
        }
    }
    int cnt=0;
    for(int i=0;i<=L;i++){
        if(tree[i]==1){
            cnt++;
        }
        // printf("%d.%d ",i,tree[i]);
    }
    printf("%d",cnt);

    
    return 0;
}

#include <stdio.h>

void shu(int a[],int l,int r,int L)
{
    for(int i=0;i<=L;i++)
    {
        if(i>=l&&i<=r)
        {
            a[i]=1;
        }
    }
}
int main() {
    int L,M;
    scanf("%d%d",&L,&M);
    int a[10000]={0};
    int n=M;
    for(int i=0;i<n;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        shu(a,l,r,L);
    }
    int hen=0;
    for(int i=0;i<=L;i++)
    {
        if(a[i]==0)
        {
            hen++;
        }
    }
    printf("%d",hen);
}