본문 바로가기

Algorithm

 (13)
Segment Tree and Lazy Propagation 드디어 느리게 갱신하는 세그먼트 트리의 구현을 끝냈다. update에서 r을 e로 쓴 오타를 몇 시간동안 찾지 못해 고생했다. 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net #include using namespace std; #define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) typedef long long ll; const int N=1e6+1; struct Segment { ll ..
연속합 최대 Segment Tree 말 그대로 구간에서 최대 연속합을 구해주는 세그먼트 트리이다. 금광 세그로 유명하고, 금광 문제를 풀기 위해 배웠다. 아이디어가 신기함! 진한님의 코드를 적극 참고했습니다. 16993번: 연속합과 쿼리 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j : Ai, Ai+1, ..., Aj에서 가장 큰 연속합을 출력한다. (1 ≤ i ≤ j ≤ N) 수열의 인덱스는 1부터 시작 www.acmicpc.net #include using namespace std; #define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) typedef long long ll; const ll INF=1e18; ..
Li Chao Tree 리차오 트리 특: CHT를 사용할 때 필요한 기울기의 단조성이 없어도 된다. 트리 안에 식(흔히 일차함수)을 넣는 것과 점 최소/최대 쿼리를 O(logN)에 해주는 자료구조. 외우기 쉽고 범용성도 좋아 유용할 것 같다는 생각이 든다. CHT로 풀리는 문제는 시간이 빡빡하지 않은 이상 리차오 트리로도 풀린다. 12795번: 반평면 땅따먹기 첫 줄에는 게임을 진행한 정보의 개수 Q(1 ≤ Q ≤ 200,000)이 주어지며, 이어서 Q 줄에 걸쳐 각 정보가 주어진다. 각 줄의 첫 번째 숫자가 1일 경우 이어서 2개의 정수 a, b(|a| ≤ 1,000,000, |b| ≤ 1,000,000, www.acmicpc.net #include using namespace std; #define fastio ios::s..
Bottom-Up Segment Tree 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net #include using namespace std; #define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) typedef long long ll; struct Segment { vector tree; int n; Segment(int n) : tree(2*n), n(n) {} ll f(ll a,ll b) { return a+b; } void ini..
Dinic's algorithm 최대 유량 알고리즘의 최종 버전. 구현은 충분히 외울 수 있을 정도로 직관적이다. 시간복잡도: O(V^2E) (라고 하지만 더 빠르다.) 13161번: 분단의 슬픔 첫 번째 줄에는 UCPC 구성원의 수 N(1 ≤ N ≤ 500)이 주어진다. 두 번째 줄에는 N개의 정수가 주어지는데, i번째 수가 1이면 i번 사람은 무조건 A진영에 들어가야 함을, 2라면 무조건 B진영에 들어가야 www.acmicpc.net #include using namespace std; const int V=503; const int s=501; const int t=502; const int INF=2e9; int n; int c[V][V],f[V][V]; vector ad[V]; int lev[V],work[V]; bool ch..

티스토리툴바