algoshipda의 블로그

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) :  http://ideone.com/bugbDy 코드 (해싱) :  http://ideone.com/hkjw5n

일반적인 구간 업데이트 쿼리 처리 문제는 Lazy propagation을 구현한 세그먼트 트리로 풀 수 있다.  좀 더 특수한 경우의 문제로 먼저 구간 업데이트 쿼리가 쭈~욱 주어지고, 업데이트 쿼리의 중간에는 다른 쿼리를 처리할 필요가 없는 문제를 생각할 수 있다. 이런 경우의 문제는 구간 업데이트 쿼리를 각각 $O(1)$에 처리할 수 있다. 길이 $N$인 배열 $A$가 주어졌다고 하자. 편의상 인덱스를 $1 \sim N$으로 쓰고 $A[0]$에는 $0$이 들어있다고 생각하자. 그리고 다른 배열을 정의하겠다. $S[i]$ : 구간 업데이트 쿼리에 의해 $A$의 $[l, \infty]$에 일정하게 더해진 값 $P[i]$ : $A[0]$ ~ $A[i]$의 구간합 만약 $S$를 알고 있다고 하면 $P[0] = 0$ $P[i] = P[i - 1] + S[i] + A[i]$ 가 된다. $S$는 구간 쿼리가 구간 $[l, r]$에 $x$를 일정하게 더해라는 식으로 들어오면 $S[l]$에 $x$를 더하고 $S[r + 1]$에 $x$를 빼서 처리할 수 있다. 설명하려고 $S$와 $P$를 따로 썼지만 실제 구현에서는 하나의 배열로 처리해도 무방하다.  -------------------------------------------------------------- 관련 문제 http://codeforces.com/gym/100571/problem/B https://www.acmicpc.net/problem/12746

http://dillinger.io/ 저기서 마크다운으로 작성한 다음에 HTML로 바꿔서 적으면 된다 테스트 : Untitled Document.md Hello World Hello world Hello world apple banana italic bold npm start show me the money black sheep wall function sayHello ( ) { console .log( 'hello world' ); } sayHello(); for ( int i = 0 ; i < n; ++i) { puts ( "Hello World" ); } <addr> 뭔가 애매하게 되는데 만족스럽다.