Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間7月前 (2025/04/23 01:21)推噓0(0推 0噓 1→)

2179. 不知道是好幾天前的daily惹拖了好久前面一直以為constraint有 x < y < z 結果只要px < py < pz value不用排順序== 雖然前面那個版本好像也是寫錯就是了 # bit跟total都是BIT 先開一個BIT計前面有幾個再開一個BIT計加起來是多少 long long goodTriplets(vector<int>& nums1, vector<int>& nums2) { int n = nums1.size(); ll res = 0; vector<ll> bit(n+1, 0); vector<ll> total(n+1, 0); vector<int> idx2(n, 0); // val to idx for(int i = 0; i < n; i++){ int val = nums2[i]; idx2[val] = i + 1; // 0-indexed to 1-indexed } for(int i = 0; i < n; i++){ int v = nums1[i]; modify(bit, idx2[v], 1); ll add = search(bit, idx2[v]) - 1; modify(total, idx2[v], add); res += search(total, idx2[v] - 1); } return res; } inline int lowbit(int x){ return x & -x; } void modify(vector<ll>& bit, int pos, int val){ // add val at pos int n = bit.size(); while(pos < n){ bit[pos] += val; pos += lowbit(pos); } } ll search(vector<ll>& bit, int pos){ // return val at pos ll res = 0; while(pos){ res += bit[pos]; pos -= lowbit(pos); } return res; } -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg