Competitive-Coding-Library/Order_Statistics_Tree_Template.cpp at master · vicennial/Competitive-Coding-Library · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//Gvs Akhil (Vicennial)
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#defineintlonglong
#definepb push_back
#defineeb emplace_back
#definemp make_pair
#definemt make_tuple
#defineld(a) while(a--)
#definetci(v,i) for(auto i=v.begin();i!=v.end();i++)
#definetcf(v,i) for(auto i : v)
#defineall(v) v.begin(),v.end()
#definerep(i,start,lim) for(longlong (i)=(start);i<(lim);i++)
#definesyncios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#defineosit ostream_iterator
#defineINF0x3f3f3f3f
#defineLLINF1000111000111000111LL
#definePI3.14159265358979323
#defineendl'\n'
#definetrace1(x) cerr<<#x<<": "<<x<<endl
#definetrace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#definetrace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#definetrace4(a, b, c, d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#definetrace5(a, b, c, d, e) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#definetrace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
constint N=1000006;
usingnamespacestd;
usingnamespace__gnu_pbds;// inc this
typedef vector<int> vi;
typedef vector<vi> vvi;
typedeflonglong ll;
typedef vector<longlong> vll;
typedef vector<vll> vvll;
typedeflongdouble ld;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef tuple<int,int,int> iii;
typedef set<int> si;
typedefcomplex<double> pnt;
typedef vector<pnt> vpnt;
typedef priority_queue<ii,vii,greater<ii> > spq;
const ll MOD=1000000007LL;
template<typename T> T gcd(T a,T b){if(a==0) return b; returngcd(b%a,a);}
template<typename T> T power(T x,T y,ll m=MOD){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> order_set;
order_set x;
int32_tmain(){
	x.insert(5);
	x.insert(5);
// x.erase(5);
	cout<<x.order_of_key(5)<<endl;
	cout<<x.order_of_key(6)<<endl; // strictly lesser
	cout<<*x.find_by_order(6)<<endl; // kth index, starts from zero index, acsending
}