[Hackerearth] Curious Queries

 

Problem Link    : Curious Queries
Category        : Merge Sort Tree
Contest         : December Circuits'23  

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
using pii = pair<int, int>;
 
const int maxn = 1e5 + 5;
 
struct MergesortTree {
    vector<pii> store;
    MergesortTree() {
        store.clear();
    }
 
    void assignLeaf(int val) {
        store.clear();
        store.push_back({val, val});
    }
    void marge(const MergesortTree &lchild, const MergesortTree &rchild) {
        int i = 0;
        int j = 0;
        store.clear();
        while (i < lchild.store.size() and j < rchild.store.size()) {
            if (lchild.store[i].first < rchild.store[j].first) {
                int sum = lchild.store[i].first + (store.size() ? store.back().second : 0);
                store.emplace_back(lchild.store[i].first, sum);
                i++;
            } else {
                int sum = rchild.store[j].first + (store.size() ? store.back().second : 0);
                store.emplace_back(rchild.store[j].first, sum);
                j++;
            }
        }
        while (i < lchild.store.size()) {
            int sum = lchild.store[i].first + (store.size() ? store.back().second : 0);
            store.emplace_back(lchild.store[i].first, sum);
            i++;
        }
        while (j < rchild.store.size()) {
            int sum = rchild.store[j].first + (store.size() ? store.back().second : 0);
            store.emplace_back(rchild.store[j].first, sum);
            j++;
        }
    }
    int getSum(int limit) {
        int id = upper_bound(store.begin(), store.end(), pii(limit, INT_MAX)) - store.begin();
        if (id == store.size()) {
            return 0;
        }
        int sum = store.back().second - (id - 1 >= 0 ? store[id - 1].second : 0);
        return sum;
    }
} Tree[maxn * 4];
 
int n;
int q;
int arr[maxn];
 
void build(int node, int a, int b) {
    if (a == b) {
        Tree[node].assignLeaf(arr[a]);
        return;
    }
    int lchild = node * 2;
    int rchild = node * 2 + 1;
    int mid = (a + b) / 2;
    build(lchild, a, mid);
    build(rchild, mid + 1, b);
    Tree[node].marge(Tree[lchild], Tree[rchild]);
}
 
int query(int node, int a, int b, int i, int j, int limit) {
    if (a > b or a > j or b < i) {
        return 0;
    }
    if (a >= i and b <= j) {
        return Tree[node].getSum(limit);
    }
    int lchild = node * 2;
    int rchild = node * 2 + 1;
    int mid = (a + b) / 2;
    int p = query(lchild, a, mid, i, j, limit);
    int q = query(rchild, mid + 1, b, i, j, limit);
    return p + q;
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("F2.txt", "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        cin >> n >> q;
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        build(1, 1, n);
        for (int i = 1; i <= q; i++) {
            int l, r;
            cin >> l >> r;
            l++;
            r++;
            int limit = arr[r];
            int ans = query(1, 1, n, 1, l, limit);
            cout << ans << " \n"[i == q];
        }
    }
}