---
tags: codebook
---

{%hackmd theme-dark %}

# priority LIS

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

template<typename T>
struct segment_tree{
    const T limit;
    const size_t _size;
    vector<T> vec;
    const T& (*cmp)(const T&,const T&);
	const T operator[](size_t pos){return vec[pos+_size];}
    const T operator()(size_t l,size_t r){
        if(l==r) return 0;
        if(l>r) swap(l,r);
        l+=_size,r+=_size;
        T ans=limit;
        while(l<r){
            if(l&1) ans=cmp(ans,vec[l++]);
            if(r&1) ans=cmp(ans,vec[--r]);
            l>>=1,r>>=1;
        }
        return ans;
    }
    void update(size_t pos,T x){
        pos+=_size,vec[pos]=x;
        while(pos!=1)vec[pos>>1]=cmp(vec[pos>>1],vec[pos]),pos>>=1;
    }
    segment_tree(const vector<T>& v,const T& (*c)(const T&,const T&)=
    [](const auto& a,const auto& b)->const decltype(a){return (a<b?a:b);}):
    limit((c(1,0)?numeric_limits<T>::min():numeric_limits<T>::max())),
    _size(v.size()),vec(_size<<1),cmp(c){
        for(size_t i=0;i!=_size;i++)
            vec[_size+i]=v[i];
        for(size_t i=_size-1;i;i--)
            vec[i]=cmp(vec[i<<1],vec[(i<<1)+1]);
    }
};
long long priority_LIS(vector<pair<int,int>>& vec){
	segment_tree<long long> tree(vector<long long>([&](){
		auto arr(vec); 
		sort(arr.begin(),arr.end(),[](const auto& a,const auto& b){return a.first<b.first;});
		arr.resize(unique(arr.begin(),arr.end(),[](const auto& a,const auto& b){
			return a.first==b.first;
		})-arr.begin());
		for(auto& i:vec) i.first=lower_bound(arr.begin(),arr.end(),i,[](const auto& a,const auto& b){
			return a.first<b.first;
		})-arr.begin();
		return arr.size();
	}(),0),[](const auto& a,const auto& b)->const decltype(a){return (a>b?a:b);});
	for(const auto& i:vec)
		tree.update(i.first,max(tree[i.first],tree(0,i.first)+i.second));
	return tree(0,tree._size);
}