rofn123

https://www.acmicpc.net/problem/1168#include int tree[400004] = {};int update(int s, int e, int node, int i, int dif) { if(s>i || e=cnt) find(s,m,node*2,cnt); else find(m+1,e,node*2+1,cnt-tree[node*2]);}int main(void) { int n,k,a=0,c=0,d; scanf("%d %d",&n,&k); c=n; a=k; for(int i=1; ic) { a %= c; if(a==0) a = c; } } printf(">");} 풀이 : 세그먼트 트리, 몇번째로 작은 수 인가? 반복문으로 구현한다면, 요세푸스 문제의 경우 아직 선택되지..

#include #include typedef struct A{int x,y;}A; //x index, y power (입력값을 저장할 구조체)int tree[2000000] = {}; //segment tree (n의 최댓값 50만 * 4)int compare(const void *a, const void *b) { //qsort, 오름차순 정렬, 구조체 y값 기준 return (*(A*)a).y - (*(A*)b).y;//왼쪽이 더 크면 +, 오른쪽이 더 크면 -, 같다면 0}int find(int s, int e, int node, int l, int r) { //segment tree 탐색 if(s > r || e e) return; tree[node] += dif; if(s==e) return..

#include int tree[4000004] = {};int find(int s, int e, int node, int cnt) { if(s==e) return s; int mid = (s+e)/2; if(tree[node*2]>=cnt) find(s, mid, node*2, cnt); else find(mid+1, e, node*2+1, cnt-tree[node*2]);}void update(int s, int e, int node, int index, int dif) { if(index e) return; tree[node] += dif; if(s==e) return; int mid = (s+e)/2; update(s, mid, node*2, index, dif); update(mid+1, e,..

#include long long int arr[100001]={}; long long int tree[400004]={}; void update(int s, int e, int node, int index, int val) { //segment tree update if(s > index || e < index) return; tree[node] += val; if(s == e) return; int m = (s+e)/2; update(s, m, node*2, index, val); update(m+1, e, node*2+1, index, val); } long long int find(int s, int e, int node, int l, int r) { //segment tree에서 부분합 구하기 ..

#include int tree[200001]; //tree 배열 int arr[100001]; //요소의 위치를 담을 배열 int sum(int x) { //Fenwick Tree 누적합 구하기 int ans = 0; while(x) { ans += tree[x]; x -= x&(-x); } return ans; } void update(int x, int n, int dif) { //Fenwick Tree 수정하기 while(x

#include int arr[100001]; //요소를 담는 배열 int tree[400004]; //트리를 구성하는 배열 int init(int s, int e, int node) { //트리를 초기화 합니다. if(s==e) return tree[node] = arr[s]; int mid = (s+e)/2; return tree[node] = init(s, mid, node*2) + init(mid+1, e, node*2+1); } int find(int s, int e, int node, int l, int r) { //트리에서 구간의 홀수의 개수를 구합니다. if(s > r || e < l) return 0; if(l

#include typedef struct Node{ //구조체 : 최솟값, 인덱스 int min, index; }Node; Node a[100001]; //요소들을 담는 배열 Node tree[400004]; //트리들을 담는 배열 Node min(Node x, Node y) { //최솟값 찾기 if(x.min != y.min) return (x.min < y.min) ? x : y; //값이 다르다면 더 작은 값의 구조체를 반환 else return (x.index < y.index) ? x : y; //값이 같다면, 더 인덱스가 작은 값의 구조체를 반환 } Node init(int start, int end, int node) { //트리 초기화 if(start == end) return tree[..

#include typedef long long int ll; ll a[1000000]={}; //숫자 담기 ll tree[4000000]; //트리 배열 ll init(int s, int e, int node) { //트리 배열 초기화 (segment tree 초기화) if(s==e) return tree[node] = a[s]; int mid = (s+e)/2; return tree[node] = init(s, mid, node*2) + init(mid+1, e, node*2+1); } ll sum(int s, int e, int node, int l, int r) { //구간합 구하기 if(s > r || e < l) return 0; //찾는 범위가 아니면 0 리턴 if(l