100分解法

比较基础的一个差分题。可以选择离散化m个区间去差分，时间复杂度o(mlogm)，空间复杂度o(m)。当然，由于本题n较小，也可以不进行差分，时间复杂度o(n)，空间复杂度o(n)。
讲一下具体的思路。首先如果我们每棵树都没有浇水的话，m天后每棵树高度都为m。如果m是奇数的话，我们找到浇水次数为偶数的树的个数即可，反之找到浇水次数奇数的树个数即可，统计这一件事就需要用到差分。对于每个区间，我们可以在l[i]打上一个+1的标志，在r[i]打上一个-1的标志，然后用sum一边遍历数组一边记录数组的前缀和，在某一棵树的位置sum的值就是这棵树浇水的次数，统计一下其中奇数偶数的个数即可。下面给出不离散化的代码：

int a[20000005];
class Solution {
public:
    /**
     * 返回m天后高度为奇数的树的数量
     * @param n int整型 
     * @param m int整型 
     * @param l int整型vector 
     * @param r int整型vector 
     * @return int整型
     */
    int oddnumber(int n, int m, vector<int>& l, vector<int>& r) {
        // write code here
        for(int i=0;i<m;i++)a[l[i]]++,a[r[i]+1]--;
        int ans=0,sum=0;
        for(int i=1;i<=n;i++)
        {
            sum+=a[i];
            if(sum%2)ans++;
        }
        if(m%2)return n-ans;
        return ans;
    }
};