본문 바로가기
반응형
SMALL

세그먼트트리

3006 - 터보소트 3006번: 터보소트 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이며, 배열의 크기이다. 둘째 줄부터 N개의 줄에는 1보다 크거나 같고, N보다 작거나 같은 수가 중복 없이 주어진다 www.acmicpc.net #include const int LN = 1e5; int N; int idxs[LN + 10]; int tree[LN * 3 + 10]; int seg_init(int n, int s, int e) { if (s == e) { return tree[n] = 1; } int m = (s + e) / 2; return tree[n] = seg_init(n * 2, s, m) + seg_init(n * 2 + 1, m + 1, e); } void upda.. 더보기
1395 - 스위치 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net #include typedef long long ll; const ll LN = 1e5; ll tree[LN * 3 + 10]; ll lazy[LN * 3 + 10]; ll N, M; void propagate(ll n, ll s, ll e) { if (lazy[n] % 2) { tree[n] = (e - s + 1) - tree[n]; if (s != e) { ++lazy[n * 2]; ++lazy[n * 2 + 1]; .. 더보기
19646 - Random Generator 19646번: Random Generator 국렬이는 1부터 N까지의 양의 정수로 이루어진 순열을 주어진 양의 정수 w1 ... , wN를 이용해서 무작위로 만들 것이다. 다음은 무작위로 순열을 만드는 방법이다. 1부터 N까지의 양의 정수 i (1 ≤ www.acmicpc.net #include const int LN = 2e5; int R; int R_ARR[LN]; int tree[LN * 3 + 10]; int N; int push(int n, int s, int e, int t, int v) { if (s == e && s == t) { tree[n] = v; return tree[n]; } if (t < s || e < t) { return tree[n]; } int m = (s + e) / 2.. 더보기
1849 - 순열 1849번: 순열 1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라 www.acmicpc.net #include const int LN = 1e5; int N; int tree[LN * 3 + 10]; int arr[LN]; int R_ARR[LN]; int R; int push(int n, int s, int e, int t, int v) { if (s == e && s == t) { tree[n] = v; return tree[n]; } if (t < s || e < t) { return tree[n]; } int m = (s + e) / 2;.. 더보기
1777 - 순열복원 1777번: 순열복원 순열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 두 번째 줄에는 순열 1, 2, …, N에 해당하는 Inversion sequence가 공백으로 구분되어 들어온다. www.acmicpc.net #include const int LN = 1e5 * 3; int tree[LN]; int N, r; int ARR[LN]; int R_ARR[LN]; int push(int n, int s, int e, int t, int v) { if (t < s || e < t) { return tree[n]; } if (s == e && t == s) { tree[n] = v; return tree[n]; } int m = (s + e) / 2; push(n * 2, s, m, t, v); .. 더보기
1306 - 달려라 홍준 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 www.acmicpc.net #include const int MAX_NUM = 1e6 + 10; const int NODE = 1e6; int tree[NODE * 3]; int N, M; int sp, ep; int push(int n, int s, int e, int t, int v) { if (t < s || e < t) return tree[n]; if (s == e && s == t) { tree[n] = v; return tree[n]; } int m =.. 더보기
반응형
LIST

티스토리툴바