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;
}

我快哭了 大師