PS/Study (8) 썸네일형 리스트형 PBDS 구현하기 일반적으로 STL의 std::set은 k-th element를 찾거나 counting을 log 시간에 할 수 없다.PBDS(Policy Based Data Structure)은 이를 해결할 수 있다고 한다. Set과 같은 정렬 형태의 자료구조가 필요하면서 위의 동작 요구하는 BOJ의 일반적인 문제는 입력의 제한이 있기 때문에 세그먼트 트리 등으로 충분히 해결할 수 있는 경우가 대부분이다.다만, interaction 문제나 세그먼트 트리로 만들어야하는 key 값의 range가 매우 크거나 실시간 쿼리가 필요한 경우 PBDS를 통해 해결하는 것이 조금 더 효율적일 것이다. 사실 BBST(Balanced Binary Search Tree)라면 PBDS를 쉽게 구현할 수 있는 것 같아서 유명한 RB Tree(R.. 공부할 알고리즘 목록 Knuth's Algorithm X : http://www.secmem.org/blog/2019/12/15/knuths-algorithm-x/ Li-Chao Tree : https://justicehui.github.io/hard-algorithm/2019/05/22/Li-Chao-Tree/ http://www.secmem.org/blog/2021/04/18/lichao-tree-lazy/ Chinese Ramainder Theorem : https://m.blog.naver.com/kks227/221635322468 CHT : https://blog.naver.com/kks227/221418495037 Extended Euclidean Algorithm : 좀 더 간단한 구현체 찾아보기 Heavy-Li.. 알고리즘별 기본 문제 (수정 예정) 보호되어 있는 글입니다. 카탈란 수 ( Catalan Number ) #include using namespace std; const int N=1e6+10, M=1e9+7; typedef long long ll; ll inv[N]={0,1}, cat[N]={1,1}; int main(){ int n; scanf("%d",&n); for(int i=2; i 모듈러 인버스 (modulo inverse) typedef long long ll; typedef pair pii; pll MInv(ll a, ll b) { // a : inverse n | b : modulo p if(!a) return {0,1}; auto [p,q] = MInv(b%a,a); return {q-(b/a)*p,p}; } v[0]=0, v[1]=1; for(int i=2; i 에라토스테네스의 체 1) 소수간 비교 #include using namespace std; const int N=1000000; int cnt=0; vector p; int main(){ p.push_back(2); for(int i=3; i N! mod P https://github.com/infossm/infossm.github.io/pull/166/commits/797eb96dd448a296d87790463ebde4df2f96873d?short_path=d0d4681#diff-d0d46816e14b7e5bc6d8232a85ce5bd9 강한필 9월 개인과제 by ho94949 · Pull Request #166 · infossm/infossm.github.io N! mod P 의 빠른 계산 github.com http://fredrikj.net/blog/2012/03/factorials-mod-n-and-wilsons-theorem/ Factorials mod n and Wilson’s theorem fredrikj.net / blog / Factoria.. Lazy Propagation Segment Tree 공부를 하며 Lazy Propagation에 대해 조금 알게 되었습니다. LightSwitching-USACO-2008-NOV-Gold(https://www.acmicpc.net/problem/1395) Lazy Propagation 이해는 https://www.acmicpc.net/blog/view/26 여기서... 소스코드 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 #include using namespace std; int tr[400000], lz[400000]; void .. 이전 1 다음