Just curious if any optimizations in this fenwick merge tree can make it pass the remaining TLEing test case in https://cses.fi/problemset/task/3163/
#include <bits/stdc++.h>
using namespace std;
void setIO() {
cin.tie(0)->sync_with_stdio(0);
}
class FenwickMergeTree {
public:
int n;
vector<vector<int>> tree;
FenwickMergeTree(const vector<int> &a) : n(a.size()), tree(n + 1) {
// 1. Distribute elements into responsible Fenwick nodes (1-based)
for (int i = 0; i < n; ++i) {
for (int idx = i + 1; idx <= n; idx += idx & -idx) {
tree[idx].push_back(a[i]);
}
}
// 2. Sort each node's vector once
for (int i = 1; i <= n; ++i) {
sort(tree[i].begin(), tree[i].end());
}
}
// Counts elements strictly less than x in 0-based prefix [0 .. r]
int prefixCountLess(int r, int x) {
int res = 0;
for (int idx = r + 1; idx > 0; idx -= idx & -idx) {
res += lower_bound(tree[idx].begin(), tree[idx].end(), x) - tree[idx].begin();
}
return res;
}
// Counts elements strictly less than x in 0-based range [l .. r]
int countLess(int l, int r, int x) {
return prefixCountLess(r, x) - prefixCountLess(l - 1, x);
}
};
void solve() {
int n, q;
cin >> n >> q;
vector<int> arr(n);
for (int &x : arr) cin >> x;
FenwickMergeTree me(arr);
while (q--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
// Convert 1-based [a, b] to 0-based [a-1, b-1]
int upper = me.countLess(a - 1, b - 1, d + 1);
int lower = me.countLess(a - 1, b - 1, c);
cout << upper - lower << '\n';
}
}
int32_t main() {
setIO();
solve();
return 0;
}







