Problem:
 Score : 100 points    Problem Statement There are N flowers arranged in a row.
For each i ( 1 \leq i \leq N ), the height and the beauty of the i -th flower from the left is h_i and a_i , respectively.
Here, h_1, h_2, \ldots, h_N are all distinct.  Taro is pulling out some flowers so that the following condition is met:   The heights of the remaining flowers are monotonically increasing from left to right.   Find the maximum possible sum of the beauties of the remaining flowers.      Constraints  All values in input are integers.  1 \leq N \leq 2 × 10^5  1 \leq h_i \leq N  h_1, h_2, \ldots, h_N are all distinct.  1 \leq a_i \leq 10^9         Input Input is given from Standard Input in the following format:  N  h_1  h_2  \ldots  h_N  a_1  a_2  \ldots  a_N       Output Print the maximum possible sum of the beauties of the remaining flowers.        Sample Input 1 4
3 1 4 2
10 20 30 40      Sample Output 1 60  We should keep the second and fourth flowers from the left.
Then, the heights would be 1, 2 from left to right, which is monotonically increasing, and the sum of the beauties would be 20 + 40 = 60 .       Sample Input 2 1
1
10      Sample Output 2 10  The condition is met already at the beginning.       Sample Input 3 5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000      Sample Output 3 5000000000  The answer may not fit into a 32-bit integer type.       Sample Input 4 9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5      Sample Output 4 31  We should keep the second, third, sixth, eighth and ninth flowers from the left.

Solution (Python):


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  
from itertools import combinations as comb  
from itertools import permutations as permutate
from bisect import bisect_left as bl



from bisect import bisect_right as br
from bisect import bisect







BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None


    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)





from types import GeneratorType


def iterative(f, stack=[]):
    def wrapped_func(*args, **kwargs):
        if stack: return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
                continue
            stack.pop()
            if not stack: break
            to = stack[-1].send(to)
        return to

    return wrapped_func







mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  

def out(var): sys.stdout.write(str(var))  

def lis(): return list(map(int, inp().split()))

def stringlis(): return list(map(str, inp().split()))

def sep(): return map(int, inp().split())

def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n

def nextline(): out("\n")  

def testcase(t):
    for p in range(t):
        solve()

def printlist(a):
    for p in range(0, len(a)):
        out(str(a[p]) + ' ')



def solve():
    class SegmentTree:
        def __init__(self, data, default=0, func=max):
            """initialize the segment tree with data"""
            self._default = default
            self._func = func
            self._len = len(data)
            self._size = _size = 1 << (self._len - 1).bit_length()

            self.data = [default] * (_size) + data + [default] * (_size - self._len)
            for i in range(_size - 1, -1, -1):
                self.data[i] = func(self.data[2 * i], self.data[2 * i + 1])

        def __delitem__(self, idx):
            self[idx] = self._default

        def __getitem__(self, idx):
            return self.data[idx + self._size]

        def __setitem__(self, idx, value):
            idx += self._size
            self.data[idx] = value
            idx >>= 1
            while idx:
                self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
                idx >>= 1

        def __len__(self):
            return self._len

        def query(self, start, stop):
            """func of data[start, stop)"""
            start += self._size
            stop += self._size

            res_left = res_right = self._default
            while start < stop:
                if start & 1:
                    res_left = self._func(res_left, self.data[start])
                    start += 1
                if stop & 1:
                    stop -= 1
                    res_right = self._func(self.data[stop], res_right)
                start >>= 1
                stop >>= 1

            return self._func(res_left, res_right)

        def __repr__(self):
            return "SegmentTree({0})".format(self.data)


    n=int(inp())
    h=lis()
    b=lis()
    dp=[0]*(n+5)
    s=SegmentTree(dp,default=0,func=max)
    for i in range(n):
        dp[h[i]]=s.query(1,h[i])+b[i]
        s[h[i]]=dp[h[i]]
    
    print(max(dp))















solve()

Solution (Python):
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



n = val()
h = li()
v = li()

class Node:
    def __init__(self,s,e):
        self.start=s
        self.end=e
        self.val = 0
        self.left=None
        self.right=None
 
def build(nums,l,r):
    if l == r:
        temp = Node(l,l)
        temp.val = nums[l]
    else:
        mid=(l+r)>>1
        temp=Node(l,r)
        temp.left=build(nums,l,mid)
        temp.right=build(nums,mid+1,r)
        temp.val = max(temp.left.val,temp.right.val)
    return temp

def update(root,start,value):
    if root.start == start == root.end:
        root.val = value
    elif root.start <= start and root.end >= start:
        update(root.left,start,value)
        update(root.right,start,value)
        root.val = max(root.left.val,root.right.val)





def query(root,start,end):
    if root.start>=start and root.end<=end:return root.val
    elif root.start>end or root.end<start:return -float('inf')
    else:
        temp1 = query(root.left,start,end)
        temp2 = query(root.right,start,end)
        return max(temp1,temp2)
        


ans = 0

root = build([0] * (n + 1), 0, n)
for i in range(n):
    curr = query(root, 0, h[i] - 1)
    ans = max(ans, curr + v[i])
    update(root, h[i], curr + v[i])

print(ans)

Solution (Python):


import os,sys
from io import BytesIO, IOBase
from collections import deque

def update(seg_tree,val,update_val,x):
    curr = deque([(1,x,1)])
    while len(curr):
        y = curr.popleft()
        if y[0]<=val<=y[1]:
            seg_tree[y[2]] = max(seg_tree[y[2]],update_val)
            if y[0]!=y[1]:
                curr.append((y[0],(y[0]+y[1])//2,2*y[2]))
                curr.append(((y[0]+y[1])//2+1,y[1],2*y[2]+1))

def trav(seg_tree,val,x):
    curr = deque([(1,x,1)])
    ans = 0
    while len(curr):
        y = curr.popleft()
        if y[1]<val:
            ans = max(ans,seg_tree[y[2]])
        elif y[0]<=val<=y[1] and y[0]!=y[1]:
            curr.append((y[0],(y[0]+y[1])//2,2*y[2]))
            curr.append(((y[0]+y[1])//2+1,y[1],2*y[2]+1))
    return ans

def main():
    n = int(input())
    h = list(map(int,input().split()))
    a = list(map(int,input().split()))
    x = 1<<n.bit_length()
    seg_tree = [0]*(x<<1)
    fin = 0
    for i in range(n):
        k = trav(seg_tree,h[i],x)
        fin = max(fin,a[i]+k)
        update(seg_tree,h[i],a[i]+k,x)
    print(fin)


BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



class Node:
    def __init__(self,s,e):
        self.start=s
        self.end=e
        self.val = 0
        self.left=None
        self.right=None
 
def build(nums,l,r):
    if l == r:
        temp = Node(l,l)
        temp.val = nums[l]
    else:
        mid=(l+r)>>1
        temp=Node(l,r)
        temp.left=build(nums,l,mid)
        temp.right=build(nums,mid+1,r)
        temp.val = max(temp.left.val,temp.right.val)
    return temp

def update(root,start,value):
    if root.start == start == root.end:
        root.val = value
    elif root.start <= start and root.end >= start:
        update(root.left,start,value)
        update(root.right,start,value)
        root.val = max(root.left.val,root.right.val)





def query(root,start,end):
    if root.start>=start and root.end<=end:return root.val
    elif root.start>end or root.end<start:return -float('inf')
    else:
        temp1 = query(root.left,start,end)
        temp2 = query(root.right,start,end)
        return max(temp1,temp2)
        

    

N = val()
height = li()
beauty = li()

fenwick = build([0] * (N + 1), 0, N)


ans = 0

for i in range(N):
    curr = beauty[i] + query(fenwick, 0, height[i])
    ans = max(ans, curr)
    update(fenwick, height[i], curr)

print(ans)

Solution (Python):
N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
size = 2**N.bit_length()
seg = [0 for i in range(2*size + 1)]

def update(i, x):
  i += size
  seg[i] = x
  while 1 < i:
    i >>= 1
    seg[i] = max(seg[i<<1|0], seg[i<<1|1])

def query_(a, b, k, l, r):
  ret = 0

  a += size
  b += size
  while a < b:
    if b & 1:
      b -= 1
      ret = max(ret, seg[b])

    if a & 1:
      ret = max(ret, seg[a])
      a += 1

    a >>= 1
    b >>= 1

  return ret


def query(a, b):
  return query_(a, b, 1, 0, N)

for i in range(N):
  temp = query(0, H[i])
  update(H[i], temp+A[i])

print(query(0, N+1))

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        t = self.one
        while l < r:
            if l & 1:
                s = self.func(s, self.b[l - 1])
                l += 1
            if r & 1:
                r -= 1
                t = self.func(self.b[r - 1], t)
            l >>= 1
            r >>= 1
        return self.func(s, t)


seg = SegmentTree([0]*(n+1))

for i in range(n):
    j = seg.get_segment(0, h[i] + 1)
    seg.update_func(h[i], j + a[i])
print(seg.get_segment(0, n+1))

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


sellogn = []
seln = 0
selfunc = max
selone = 0
selb = []


def __init__(a, func=max, one=-10 ** 18):
    global sellogn, seln, selfunc, selone, selb
    sellogn = (len(a) - 1).bit_length()
    seln = 1 << sellogn
    selfunc = func
    selone = one

    selb = [selone] * (2 * seln - 1)
    for i, j in enumerate(a):
        selb[i + seln - 1] = j
    for i in reversed(range(seln - 1)):
        selb[i] = selfunc(selb[i * 2 + 1], selb[i * 2 + 2])


def get_item(i):
    global sellogn, seln, selfunc, selone, selb
    return selb[i + seln - 1]


def update(index, x):
    global sellogn, seln, selfunc, selone, selb
    i = index + seln - 1
    selb[i] = x
    while i != 0:
        i = (i - 1) // 2
        selb[i] = selfunc(selb[i * 2 + 1], selb[i * 2 + 2])


def update_func(index, x):
    global sellogn, seln, selfunc, selone, selb
    i = index + seln - 1
    selb[i] = selfunc(selb[i], x)
    while i != 0:
        i = (i - 1) // 2
        selb[i] = selfunc(selb[i * 2 + 1], selb[i * 2 + 2])


def get_segment(l, r):
    global sellogn, seln, selfunc, selone, selb
    l += seln
    r += seln
    s = selone
    t = selone
    while l < r:
        if l & 1:
            s = selfunc(s, selb[l - 1])
            l += 1
        if r & 1:
            r -= 1
            t = selfunc(selb[r - 1], t)
        l >>= 1
        r >>= 1
    return selfunc(s, t)


__init__([0]*(n+1))

for i in range(n):
    j = get_segment(0, h[i] + 1)
    update_func(h[i], j + a[i])
print(get_segment(0, n+1))

Solution (Python):

def segfunc(x,y):
    return max(x,y)

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n=int(input())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
h=list(map(int,input().split()))
a=list(map(int,input().split()))
dp=[0]*n
init(dp)
ans=0
for i in range(n):
    tmp=query(0,h[i])
    update(h[i]-1,tmp+a[i])

ans=query(0,n)
print(ans)

Solution (Python):










import bisect

class SegTree:
	"""
	1-indexed
	"""
	def __init__(self,size,func,init_val,undef):
		self.specSize = size
		self.datSize = 1
		self.compareFunc = func		
		self.INIT_VAL = init_val	
		self.UNDEFINED_VAL = undef	
		
		
		self.datSize = 2**size.bit_length()
		

		
		
		self.datTree = [self.INIT_VAL for _ in range(2*self.datSize+1)]

	def update(self, i, val ):
		"""
		i: index(1-ordered)
		"""
		
		
		i += self.datSize
		
		self.datTree[i] = val
		while 1 < i:
			
			i >>= 1
			self.datTree[i] = self.compareFunc( self.datTree[i<<1|0], self.datTree[i<<1|1] )
			
			

	def query(self,a,b):
		return self.query_(a,b,1,0,self.datSize)

	def query_(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		all 1-indexed
		i is the root vertex of search 
		l,r is range of the root vertex(not use)
		"""
		ret = self.UNDEFINED_VAL

		a += self.datSize
		b += self.datSize
		while a < b:
			if b & 1:
				b -= 1
				ret = self.compareFunc(ret, self.datTree[b])

			if a & 1:
				ret = self.compareFunc(ret, self.datTree[a])
				a += 1

			a >>= 1; b >>= 1

		return ret
	def query_recursive(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		all 1-indexed
		i is the root vertex of search 
		l,r is range of the root vertex
		"""
		if r <= a or b <= l:
			
			return self.UNDEFINED_VAL

		if a <= l and r <= b:
			
			return self.datTree[i]
		else:
			
			m = (l+r) >> 1 
			
			
			vl = self.query_(a, b, (i>>1) + 1, l, m )
			vr = self.query_(a, b, (i>>1) + 2, m, r )
			return self.compareFunc(vl,vr)

	def printTree(self):
		print(self.datTree)
		



def LongestIncreaseSeaquence(H,A):
	
	
	N = len(H)
	
	lis = 0

	
	
	tree = SegTree(N,max,0,-1e18)
	for n in range(N):

		

		maxValOfCurrentRange = tree.query(0,H[n])
		

		

		
		
		
		tree.update( H[n], maxValOfCurrentRange + A[n] )

	
	lis = tree.query(0,N+1)
	return lis


def main():
	N = int(input())
	
	H = list(map(int, input().split()))
	A = list(map(int, input().split()))
	
	print(LongestIncreaseSeaquence(H,A))



if __name__ == "__main__":
	main()

Solution (Python):
















class BIT:

	def __init__(self,size):
		self.N = size
		self.bit = [0] * (self.N+1)

	def getSum(self,i):
		s = 0
		while 0 < i:
			s += self.bit[i]
			i -= i & -i

		return s

	def getMax(self,i):
		s = 0
		while 0 < i:
			s = max(s, self.bit[i])
			i -= i & -i

		return s

	def add(self,i,val):
		while i <= self.N:
			
			
			
			self.bit[i] = max( self.bit[i], val )
			i += i & -i

def LongestIncreaseSeaquence(H,A):
	
	
	N = len(H)
	
	lis = 0

	
	
	tree = BIT(N)
	for n in range(N):
		tree.add( H[n], tree.getMax(H[n]) + A[n] )

	lis = tree.getMax(N)

	return lis


def main():
	N = int(input())
	
	H = list(map(int, input().split()))
	A = list(map(int, input().split()))
	
	print(LongestIncreaseSeaquence(H,A))



if __name__ == "__main__":
	main()

Solution (Python):
















class BIT:

	def __init__(self,size):
		self.N = size
		self.bit = [0] * (self.N+1)

	def getSum(self,i):
		s = 0
		while 0 < i:
			s += self.bit[i]
			i -= i & -i

		return s

	def getMax(self,i):
		s = 0
		while 0 < i:
			s = max(s, self.bit[i])
			i -= i & -i

		return s

	def add(self,i,val):
		while i <= self.N:
			
			
			
			self.bit[i] = max( self.bit[i], val )
			i += i & -i

def LongestIncreaseSeaquence(H,A):
	
	
	N = len(H)
	
	lis = 0

	
	
	tree = BIT(N)
	for n in range(N):
		tree.add( H[n], tree.getMax(H[n]) + A[n] )

	lis = tree.getMax(N)

	return lis


def main():
	N = int(input())
	
	H = list(map(int, input().split()))
	A = list(map(int, input().split()))
	
	print(LongestIncreaseSeaquence(H,A))



if __name__ == "__main__":
	main()

Solution (Python):















class SegTree:
	def __init__(self,size,func,init_val,undef):
		self.specSize = size
		self.datSize = 1
		self.compareFunc = func		
		self.INIT_VAL = init_val	
		self.UNDEFINED_VAL = undef	
		while self.datSize < size: self.datSize *= 2

		
		self.datTree = [self.INIT_VAL for _ in range(2*self.datSize+1)]
		

	def update(self, i, val ):
		i -= 1	
		i += (self.datSize - 1)
		
		self.datTree[i] = val
		while 0 < i:
			i = (i-1) >> 1	
			self.datTree[i] = self.compareFunc( self.datTree[i*2+1], self.datTree[i*2+2] )
			

	def query(self,a,b):
		return self.query_2(a,b,0,0,self.datSize)

	def query_(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		all 1-indexed
		i is the root vertex of search 
		l,r is range of the root vertex
		"""
		if r <= a or b <= l:
			
			return self.UNDEFINED_VAL

		if a <= l and r <= b:
			
			return self.datTree[i]
		else:
			
			m = (l+r) >> 1 
			
			
			vl = self.query_(a, b, (i << 1) + 1, l, m )
			vr = self.query_(a, b, (i << 1) + 2, m, r )
			return self.compareFunc(vl,vr)

	def query_2(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		all 1-indexed
		i is the root vertex of search 
		l,r is range of the root vertex
		"""
		ret = self.UNDEFINED_VAL

		a += self.datSize
		b += self.datSize
		while a < b:
			if b & 1:
				b -= 1
				ret = self.compareFunc(ret, self.datTree[b-1])

			if a & 1:
				ret = self.compareFunc(ret, self.datTree[a-1])
				a += 1

			a >>= 1; b >>= 1

		return ret
		
		
		

		
		
		
		
		
		
		
		
		
		
		


def LongestIncreaseSeaquence(H,A):
	
	
	N = len(H)
	
	lis = 0

	
	
	tree = SegTree(N,max,0,-1e18)
	for n in range(N):

		

		maxValOfCurrentRange = tree.query(0,H[n])
		

		

		
		
		
		tree.update( H[n], maxValOfCurrentRange + A[n] )

	lis = tree.query(0,N+1)
	return lis


def main():
	N = int(input())
	
	H = list(map(int, input().split()))
	A = list(map(int, input().split()))
	
	print(LongestIncreaseSeaquence(H,A))



if __name__ == "__main__":
	main()

Solution (Python):










import bisect

class SegTree:
	def __init__(self,size,func,init_val,undef):
		self.specSize = size
		self.datSize = 1
		self.compareFunc = func		
		self.INIT_VAL = init_val	
		self.UNDEFINED_VAL = undef	
		while self.datSize < size: self.datSize *= 2

		
		self.datTree = [self.INIT_VAL for _ in range(2*self.datSize+1)]

	def update(self, i, val ):
		i -= 1	
		i += (self.datSize - 1)
		
		self.datTree[i] = val
		while 0 < i:
			i = (i-1) >> 1	
			self.datTree[i] = self.compareFunc( self.datTree[i*2+1], self.datTree[i*2+2] )
			

	def query(self,a,b):
		return self.query_(a,b,0,0,self.datSize)

	def query_(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		all 1-indexed
		i is the root vertex of search 
		l,r is range of the root vertex
		"""
		if r <= a or b <= l:
			
			return self.UNDEFINED_VAL

		if a <= l and r <= b:
			
			return self.datTree[i]
		else:
			
			m = (l+r) >> 1 
			
			
			vl = self.query_(a, b, (i << 1) + 1, l, m )
			vr = self.query_(a, b, (i << 1) + 2, m, r )
			return self.compareFunc(vl,vr)

def LongestIncreaseSeaquence(H,A):
	
	
	N = len(H)
	
	lis = 0

	
	
	tree = SegTree(N,max,0,-1e18)
	for n in range(N):

		

		maxValOfCurrentRange = tree.query(0,H[n])
		

		

		
		
		
		tree.update( H[n], maxValOfCurrentRange + A[n] )

	lis = tree.query(0,N+1)
	return lis


def main():
	N = int(input())
	
	H = list(map(int, input().split()))
	A = list(map(int, input().split()))
	
	print(LongestIncreaseSeaquence(H,A))



if __name__ == "__main__":
	main()

Solution (Python):









import bisect

class SegTree:
	def __init__(self,size,func,init_val,undef):
		self.specSize = size
		self.datSize = 1
		self.compareFunc = func		
		self.INIT_VAL = init_val	
		self.UNDEFINED_VAL = undef	
		while self.datSize < size: self.datSize *= 2

		
		self.datTree = [self.INIT_VAL for _ in range(2*self.datSize+1)]

	def update(self, i, val ):
		i -= 1	
		i += (self.datSize - 1)
		
		self.datTree[i] = val
		while 0 < i:
			i = (i-1)//2
			self.datTree[i] = self.compareFunc( self.datTree[i*2+1], self.datTree[i*2+2] )
			

	def query(self,a,b):
		return self.query_(a,b,0,0,self.datSize)

	def query_(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		i is the root vertex of search 
		l,r is range of the root vertex
		"""
		if r <= a or b <= l:
			
			return self.UNDEFINED_VAL

		if a <= l and r <= b:
			
			return self.datTree[i]
		else:
			
			m = (l+r) // 2
			vl = self.query_(a, b, i*2 + 1, l, m )
			vr = self.query_(a, b, i*2 + 2, m, r )
			return self.compareFunc(vl,vr)

	def debugPrint(self):
		print("=== seg tree debug print start ===")
		print(self.datTree)
		print("== root ==")
		print(self.datTree[0])
		print("== leaf ==")
		print(self.datTree[self.datSize-1:])
		print("=== seg tree debug print end ===")

def LongestIncreaseSeaquence(H,A):
	
	
	N = len(H)
	
	lis = 0

	
	
	tree = SegTree(N,max,0,-1e18)
	for n in range(N):

		

		maxValOfCurrentRange = tree.query(0,H[n])
		valOfNext = tree.query(H[n],H[n]+1)

		

		if valOfNext < maxValOfCurrentRange + A[n]:
			
			
			tree.update( H[n], maxValOfCurrentRange + A[n] )

	lis = tree.query(0,N+1)
	return lis


def main():
	N = int(input())
	
	H = list(map(int, input().split()))
	A = list(map(int, input().split()))
	
	print(LongestIncreaseSeaquence(H,A))



if __name__ == "__main__":
	main()

Solution (Python):
class BITmax:
    def __init__(self, N, init=0):
        self.init = init
        self.length = N + 1
        self.tree = [self.init] * (N+1)
    
    def set(self, x, value):
        while x < self.length:
            old = self.tree[x]
            if value <= old:
                break
            self.tree[x] = value
            x += x & -x
    
    def find_max_to(self, x):
        result = self.init
        while x > 0:
            result = max(result, self.tree[x])
            x -= x & -x
        return result

def main():
    N = int(input())
    dpt = BITmax(N)

    h_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))

    for h, b in zip(h_list, b_list):
        dpt.set(h, dpt.find_max_to(h-1) + b)

    print(max(dpt.tree))

if __name__ == '__main__':
    main()

Solution (Python):
class BITmax:
    def __init__(self, N, init=0):
        self.init = init
        self.tree = [self.init] * (N+1)
    
    def set(self, x, value):
        while x < N + 1:
            old = self.tree[x]
            if value <= old:
                break
            self.tree[x] = value
            x += x & -x
    
    def find_max_to(self, x):
        result = self.init
        while x > 0:
            result = max(result, self.tree[x])
            x -= x & -x
        return result

N = int(input())
dpt = BITmax(N)

h_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))

for h, b in zip(h_list, b_list):
    dpt.set(h, dpt.find_max_to(h-1) + b)

print(max(dpt.tree))