너와 나의 스토리

문제: https://www.acmicpc.net/problem/1275 소스 코드: #include #include #include #include #include #define swap(a,b) {int t = a; a = b; b = t;} using namespace std; typedef long long ll; int n, m; ll seg[100001 * 4]; vector v; ll update(int pos, int val, int node, int x, int y) { if (ypos) return seg[node]; if (x == y) return seg[node] = val; int mid = (x + y) >> 1; return seg[node] = update(pos, val,..

문제: https://www.acmicpc.net/problem/12837 문제 풀이: 입력으로 [1 p x]가 들어오면 index가 p인 곳의 값을 x로 바꿔주고 입력으로 [2 p q]가 들어오면 index p부터 q까지의 합을 출력한다. 소스 코드: #include #define sz 1000001*4 using namespace std; typedef long long ll; int n, m; ll seg[sz]; ll update(int pos, int val, int x, int y, int node) { if (posy) return seg[node]; if (x == y) return seg[node] += val; int mid = (x + y) >> 1; return seg[node] =..

문제: https://www.acmicpc.net/problem/1321 소스 코드: #include #include #include #include #include using namespace std; int N,M,seg[500001*4]; int update(int pos, int val, int node, int x, int y) { if (pos > 1; return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * 2 + 1, mid + 1, y); } i..

문제: https://www.acmicpc.net/problem/2357 소스 코드: #include #include #include #include #include #define SIZE 100001*4 #define MAX 1000000000 using namespace std; int n,m,large[SIZE], small[SIZE]; int large_update(int pos,int val,int x,int y,int node) { if (pos > y || pos > 1; return large[node] = max(large_update(pos, v..

문제: https://www.acmicpc.net/problem/1849 푸는 방법: 예제) A[1]=5, A[2]=0, A[3]=1, .......-> 1은 왼쪽에서부터 5번째에 넣고, 2번은 왼쪽에서부터 0번째에 값을 넣는다(왼쪽에서 오른쪽으로 가면서 자리를 찾아갈 때 이미 차있는 곳은 넘어간다) 자리 1 2 3 4 5 6 7 8 번호 2 7 3 5 4 1 8 6 result[6]=1 -> result[1]= 2 -> result[3]=3 -> result[3]=4 -> ..... 어느 위치에 숫자가 존재하여 그만큼 넘어가야할지를 세그로 찾음숫자가 들어간 위치에는 update() 함수를 통해 0을 넣는다. (원래는 각 자리에 1 들어있음) 소스코드:https://gist.github.com/hovy1..

문제 : https://www.acmicpc.net/problem/5676 푸는 방법:1. 세그먼트 트리 사용하는데 그냥 다 곱하면 overflow 발생할 수 있으므로 부호만 저장 소스 코드:https://gist.github.com/hovy1994/7d9134b9a9122e553c39d28d5a7e5b01#file-5676

문제: https://www.acmicpc.net/problem/3653사용 알고리즘: 세그먼트 트리 푸는 방법: 1. n+m 크기의 배열 만들어 영화들의 위치를 저장. pos[m+n]부터 값을 넣는데 1이 가장 위로 가도록 한다. -> pos[m]=1, pos[m+1]=2, pos[m+2]=3 ......... -> update() 함수 이용해서 해당 위치에 1 저장 2. 변수 t에 제일 위에 있는 영화의 인덱스 저장. 3. a번 영화를 뽑을 때 - query() 함수 이용해서 t~pos[a]에 존재하는 영화의 개수 출력. - update() 함수 이용해서 pos[a]위치에 값이 0이 되게 하고, t--; pos[a]=t; 해줌 - 다시 update() 함수로 t위치의 값에 1 넣어줌 (a가 맨 위에 ..