Solution 1

As mentioned in the module, you can apply coordinate compression before using a segment tree or a BIT.

Stick with arrays (or vectors) whenever possible; using a map instead may TLE.

Implementation

Time Complexity: O((N+Q)log⁡(N+Q))\mathcal{O}((N + Q) \log(N + Q))

import java.io.*;
import java.util.*;


// Utilizing the Fact that Total Unique Number of Salaries Including the Queries and
// Input Array is no more than n (2e5) + 2 * q (2e5) which is 6*10^5.


// So we don't have to worry about salary in range 1e9, we will compress it.


public class Salary_Queries {
	static Reader fr = new Reader();

Here is a similar solution with a map that passes slightly under the time limit.

Time Complexity: O((N+Q)log⁡(N+Q))\mathcal{O}((N + Q) \log(N + Q))

#include <bits/stdc++.h>
using namespace std;


 Code Snippet: Binary Indexed Tree (from the module) (Click to expand)


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);


	int n, q;

Solution 2

Just use indexed set!

Time Complexity: O((N+Q)log⁡N)\mathcal{O}((N + Q) \log N)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>


using namespace std;
using namespace __gnu_pbds;


typedef pair<int, int> pii;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum