Untitled
python
a month ago
2.1 kB
5
Indexable
Never
from sys import stdin from math import log2, ceil MOD = 10**9 + 7 input = stdin.readline sz = 1000001 # 입력 받기 h = (1<<int(ceil(log2(sz))+1)) # with open('1.in', 'r') as file: n = int(input()) nums = list(map(int, input().strip().split())) tree = [(0,0) for _ in range(4*(sz))] # 길이 개수 def update(idx:int, val): global h idx += h tree[idx] = val idx//=2 while(idx>0): left_leng, left_cnt = tree[idx*2] right_leng, right_cnt = tree[idx*2+1] if(left_leng == right_leng): tree[idx] = (left_leng, (left_cnt + right_cnt)%MOD ) elif left_leng > right_leng: tree[idx] = (left_leng, left_cnt)# tree[idx*2] else: tree[idx] = (right_leng, right_cnt)# tree[idx*2+1] idx//=2 return def query(a:int, b:int): global h a += h b += h ret = 0 cnt = 0 while(a<=b): if (a%2==1): left_leng, left_cnt = tree[a] if ret == left_leng: cnt = (cnt + left_cnt) % MOD elif left_leng > ret: ret = left_leng cnt = left_cnt a+=1 if (b%2==0): right_leng, right_cnt = tree[b] if ret == right_leng: cnt = (cnt + right_cnt) % MOD elif right_leng > ret: ret = right_leng cnt = right_cnt b-=1 # ret = max(ret, tree[b]) a>>=1 b>>=1 return ret, cnt # arr = [10, 20, 10, 30, 20, 50] from math import log2 res = 0 cnt = 0 compress_dict = {num : idx+1 for idx , num in enumerate(sorted(nums))} for idx, num in enumerate(nums): best_leg, best_cnt = query(0, num-1) if(best_leg == 0): update(num,(1,1)) else: update(num, (best_leg+1, best_cnt)) if res < best_leg+1: res = best_leg + 1 # cnt = best_cnt # num-1 개수 이전 ? # elif res == best_leg+1: # cnt = (cnt + best_cnt)%MOD print(best_leg, best_cnt) print(res, tree[:30])