뉴비의 PS 낙서장

오프라인 다이나믹 커넥티비티 알고리즘을 알아보자. Offline Dynamic Connectivity 는 간선 추가, 삭제를 오프라인으로 처리하는 문제에 쓰인다. 대표적으로 BOJ의 16911 = 16912 = 15316 r) return; if(rl 1; add(node*2,l,mid,rl,rr,x), add(node*2+1,mid+1,r,rl,rr,x); } void Rollback(int cntt) { for(int i = 1;i > n >> Q; for(int i = 1;i op >> x >> y; if(x > y) swap(x,y); if(op == 1) vis[i] = 1,LifeTime[{x,y}] = i,QueryIn[i] = {x,y}; else if(op == 2) vis[LifeTim..

2차원 배열이 있다고 생각해보면 위에서 아래로 누적합을 한번 하고 왼쪽에서 오른쪽으로 누적합을 한번한다면, 누적합 배열이 만들어 진다. 이제 그러면 포함-배제의 원리를 이용하여 누적합 배열을 채우면 O(2048N) 으로 시간초과가 나지만 이제 11차원으로 늘려보면 11번의 뱡향으로 밀면 된다는 것을 알 수 있다. 그래서 저 방법을 사용하면 O(11N) 으로 11차원 누적합 배열을 전처리 할 수 있다. Do : 지금 쿼리가 a[ret[0][0]~ret[0][1]][ret[1][0]~ret[1][1]] ... [ret[10][0]~ret[10][1]] 일때 값 구하기, 포함-배제의 원리를 사용하는 2차작업 f : 포함-배제의 원리를 사용하는 1차작업 쿼리를 처리할때는 포함-배제의 원리를 사용해도 시간이 충분..

C++ 로 조합을 구현하는 방법을 알려주겠다. nCr = n-1Cr-1 + n-1Cr 라는 식을 이용하여 O(nr) 만에 구하는 방법도 있지만, n,r 이 10만정도 된다면 메모리도 시간도 펑펑 터질 것이다. 그래서 이번 글에는 조합을 빨리 구하는 방법을 알려주겠다. (와아앙아앙아아 짝짝짝짝) 순서는 STL내장함수인 next_permutation 을 사용해서 출력하면된다. (이 글은 나중에 추가될 예정이다) 조합을 구할려면 일단 식을 보자 조합 식 이제 이 식을 직접 구하면 되는데 n! 을 구하고 r! 을 구하려고 하면 mod 값에 나눠버리는 경우가 있어서 매우 까다롭다. 예를 들어보자. mod = 7, 구하려고 하는 수는 5C3 이다. 그러면 5! 을 구하고 3! 을 구하고 2! 을 구하고 5! 구한것..