CSES - List Removals

Solution 1

Use a rope.

Copy
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;

using ll = long long;
using ld = long double;
using db = double;
using str = string;  // yay python!

Solution 2

Use an indexed set.

Copy
#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 3

Binary search on a BIT.

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

using ll = long long;
using ld = long double;
using db = double;
using str = string;  // yay python!

using pi = pair<int, int>;
using pl = pair<ll, ll>;

Solution 4

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

Copy
#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;