树状数组（二维偏序）

题目链接

https://leetcode.cn/problems/maximum-sum-queries/description/

题目大意

题目思路

二维偏序问题 -> 一维排序，一维树状数组！

题目代码

class Solution {
public:int sz;vector<int> tr;int lowbit(int x){return x & -x;}void update(int x,int k){for(int i = x;i <= sz;i += lowbit(i))tr[i] = max(tr[i],k);}int query(int x){int ans = -1;for(int i = x;i;i -= lowbit(i)) ans = max(ans,tr[i]);return ans;}vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {int n = nums1.size(),m = queries.size();vector<array<int,2>> nums(n);for(int i = 0;i < n;++i) nums[i] = {nums1[i],nums2[i]};vector<array<int,3>> q(m);for(int i = 0;i < m;++i) q[i] = {queries[i][0],queries[i][1],i};// 离散化unordered_set<int> s;for(auto x:nums) s.insert(x[1]);for(auto x:q)    s.insert(x[1]);vector<int> list(s.begin(),s.end());sort(list.begin(),list.end());sz = list.size();map<int,int> mp;for(int i = 0;i < sz;++i) mp[list[i]] = i;// 一维排序sort(nums.begin(),nums.end(),[](const auto& a,const auto& b){return a[0] > b[0];});sort(q.begin(),q.end(),[](const auto& a,const auto& b){return a[0] > b[0];});tr.resize(sz + 10,-1);vector<int> ans(m);int idx = 0;for(auto qy:q){int x = qy[0],y = qy[1],i = qy[2];while(idx < n && nums[idx][0] >= x){update(sz - mp[nums[idx][1]],nums[idx][0] + nums[idx][1]);++idx;}ans[i] = query(sz - mp[y]);}return ans;}
};