神经,树状数组做多了一开始还想着用树状数组来查询差分数组,但是我们要进行所有元素的查询,直接过一遍就好啦
class Solution {
public:int numberOfPoints(vector<vector<int>>& nums) {vector<int> c(105, 0);for (int i = 0; i < nums.size(); i++) {c[nums[i][0]] += 1;c[nums[i][1] + 1] -= 1;}int ans = 0; int num = 0;for (int i = 1; i < 105; i++) {num += c[i];ans += (num > 0);}return ans;}
};
就好像这个题目,我们可以小试牛刀直接进行树状数组
int a[60];
int lowbit(int x) { return x & (-x); }
void add(int x, int p) {for (int i = x; i <= 50; i += lowbit(i)) {a[i] += p;}
}
int query(int x) {int sum = 0;for (int i = x; i; i -= lowbit(i)) {sum += a[i];}return sum;
}class Solution {
public:bool isCovered(vector<vector<int>>& ranges, int left, int right) {for (int i = 1; i <= 50; i++) a[i] = 0;for (int i = 0; i < ranges.size(); i++) {add(ranges[i][0], 1);add(ranges[i][1] + 1, -1);}int flag = 1;for (int i = left; i <= right; i++) {int t = query(i);if (!t) {flag = 0; break;}}return flag;}
};