CSES - List Removals

Solution 1

Use a rope.

#include <ext/rope>
#include <bits/stdc++.h>
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.

Implementation without template

#include <bits/stdc++.h>
 
using namespace std;
 
#include <ext/pb_ds/tree_policy.hpp>
#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>;
 

Implementation with template

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

Binary search on a BIT.

#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

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

struct node;

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

vector<int> results;