新的差分思路

本来只是想试着玩玩，没想到真的过掉了2333

这道题作为学习差分也是很好的

首先c[i] 表示 a[i + 1] - a[i]，也就是从a[i]到a[i + 1]的变化值

然后区间移走大树的问题就好处理了

最后在循环一遍统计一下有多少树没有被移动就行了

记得因为c[i] 表示的是 a[i + 1] - a[i]

而这道题树的下标是从0开始的，所以要特判一下0的情况，不然会WA一个点

CPP

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

int c[10010], n, m, k;

int main() { 
    cin >> n >> m;
    for(int i = 1; i <= m; i++) { 
        int l, r;
        cin >> l >> r;
        if(l) c[l - 1]--;   // 可以理解为接下来的a[i] 的值都--
        else k = -1;
        c[r]++;            // 到这里结束
    }
    int ans = 0;
    for(int i = 0; i <= n; i++) { 
        if(!k) ans++;  // !k表示这个位置的树还没有被移动
        k += c[i];
    }
    printf("%d\n", ans);
}

讨论操作

回复

相关推荐

新的差分思路