#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using namespace std ;
#define int int64_t //be careful about this
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)
#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))
template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<typename T>
void __p(T a) {
cout<<a;
}
template<typename T, typename F>
void __p(pair<T, F> a) {
cout<<"{";
__p(a.first);
cout<<",";
__p(a.second);
cout<<"}\n";
}
template<typename T>
void __p(std::vector<T> a) {
cout<<"{";
for(auto it=a.begin(); it<a.end(); it++)
__p(*it),cout<<",}\n"[it+1==a.end()];
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
__p(a1);
__p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
cout<<name<<" : ";
__p(arg1);
cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
int bracket=0,i=0;
for(;; i++)
if(names[i]==','&&bracket==0)
break;
else if(names[i]=='(')
bracket++;
else if(names[i]==')')
bracket--;
const char *comma=names+i;
cout.write(names,comma-names)<<" : ";
__p(arg1);
cout<<" | ";
__f(comma+1,args...);
}
void setIO(string s = "") {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin.exceptions(cin.failbit);
cout.precision(15); cout << fixed;
#ifdef ONLINE_JUDGE
if(sz(s)){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
#define __f(...) 0
#endif
}
/*
* Treaps Implementation
* prior is priority which gives heap property
* key gives BST property
* size is size of our tree
* sum is sum of our subtree
* lazy is lazy value
* val is value stored at that node
* source:
https://tanujkhattar.wordpress.com/2016/01/10/treaps-one-tree-to-rule-em-all-part-2/
https://www.codechef.com/viewsolution/36079099
* verification:
https://www.spoj.com/status/HORRIBLE,deepkamal/
*/
// currently not considering reverse
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(){
return uniform_int_distribution<int>(0,1e9)(rng) ;
}
struct node{
int prior, size, val, sum, lazy, key;
//bool rev ;
node *l, *r;
node ():l(nullptr) , r(nullptr) {}
};
node* newnode(int k,int _val){
node *ret ; ret = new node();
ret->key = k ;
ret->val = ret->sum = _val;
ret->lazy = 0 ;
ret->size = 1 ;
ret->prior = Random() ;
return ret ;
}
typedef node* pnode;
struct IMPLICIT_TREAP {
node *tree;
IMPLICIT_TREAP(): tree (nullptr) { }
int SZ(pnode t){
return t ? t->size : 0 ;
}
void upd_sz(pnode t){
if(t){ t->size = SZ(t->l) + 1 + SZ(t->r); }
}
void combine(pnode& t,pnode l,pnode r){//combine segtree ranges
t->sum = 0 ;
if(l) t->sum += l->sum ;
if(r) t->sum += r->sum;
}
void propagate(pnode t){
if(!t or !t->lazy) return ; // here this implementation is for sum so t->lazy != 0
t->val += t->lazy ; //operation of lazy
t->sum += t->lazy * SZ(t) ;
if(t->l) t->l->lazy += t->lazy ; //propagate lazy for t's children
if(t->r) t->r->lazy += t->lazy ;
t->lazy = 0;
}
void reset(pnode t){
if(t) t->sum = t->val;//lazy already propagated
}
void operation(pnode t){//operation of segtree
if(!t) return ;
reset(t) ; // node represents single element of array
propagate(t->l) ; propagate(t->r) ;//imp:propagate lazy before combining l,r
combine(t,t->l,t->r) ; t->sum += t->val ;
}
void split(pnode t,pnode &l,pnode &r,int pos,int add = 0){ // add keeps track of the i value
if(!t){ l = r = NULL ; return ; }
propagate(t) ;
int curr_pos = add + SZ(t->l);
if(curr_pos <= pos){//element at pos goes to "l"
split(t->r, t->r, r, pos, curr_pos+1); l = t;
}else{
split(t->l, l, t->l, pos, add); r = t;
}
upd_sz(t) ; operation(t) ;
}
void merge(pnode &t,pnode l,pnode r){//result/left/right array
propagate(l) ; propagate(r) ;
if(!l or !r){
t = l?l:r;
}else if(l->prior > r->prior) {
merge(l->r,l->r,r); t = l;
}else{
merge(r->l,l,r->l); t = r;
}
upd_sz(t) ; operation(t) ;
}
void insert(int pos,int _val){
pnode r = newnode(pos,_val);
pnode a, b, c;
split(tree, a, b, pos-1) ;
merge(c, a, r);
merge(tree, c, b);
}
void del(int pos){
pnode a, b, c;
split(tree, a, c, pos);
split(a, a, b, pos-1);
merge(tree, a, c);
}
int get(int pos){
pnode a, b, c;
split(tree, a, c, pos) ; split(a, a, b, pos-1) ;
merge(a, a, b) ; merge(tree, a, c) ;
return b->val ;
}
void range_update(pnode t,int l,int r,int val){ //[l,r]
pnode a, b, c;
split(t, b, c, r) ; split(b, a, b, l-1) ;
b->lazy += val;
merge(b,a,b) ; merge(t,b,c) ;
}
int range_query(pnode t,int l,int r){//[l,r]
pnode a, b, c;
split(t,a,c,r) ; split(a,a,b,l-1) ;
int ans = b->sum ;
merge(a,a,b) ; merge(t,a,c) ;
return ans;
}
};
struct compress_1d_co_ordinates {
vector<int> values;
void add(int x){
values.push_back(x);
}
void gen(){
sort(values.begin(),values.end());
values.erase(unique(values.begin(),values.end()),values.end());
}
int get(int x){
int j = lower_bound(values.begin(),values.end(),x) - values.begin();
assert(values[j] == x); return j;
}
}C;
signed main(){
setIO() ;
int n,q; rd(n,q);
vt<int> a(n);
rd(a);
for(auto i : a) C.add(i);
vt<pr<int,int>> queries;
while(q--){
int i,x; rd(i,x);
queries.eb(i,x);
C.add(x);
}
C.gen();
for(auto& i : a) i = C.get(i);
for(auto [i,x]:queries) x = C.get(x);
}
Compilation message
bubblesort2.cpp:8:40: error: 'less' was not declared in this scope; did you mean 'std::less'?
8 | using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
| ^~~~
| std::less
In file included from /usr/include/c++/10/string:48,
from /usr/include/c++/10/bits/locale_classes.h:40,
from /usr/include/c++/10/bits/ios_base.h:41,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from bubblesort2.cpp:1:
/usr/include/c++/10/bits/stl_function.h:340:12: note: 'std::less' declared here
340 | struct less;
| ^~~~
bubblesort2.cpp:8:46: error: template argument 3 is invalid
8 | using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
| ^
