본문 바로가기

Algorithm/Data structure

(6)
경로 가중치 합 hld 구현 코드 특징 : 맞는지 모름 #include using namespace std; #define fastio cin.tie(0)->sync_with_stdio(0) #define X first #define Y second typedef pair pii; const int N=1e5+1; struct Segment { int a[N]; int tree[4*N],lazy[4*N]; void init(int l,int r,int i) { if(l==r) { tree[i]=a[l]; return; } int m=l+r>>1; init(l,m,i
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..