Ash_Blanc's blog

By Ash_Blanc, history, 11 minutes ago, In English

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;
}
  • Vote: I like it
  • -1
  • Vote: I do not like it