Anticái l<r nó có chia thành 2 case (maximize, minimize -> vai trò l r thay đổi nên ko có consistent) còn l<=r thì khỏi nghĩ gì hết cứ condition đúng update lại result thôi. nhìn code l<r đẹp hơn gọn hơn nhưng áp sai thấy cảnh debug liền ko còn đúng mục đích khi sài template nữa
l < r 
l < r nhưng không điều khiển được điều kiện :v ông bạn chuyên tin bảo m dùng l <= r rồi update tiện hơn 
l < r xuất hiện trong cuộc đời em
class Solution:
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
n = len(items)
items.sort()
for i in range(1, n):
items[i][1] = max(items[i][1], items[i - 1][1])
maxBeautyMap = defaultdict(int)
for p, b in items:
maxBeautyMap[p] = max(maxBeautyMap[p], b)
prices = sorted(list(maxBeautyMap.keys()))
result = []
for q in queries:
if not maxBeautyMap[q]:
index = bisect_right(prices, q)
if index > 0:
maxBeautyMap[q] = maxBeautyMap[prices[index-1]]
else:
maxBeautyMap[q]=0
result.append(maxBeautyMap[q])
return result
LC 2070 GoLang treemap
func maximumBeauty(items [][]int, queries []int) []int {
nq, cMaxB := len(queries), 0
rs := make([]int, nq)
sort.Slice(items, func(i, j int) bool {
return items[i][0] < items[j][0] || (items[i][0] == items[j][0] && items[i][1] > items[j][1])
})
tm := treemap.NewWithIntComparator()
for _, item := range items {
if cMaxB < item[1] {
cMaxB = item[1]
tm.Put(item[0], cMaxB)
}
}
for i, query := range queries {
k, v := tm.Floor(query)
if k != nil { rs[i] = v.(int) }
}
return rs
}cái prefix trước i ví dụ có N/2 phần tử, đang duyệt đến giữa:
class Solution:
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
items.sort()
prefix_max_beauty = [items[0][1]]
for price, beauty in items[1:]:
prefix_max_beauty.append(max(prefix_max_beauty[-1], beauty))
res = []
for p in queries:
i = bisect_right(items, [p, inf])
if i == 0:
res.append(0)
else:
res.append(prefix_max_beauty[i-1])
return resl, r = 0, n - 1
Thì là do giả sử sai chứ sao, tại mỗi thời điểm i thì cái dict chỉ chứa các tổng OR của các subarray kết thúc tại i thôi. Ví dụ [i - 1, i] có tổng OR là 100, thì [i - 2, i] chỉ có thể là 100, 101, 110, 111 thôi, chứ không thể là 0xx, rồi nếu [i - 2, i] là 110 thì [i - 3, i] chỉ có thể là 110, 111. Cứ thế cho đến khi bật hết bit 1. Không thể vượt quá số bit.
để chư chỉ cho cthuc flip bit thứ i, nhìn temp cringe quáreverse or bit mệt quáJava:class Solution { public int minimumSubarrayLength(int[] nums, int k) { if(k==0) return 1; int l = 0,r=0; int or = 0; int res= Integer.MAX_VALUE; int[] bit = new int[30]; while(l<=r && r<nums.length){ or|=nums[r]; int n = nums[r]; for(int i = 0;n>0;i++){ bit[i]+=n&1; n>>=1; } while(or>=k) { res = Math.min(res, r - l + 1); int left = nums[l]; int temp = 0; for(int i = 0;left>0;i++){ if((left&1)==1) bit[i]--; left>>=1; } for(int i = 0;i<bit.length;i++){ int b = bit[i]>=1?1:0; temp+=b<<i; } or = temp; l++; } r++; } return res==Integer.MAX_VALUE?-1:res; } }
0 hoặc 1 -> 1: num = num | (1<<i) hay num |= 1<<i // num or 000..1..0000
1 hoặc 0 -> 0: num = num & ~(1<<i) hay num &= ~(1<<i) // num and (11...0..1111)
Code của bác worst case là tất cả queries = nhau thì dpt là O(m^2) nhé, với m là số query
droi bác e mới sửa map lại = array 1-1 với query chứ hong 1-n hashmap nữa
class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
nums = sorted(nums)
n = len(nums)
left, right, greaterThanUpperPairs= 0, n - 1, 0
while left < right:
if nums[left] + nums[right] > upper:
greaterThanUpperPairs += right - left
right -= 1
else:
left += 1
left, right, smallerThanLowerPairs= 0, n - 1, 0
while left < right:
if nums[left] + nums[right] >= lower:
right -= 1
else:
smallerThanLowerPairs += right - left
left += 1
return (n*(n-1)//2) - (smallerThanLowerPairs + greaterThanUpperPairs)class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
nums = sorted(nums)
n = len(nums)
def countPairsLowerThanTarget(target):
left = 0
right = n -1
ans = 0
while left < right:
if nums[left] + nums[right] >= target:
right -= 1
else:
ans += right - left
left += 1
return ans
return countPairsLowerThanTarget(upper + 1) - countPairsLowerThanTarget(lower)class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
nums = sorted(nums)
n = len(nums)
def bisearch(left, target):
right = n - 1
while left <= right:
mid = left + (right - left)//2
if nums[mid] >= target:
right = mid - 1
else:
left = mid + 1
return right + 1
ans = 0
for i, val in enumerate(nums):
left = bisearch(i + 1, lower - nums[i])
right = bisearch(i + 1, upper + 1 - nums[i])
ans += right - left
return ans
Em cũng dùng l <= rsao bác lại phản bội lại template l<rhôm qua e đã tin tưởng bác sử dụng chung 1 template nên mới cầu cứu mà
class Solution {
public:
long long countFairPairs(vector<int>& nums, int lower, int upper) {
int n = nums.size();
sort(nums.begin(), nums.end());
long long ans = 0;
for (int i = 0; i <= n - 2; i++) {
ans += countPairsInRange(nums, i + 1, nums[i], lower, upper);
}
return ans;
}
int countPairsInRange(std::vector<int>& nums, int indexStart, int currentNumber, int lower, int upper) {
int indexLower = findLowerBound(nums, indexStart, currentNumber, lower);
int indexUpper = findUpperBound(nums, indexStart, currentNumber, upper);
if (indexLower <= indexUpper && indexUpper < nums.size()) {
return indexUpper - indexLower + 1;
}
return 0;
}
int findLowerBound(std::vector<int>& nums, int indexStart, int currentNumber, int lower) {
int left = indexStart;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (currentNumber + nums[mid] < lower) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
int findUpperBound(std::vector<int>& nums, int indexStart, int currentNumber, int upper) {
int left = indexStart;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (currentNumber + nums[mid] <= upper) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
};class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
nums.sort()
result, n = 0, len(nums)
def lowerBound(target):
count, left, right = 0, 0, n - 1
while left < right:
if nums[left] + nums[right] < target:
count += right - left
left += 1
continue
right -= 1
return count
return lowerBound(upper + 1) - lowerBound(lower)chỉ có mode light hay dark hay system thôi, voz theme cũ nhìn quen mắt, qua cái theme này khó chịu vl
class Solution {
public long countFairPairs(int[] nums, int lower, int upper) {
int n = nums.length;
long answer = 0;
for (int i = 0; i < n; i++) {
int low = lower - nums[i];
int high = upper - nums[i];
int lowIdx = upperBoundEqual(i + 1, n - 1, nums, low);
int highIdx = lowerBoundEqual(i + 1, n - 1, nums, high);
if (lowIdx != -1 && highIdx != -1) {
answer += (highIdx - lowIdx + 1);
}
}
return answer;
}
public int lowerBoundEqual(int start, int end, int[] nums, int value) {
int lastIndex = -1;
while (start <= end) {
int mid = (start + end) / 2;
if (nums[mid] <= value) {
lastIndex = mid;
start = mid + 1;
} else {
end = mid - 1;
}
}
return lastIndex;
}
public int upperBoundEqual(int start, int end, int[] nums, int value) {
int lastIndex = -1;
while (start <= end) {
int mid = (start + end) / 2;
if (nums[mid] >= value) {
lastIndex = mid;
end = mid - 1;
} else {
start = mid + 1;
}
}
return lastIndex;
}
}
function countFairPairs(nums: number[], lower: number, upper: number): number {
const n = nums.length
nums.sort((a, b) => a - b);
let res = 0;
const lowerBound = (i: number) => {
let l = i + 1, r = n - 1
while (l <= r) {
const m = l + Math.floor((r - l) / 2);
if (nums[i] + nums[m] >= lower) r = m - 1
else l = m + 1;
}
return l;
}
const upperBound = (i: number) => {
let l = i + 1, r = n - 1;
while (l <= r) {
const m = l + Math.floor((r - l) / 2);
if (nums[i] + nums[m] <= upper) l = m + 1;
else r = m - 1;
}
return r;
}
for (let i = 0; i < n; i++) {
const lb = lowerBound(i), ub = upperBound(i);
res+= ub - lb >= 0 ? ub - lb + 1 : 0
}
return res;
};
