Solution 1

Use an indexed set.

C++

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


#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;


template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

Solution 2

Binary search on a BIT.

C++

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


constexpr int bits(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }


/**
 * Description: range sum queries and point updates for $D$ dimensions
 * Source: https://codeforces.com/blog/entry/64914
 * Verification: SPOJ matsum
 * Usage: \texttt{BIT<int,10,10>} gives 2D BIT

Solution 3

Use a segment tree to store the number of elements present in each segment and walk down it

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;


struct node;


vector<int> information;  // stores the actual array with our data in


vector<int> results;

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