적당히 큰 소수 목록: 1e9+7 1e9+9 998244353 1073741783 2e9+11 

 

N이하 최대 2의 거듭제곱수 = 1<<(int)log2(n) = 1<<(31-clz(n)) 

N이상 최소 2의 거듭제곱수 = 1<<(32-clz(n-1)) 

ctz=하위비트 연속0 개수 

clz=상위비트 연속0 개수 

 

정수 삼분탐색 템플릿 [deprecated: 반씩 쪼개는 상수커팅가능]

while(e-s>2){ 

Int m1=(s*2+e)/3, m2=(s+e*2)/3; 

f(m1)>f(m2)?s=m1:e=m2; 

} 

Ans=min({f(s),f(s+1),f(e)}); 

 

//reverse iterator 

auto mri(auto it){ return make_reverse_iterator(it); }//*mri(it) == *prev(it) 

auto rerase(auto& c, auto ri){ return mri(c.erase(prev(ri.base()))); } 

set 역순필요할때 operator< 오버로딩말고 rbegin()쓰는것도 고려가능 

 

std::reduce로 함수형 가능..이 아니라 아직은 accumulate 써야하는듯(주의: long long 배열에 int 초기값을 주면 int 반환값이 int다. 초기값타입을 누적하는 변수로 쓰는데 그게 int형이기 때문인듯) 

Adjacent_difference:  차이배열 

Inner_product: ? 

Partial_sum: ? 

iota: int to string 

 

튜플분해 

auto [a,b,c]=tp;//abc를 선언과 동시에 초기화 

Tie(a,b,c) = tp;//a,b,c에 값 들어감 

 

중복제거(정렬되있어야함) 

V.erase(unique(v.begin(), v.end()), v.end()) 

 

실수나누기 

Fmod 

 

Rooted트리의 간선가중치는 자식의 정점가중치로 1:1 대응 가능하다. 

루트에 가상의 간선을 연결하면 반대로도 가능. 

 

Gcc에 String 을 트리로 구현한 Rope라는 것이 있다. Logn으로 합치고 찾고 한다. 

https://en.wikipedia.org/wiki/Rope_(data_structure) 

String과 거의 똑같은 인터페이스로 사용가능(cout, += 같이 거의 모든것 가능) 

 

concat two list in O(1): list::splice() (merge는 정렬된거 합치는거다) 

set합치기 개념이면 djs가 더 나음 

 

바텀업dp할때 base case 처리하는게 음수인덱스같은걸 참조해서 더러울 때가 있는데, dp변수 접근을 함수로 감싸서 처리할 수 있다. 모범사례: https://www.acmicpc.net/source/18715592 

static int _0=0, _1=1; assert(_0==0 and _1==1); 상수값 이렇게 작성하면 더 편할듯. 

 

점과 직선사이의 거리: 직선위의 두점을 잡고, 외적으로 삼각형 넓이 구한다음, 수선에 대응하는 밑변길이로 나누면 됨 

 

수직수평 선분만 있을때 간단한 교차판별: x사영끼리 교차 && y사영끼리 교차 => 교차 (지금보니 분리축 이론이네) (boj2536 kyo20111코드, boj10875) 

 

Set Custom Comparator 

struct B{int y, x, idx;}; 

auto ycomp=[](const B& a, const B& b){return tuple<int,int,int>{a.y,a.x,a.idx}<tuple<int,int,int>{b.y,b.x,b.idx};}; 

auto xcomp=[](const B& a, const B& b){return tuple<int,int,int>{a.x,a.y,a.idx}<tuple<int,int,int>{b.x,b.y,b.idx};}; 

set<B, decltype(ycomp)> s(ycomp); 

set<B, decltype(xcomp)> t(xcomp); 

주의사항: tuple비교가 아닌 y만 비교를 하면, x가 달라도 같은y값을 가지는 원소는 같은원소로 취급해서 중복거가 되버린다. 중복허용이 되야하면 tuple비교를 써도 되긴하는데, multiset을 쓰는게 더 간결할 것이다. 

 

Lower Bound Comparator = bool(IterDeref, ValType) 

Upper Bound Comparator = bool(ValType, IterDeref) 

Boj18035 내코드 참고 
 

이동시맨틱 

Std::move(a)로 O(1)에 '이동'시킬 수 있다. STL컨테이너들도 가능 

(주의!!!! pbds의 order statistics tree는 이동연산자가 없다. 실제로 이거때메 맞왜 TLE로 고생한적 있다. Boj.kr/8211. 이동생성자는 복사생성자,대입연산자등이 없을때만 자동선언되는데, Xet에는 복사생성자만 있기 때문. 이동시맨틱을 지원하지 않던때에 만들었기 때문으로 추정됨). 

작은거큰거 병합등에 사용하면 코드가 깔끔해짐(boj.kr/16858). 다만, 자식들을 만들어서 합치는게 아니라, 전부 누적시켜서, 현재값-이전값(-는 역연산 의미)으로 구하는 방식도 매우 자주 나오니 한번쯤 생각해보자. 

리턴값에 명시적 move 필요한 경우들: 

Return문에 삼항연산자등의 조건분기 

l-value identifier가 아닌 경우(a[0]같은 인덱스참조 반환(l-value는 맞지만 identifier가 아니라서 안됨. Boj.kr/16858 참고) 등) 

그냥, RVO가 필요한데 잘 모르겠으면 다 써줘라