블로그 옮겼습니다

문제 링크 \(1\le{N, M, K}\le{300,000}\)\(1\le{a_i, p_i}\le{10^9}\)M개의 구역이 있다. 각각의 구역은 N개의 국가중 하나에 의해 소유된다. N개의 국가는 각자 pi개의 운석 샘플을 가져가야 한다.유성이 K번 떨어진다. 유성이 한번 떨어질 때에는 특정 연속된 구간에 특정량이 떨어진다.li, ri, ai 로 표현될 수 있으며 구역은 원형이므로 li > ri 일 수도 있음에 유의한다. 유성이 어떤 국가에 속한 구역에 떨어지면 그 떨어진 개수만큼 해당 국가는 샘플을 습득할 수 있는 것이다.그렇다면 각 국가가 필요로 하는 샘플의 개수를 처음으로 충족하게 되는 건 몇 번째 유성이떨어졌을 때인지 구하는 문제이다. 즉, 답은 N개의 정수를 출력해야한다.naive 하게 생각해..

http://codeforces.com/contest/831/problem/E N > N; for(int i = 1 ; i > a; idxs[a].push_back(i); st.insert(a); update(i, 1); } int pos = 0; ll ans = 0; nums.assign(all(st)); for(int i = 0 ; i

우선 N개의 원소를 가진 어떤 임의의 배열 X가 있고,이 안에 크기 M의 구간(subarray) A가 있다고 하자. 물론 값들은 정렬되지않은 상태이다. 이 때 A의 K번째 원소를 구하는 방법은 여러가지가 있다. 우선 내가 아는 K번째 원소를 찾는 방법들을 구체적으로 써보자면(사실 내가 파라메트릭서치라고 표현하는것도 역시 바이너리 서치인데, 구분을 위해 다르게씀)(그리고 값의 범위가 큰 경우에는 좌표압축은 이미 했다고 가정한다.)1. 벡터+sort2. k번째 원소 세그먼트트리3. k번째 원소 BIT4. BIT + 파라메트릭서치 + 바이너리서치5. 머지소트+세그먼트트리+파라메트릭서치+바이너리서치6. 2D 세그먼트트리 이것 이외에도 버킷으로 어찌저찌하는 것도있는것같은데 잘모르겠다. 이것들 중에서 쿼리가 들어와..

boj.kr/9426 \(1\leq{N}\leq{250000}\) \(1\leq{K}\leq{5000}\) \(K\leq{N}\) \(0\leq{a_i}\leq{65535}\) 이 문제는 N개의 수와 구간의 길이 K가 주어졌을 때 N-K+1 개의 연속된 구간의 중앙값을 모두 더하여 출력하는 문제이다. 중앙값의 정의는 (K+1)/2 번째로 작은 수이다. naive 하게 생각해보면 O(N)개의 구간에 대해 정렬하여 가운데값을 구하는데 O(NlgN) 이므로 O(N^2lgN)이 든다. 근데 O(N^2)도 시간안에 돌아가기 힘들다. 어떻게할까? 펜윅트리에 수가 현재 길이 K의 구간안에 하나 들어갈 때마다 수 자체를 인덱스로 1업데이트하고 구간에서 사라지면 -1업데이트하는식으로 생각해보자. 그럼일단 0번째인덱스부터..

문제 링크 \(1\leq{N}\leq{10^5}\)\(1\leq{M}\leq{2\cdot{10^5}}\)\(1\leq{x,y}\leq{10^6}\) 2차원 좌표평면상에 도시의 개수 N이 주어지고 N개의 줄에 각 도시의 x,y 좌표가 주어진다.그리고 쿼리의 수 M이 주어지는데 각 쿼리의 동작은 두가지다. road a b : 도시 a와 b 사이에 직선 도로를 이어 하나의 state 로 만든다.line c : x축에 평행하게 y = c 직선을 그어 한 도로라도 이 직선에 교차되는 state 들의 수와그 state 들의 도시 수의 합을 출력한다. c는 무조건 1.5, 5.5 등 ~~.5 의 형태이며 도로들은 서로 교차하지 않는다. \(0\lt{c}\lt{10^6}\) 서로다른 state 가 도로에 의해 하나의 ..

https://oj.uz/problem/view/KRIII5P_3 \(1\leq{N}\leq{10^5},\,0\leq{s_{i},\,e_{i}}\leq{10^9}\)N개의 구간 \([s_{i},\,e_{i}]\) 가 입력으로 주어질 때(\(s_i\gt{e_i}\) 면 공집합)구간들의 교집합이란 \([max(s_1,\,s_2,\,\cdots,\,s_k),\,min(e_1,\,e_2,\,\cdots,\,e_k)]\)구간의 길이는 \(max(0,\,e_{i}-s_{i})\) 으로 정의 될 때선택된 구간들의 교집합의 길이가 1이상이도록 구간들을 선택할 때그 선택하는 방법의 수와 그 각각의 방법에서 교집합의 길이들의 합을 구하는 문제이다. 우선 방법의 수는 라인 스위핑으로도 풀 수 있고, 좌표압축+펜윅트리로도 풀..