[C++] 2 Segment Tree Easy to understand
Code\n\nvoid update(vector<long long> &seg, int start, int end, int pos, int node, long long val){\n    if(start > pos || end < pos){\n        return;\n    }\n 
# Code\n```\nvoid update(vector<long long> &seg, int start, int end, int pos, int node, long long val){\n    if(start > pos || end < pos){\n        return;\n    }\n    if(start == end){\n        seg[node] += val;\n        return;\n    }\n    int mid = (start+end)/2;\n    \n    update(seg, start, mid, pos, node*2+1, val);\n    update(seg, mid+1, end, pos, node*2+2, val);\n    \n    seg[node] = seg[node*2+1] + seg[node*2+2];\n}\n\nlong long get(vector<long long> &seg, int start, int end, int left, int right, int node){\n    if(start > right || end < left){\n        return 0;\n    }\n    if(left <= start && end <= right){\n        return seg[node];\n    }\n    \n    int mid = (start+end)/2;\n    return get(seg, start, mid, left, right, node*2+1) + get(seg, mid+1, end, left, right, node*2+2);\n}\nclass Solution {\npublic:\n    long long findMaximumElegance(vector<vector<int>>& items, int k) {\n        int n = items.size();\n        \n        sort(items.begin(), items.end(), [](vector<int> &a, vector<int> &b){\n            return a[0] > b[0];\n        });\n        \n        unordered_map<int, pair<int, int>> maxx;\n        \n        for(int i=0; i<n; i++){\n            if(maxx.find(items[i][1]) == maxx.end() || maxx[items[i][1]].first < items[i][0]){\n                maxx[items[i][1]] = {items[i][0], i};\n            }\n        }\n        \n        vector<long long> prefix(n, 0);\n        \n        prefix[0] = items[0][0];\n        \n        for(int i=1; i<n; i++){\n            prefix[i] = prefix[i-1] + items[i][0];\n        }\n        \n        vector<long long> seg1(4*n, 0);\n        vector<long long> seg(4*n, 0);\n        \n        vector<vector<int>> max_cate;\n        \n        for(auto cate : maxx){\n            max_cate.push_back({cate.first, cate.second.first, cate.second.second});\n        }\n        \n        sort(max_cate.begin(), max_cate.end(), [](vector<int> &a, vector<int> &b){\n            return a[1] > b[1];\n        });\n        \n        long long res = 0;\n        \n        for(int i=0; i<max_cate.size(); i++){\n            update(seg, 0, n-1, max_cate[i][2], 0, 1);\n            update(seg1, 0, n-1, max_cate[i][2], 0, max_cate[i][1]);\n            \n        \n            int low = -1; \n            int high = n - 1;\n            \n            while(low <= high){\n                int mid = (low+high)/2;\n                if(get(seg, 0, n-1, mid+1, n-1, 0) + mid + 1 <= k){\n                    low = mid+1;\n                }\n                else{\n                    high = mid-1;\n                }\n            }\n            \n            if(low == -1){\n                continue;\n            }\n            if(low - 1 < 0){\n                res = max(res, 1LL*(get(seg1, 0, n-1, low, n-1, 0) + 1LL*(i+1)*(i+1)));\n            }\n            else{\n                res = max(res, 1LL*(get(seg1, 0, n-1, low, n-1, 0) + prefix[low-1] + 1LL*(i+1)*(i+1)));\n            }\n            \n        }\n        return res;\n    }\n};\n```
['C++']