문제

문제를 고르고 내장 에디터에서 풀이를 작성해 보시기 바랍니다. 채점기가 실제 테스트 케이스로 코드를 바로 검증하고, 아카이브의 문제들도 자유롭게 둘러볼 수 있습니다.

전체 결과문제 894개

제목	난이도	유형	정답자	시간 제한	메모리 제한	채점
Magic Chessboard고정된 위치를 기준으로 하는 직사각형 영역의 최대공약수를 구하는 질의와, 임의의 직사각형 영역에 같은 값을 더하는 갱신을 함께 처리한다. N 곱하기 M은 500000 이하이고 연산 수는 100000 이하이다. 문제에서 주어진 조건만으로 판단할 때 2차원 GCD 세그먼트 트리와 차분 배열을 결합해야 하는 매우 어려운 문제이다. 인터뷰 문제가 아니라 대회용 고난도 문제에 해당한다. 19930324 같은 특수한 숫자는 정답 횟수와 관련된 장치일 뿐 알고리즘에는 영향을 주지 않는다. 갱신이 값을 더하는 형태이므로 GCD의 차분 성질을 이용해야 한다. 각 행과 열에 대해 차분 배열을 관리하고 GCD 세그먼트 트리로 구간 GCD를 유지하는 방식이 필요하다. 쿼리 영역이 고정된 위치를 기준으로 확장되므로 그 점을 활용한 최적화가 가능하다. 난이도는 9로 평가한다.	어려움9	세그먼트 트리정수론+2	아직 제출이 없습니다	5초	512 MB	지문만 제공
국제 메시 기구루트가 있는 트리에서 서브트리와 경로에 대한 구간 덧셈, 구간 곱셈, 구간 합 질의를 처리하고 답을 2^32로 나눈 나머지로 출력한다.	어려움9	트리세그먼트 트리+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Hard To Explain루트에서 특정 정점까지의 경로에서 C_i >= T인 정점들 중 A_i + B_i*T의 최솟값을 각 질의마다 구한다.	어려움9	트리분할 정복+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
수열과 쿼리 26수열에 대해 구간 chmin 갱신, 구간 최댓값 질의, 구간 합 질의를 최대 백만 개씩 처리한다.	어려움9	세그먼트 트리동적 계획법+2	아직 제출이 없습니다	4초	512 MB	채점 가능
수열과 쿼리 29배열에 구간 덧셈, 구간 chmax, 구간 chmin을 적용하면서 각 원소가 변경된 횟수를 B에 누적하고, B의 구간 합을 구한다.	어려움9	세그먼트 트리연결 리스트+2	아직 제출이 없습니다	4초	512 MB	지문만 제공
수열과 쿼리 30구간 덧셈, 다른 구간을 복사해 붙이는 갱신, 구간 합 질의를 최대 20만 번 처리하는 문제입니다.	어려움9	세그먼트 트리누적 합+2	아직 제출이 없습니다	2초	512 MB	지문만 제공
여행하는 상인n개 마을의 요일별 가격 변동이 주어질 때, 마을 s에서 t로 이동하는 여행에서 한 번 사고 나중에 팔아 얻을 수 있는 최대 이익을 q개의 질의마다 구한다.	어려움9	세그먼트 트리분할 정복+2	아직 제출이 없습니다	10초	1024 MB	채점 가능
호텔배열에서 한 지점의 높이가 갱신될 때마다, 각 질의 구간 [l, r] 안에서 내부에 계곡이 없는 가장 긴 연속 부분 구간의 길이를 구한다.	어려움9	세그먼트 트리배열+2	아직 제출이 없습니다	2초	512 MB	채점 가능
동적 지름가중치가 있는 트리에서 간선 가중치가 갱신될 때마다 지름을 출력한다. 각 질의는 직전 답을 이용해 복호화한다.	어려움9	트리분할 정복+2	아직 제출이 없습니다	5초	512 MB	채점 가능
Majorant배열에서 점 갱신이 일어나고, 각 구간 질의마다 엄격한 다수 원소가 i인 부분배열의 개수에 i를 곱한 합을 998244353으로 나눈 나머지를 구한다.	어려움9	세그먼트 트리분할 정복+2	아직 제출이 없습니다	2초	512 MB	지문만 제공
Triple Jump직선 위 각 구간의 강도를 받아, 여러 구간 질의마다 a<b<c와 b-a≤c-b를 만족하며 세 지점의 강도 합이 최대가 되는 값을 구한다.	어려움9	동적 계획법분할 정복+2	아직 제출이 없습니다	2초	512 MB	지문만 제공
두 안테나각 질의 구간에 속한 안테나 쌍 중 서로 통신할 수 있는 쌍이 있는지 판별하고, 있다면 통신 비용 \|Hx-Hy\|의 최댓값을 구한다.	어려움9	세그먼트 트리그래프+2	아직 제출이 없습니다	3초	512 MB	지문만 제공
시간을 달리는 비타로경로 그래프의 각 간선 i는 시간 구간 [L_i, R_i)에서만 지날 수 있고 1쵸 되감기에 비용 1이 들 때, 간선 구간 갱신과 (A,B)에서 (C,D)로 가는 최소 되감기 횟수를 묻는 질의에 답한다.	어려움9	세그먼트 트리그래프+2	아직 제출이 없습니다	3초	512 MB	지문만 제공
Wild Boar가중 무방향 그래프에서 정해진 순서의 음식 지점을 잇달아 방문하되 방금 지나온 도로를 곧바로 되짚을 수 없고, 매일 목록의 한 원소가 바뀔 때마다 최소 총 시간 또는 -1을 구한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	10초	1024 MB	지문만 제공
고용후보자들의 평가값이 주어지고 값 갱신이 발생할 때, 평가값이 기준 이상인 후보들이 이루는 연속 구간의 개수를 구하는 질의에 답한다.	어려움9	세그먼트 트리분할 정복+2	아직 제출이 없습니다	5초	512 MB	채점 가능
수열과 쿼리 32점 갱신이 있는 수열에서 각 구간의 xor이 주어진 작은 집합에 속하도록 전체를 분할할 수 있는지 판정한다.	어려움9	동적 계획법누적 합+2	아직 제출이 없습니다	10초	512 MB	채점 가능
수열과 쿼리 33부분 배열마다 서로 겹치지 않는 비어 있지 않은 연속 구간 k개를 골라 원소 합의 최댓값을 구한다.	어려움9	동적 계획법세그먼트 트리+1	아직 제출이 없습니다	5초	512 MB	지문만 제공
트리와 쿼리 13루트와 부모가 바뀔 수 있는 트리에서 서브트리와 경로에 대한 대입, 덧셈, 최솟값, 최댓값, 합 쿼리를 처리한다.	어려움9	트리세그먼트 트리+2	아직 제출이 없습니다	3초	512 MB	지문만 제공
수열과 쿼리 34두 정수 수열 a와 b를 두고 갱신과 구간 질의를 처리한다. a의 접미사 중 b와 가장 길게 일치하는 것의 길이와 그 개수를 구하고, b의 두 접미사의 최장 공통 접두사를 구하며, b의 두 부분 문자열을 이어 붙인 것이 b의 연속 부분 문자열인지 판정한다.	어려움9	문자열 매칭세그먼트 트리+2	아직 제출이 없습니다	2초	512 MB	채점 가능
수열과 쿼리 36구간 [l,r] 안에서 최댓값과 최솟값의 차가 y-x인 부분 구간 [x,y]의 개수를 세는 쿼리에 답한다.	어려움9	세그먼트 트리분할 정복+2	아직 제출이 없습니다	1초	512 MB	지문만 제공
비행기 타고 가요각 표 i는 출발 도시가 [Bi,Ci]에, 도착 도시가 [Di,Ei]에 속할 때만 가격 Ai로 쓸 수 있다. K번 도시에서 모든 도시로 가는 최소 표 값 합을 구한다.	어려움9	그래프최단 경로+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
색종이와 쿼리축에 평행한 직사각형 N개와 질의 직사각형 M개가 주어질 때, 각 질의 영역 안에서 한 점을 덮는 입력 직사각형 수의 최댓값을 구한다.	어려움9	세그먼트 트리분할 정복+2	아직 제출이 없습니다	1초	512 MB	채점 가능
은광N×N 격자에 대해 행 또는 열을 반전하는 연산이 주어질 때마다, K×K 정사각형 안에 포함되는 은광 개수의 최댓값과 그 최댓값을 이루는 정사각형의 수를 구한다.	어려움9	구현누적 합+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Seven Nevers순열에서 연속한 k개 원소를 지웠을 때 남은 수열의 최장 증가 부분 수열 길이를 모든 시작 위치마다 구한다.	어려움9	동적 계획법세그먼트 트리+2	아직 제출이 없습니다	2초	512 MB	채점 가능
Data Structure Problem2^p 크기 배열에서 점 갱신과 구간 합 질의를 처리하면서, 주어진 k와의 비트 AND, OR, XOR로 인덱스를 재배열하는 전역 변환까지 수행한다.	어려움9	세그먼트 트리비트 연산+2	아직 제출이 없습니다	8초	512 MB	지문만 제공
Rounddog를 행복하게 만들기원소가 모두 서로 다르고 최댓값에서 길이를 뺀 값이 k 이하인 부분 배열의 개수를 센다. 배열 길이는 최대 300,000이고 원소는 1 이상 n 이하다.	어려움9	분할 정복투 포인터+2	아직 제출이 없습니다	2초	512 MB	채점 가능
OR과 쿼리배열에 구간 비트 OR 갱신을 적용하면서, 주어진 구간에서 값이 K인 위치의 개수를 센다.	어려움9	세그먼트 트리비트 연산+2	아직 제출이 없습니다	1.5초	256 MB	채점 가능
데자 뷰배열에서 점 갱신이 일어나는 가운데, l 이후에서 시작하는 길이 4인 증가 부분수열을 끝내는 가장 작은 위치 d를 찾는 질의에 답한다.	어려움9	세그먼트 트리동적 계획법+2	아직 제출이 없습니다	5초	512 MB	채점 가능
최소 스패닝 트리와 쿼리가중치 방향 그래프 G와 i개 정점의 방향 경로 그래프의 텐서 곱에 대해, i가 2부터 Q+1까지 각각의 최소 스패닝 트리 간선 가중치 합을 구한다.	어려움9	최소 신장 트리그래프+2	아직 제출이 없습니다	5초	256 MB	지문만 제공
Algebra on Segment소수 p와 배열이 주어질 때 구간 곱 갱신과 구간 원소들이 생성하는 부분군의 위수를 구하는 질의를 처리한다.	어려움9	정수론세그먼트 트리+2	아직 제출이 없습니다	10초	512 MB	지문만 제공
Dirt Ratio연속한 부분 배열을 골라 (서로 다른 값의 개수)/(부분 배열 길이)를 최소로 만들고 그 값을 출력한다.	어려움9	이분 탐색누적 합+2	아직 제출이 없습니다	2초	512 MB	채점 가능
Ants가중치가 있는 트리와, 각자 시각 t_i에 a_i에서 b_i로 가는 유일한 경로를 걷는 개미 m마리가 주어진다. 각 개미마다 한 점에서 한 순간에 만날 수 있는 다른 개미 수의 최댓값을 구한다.	어려움9	트리누적 합+2	아직 제출이 없습니다	5초	256 MB	지문만 제공
Knapsack and Queries무게가 항상 증가하는 쿠키를 넣고 가장 가벼운 쿠키를 빼는 연산을 반복하면서, 고른 무게 합을 MOD로 나눈 나머지가 [l, r]에 들어가는 최대 가치를 매번 구한다.	어려움9	동적 계획법세그먼트 트리+1	아직 제출이 없습니다	10초	1024 MB	지문만 제공
Conic Section점들을 의사난수로 생성하고, 점 갱신, x 구간의 y 반전, x 구간에서 이차식의 최댓값 질의를 처리한다.	어려움9	세그먼트 트리기하+2	아직 제출이 없습니다	3초	256 MB	지문만 제공
Guess the Data Structure배열에 원소 추가, 구간 합, 전체 원소에 대한 xor 누적, 전체 정렬 연산이 주어질 때 각 구간 합 질의에 답한다.	어려움9	세그먼트 트리비트 연산+2	아직 제출이 없습니다	5초	256 MB	지문만 제공
Hash Table개방 주소법 해시 테이블에 삽입하는 명령들의 순서를 삽입과 삭제로 갱신하면서, 각 질의가 끝난 뒤 전체 비용(건너뛴 점유 셀 수)의 합을 구한다.	어려움9	세그먼트 트리해시맵+2	아직 제출이 없습니다	5초	256 MB	지문만 제공
Process with Constant Sum배열에 점 갱신이 주어질 때, 각 구간 질의마다 주어진 두 이동 연산을 더 이상 불가능할 때까지 적용해 얻을 수 있는 0의 최대 개수를 구한다.	어려움9	세그먼트 트리그리디+2	아직 제출이 없습니다	2초	512 MB	지문만 제공
수열과 쿼리 39구간에 등차수열을 더하는 갱신과, 구간 안에서 가장 긴 등차수열 부분 배열의 길이를 묻는 질의를 처리한다.	어려움9	세그먼트 트리수학+2	아직 제출이 없습니다	2초	512 MB	채점 가능
점프격자 위의 도시들과 한 도시에서 직사각형 안의 임의 도시로 이동하는 포털이 주어질 때, 1번 도시에서 모든 도시까지의 최단 시간을 구한다.	어려움9	최단 경로그래프+2	아직 제출이 없습니다	1초	512 MB	채점 가능
Progression등차수열을 더하거나 대입하는 구간 갱신을 처리하면서, 주어진 구간 안에서 인접 차이가 일정한 가장 긴 연속 구간의 길이를 구한다.	어려움9	세그먼트 트리연결 리스트	아직 제출이 없습니다	1초	1024 MB	지문만 제공
원자구간 덧셈 갱신이 주어지는 전하 수열에서, 질의 구간 안에 한정했을 때 인접한 두 전하의 차가 정확히 1인 최장 연속 구간의 길이를 구한다.	어려움9	세그먼트 트리동적 계획법+2	아직 제출이 없습니다	2초	512 MB	채점 가능
Meetings각 질의 구간에서 회의 장소를 정할 때, 참가자마다 자기 산과 회의 산 사이 최대 높이의 합이 최소가 되는 값을 구한다.	어려움9	세그먼트 트리분할 정복+2	아직 제출이 없습니다	4.5초	768 MB	지문만 제공
트리와 쿼리 18루트가 바뀌는 상황에서 서브트리 덧셈, 경로 덧셈, 그리고 한 정점에서의 거리 가중 합을 구하는 트리 쿼리 문제다.	어려움9	트리세그먼트 트리+2	아직 제출이 없습니다	5초	512 MB	지문만 제공
Stock Analysisn개의 변동 값이 주어질 때, 각 질의 [S, E] 구간에서 U를 넘지 않는 가장 큰 연속 부분합을 구한다.	어려움9	배열누적 합+2	아직 제출이 없습니다	2초	512 MB	지문만 제공
Иллюзия сортировки배열의 모든 원소에 b를 XOR한 결과가 정렬되게 하는 최소 b를 구하고, 원소 하나를 바꿀 때마다 다시 구하거나 불가능하면 -1을 출력한다.	어려움9	비트 연산분할 정복+2	아직 제출이 없습니다	2초	512 MB	지문만 제공
Dynamic Convex Hull삽입과 삭제가 있는 함수 집합 f_i(x)=(x-a_i)^4+b_i에서 주어진 x에 대한 최솟값을 구한다.	어려움9	세그먼트 트리분할 정복+2	아직 제출이 없습니다	4초	512 MB	지문만 제공
Towns and Roads열리고 닫히는 간선을 가진 트리에서 로봇이 열린 간선만 따라 이동하며, 각 질의 후 로봇 위치에서 가장 먼 마을을 모두 오름차순으로 출력한다.	어려움9	트리DFS+2	아직 제출이 없습니다	2초	512 MB	지문만 제공
Julius Caesar and Kazusa배열에서 구간을 65536으로 나눈 나머지로 1씩 증가시키는 갱신과, 같은 길이의 두 부분 배열이 같은지 묻는 질의를 처리한다.	어려움9	세그먼트 트리해시맵+2	아직 제출이 없습니다	13초	256 MB	지문만 제공
Sjeckanje수열에 구간 덧셈 갱신이 주어질 때마다, 각 구간의 최댓값과 최솟값의 차이를 합한 값이 최대가 되도록 수열을 자르는 방법의 값을 구한다.	어려움9	수학세그먼트 트리+1	아직 제출이 없습니다	2초	512 MB	지문만 제공
Binary Search Tree여러 BST에 서로 다른 값을 구간 삽입하고, 특정 값을 찾을 때 방문하는 노드 값의 합을 구한다.	어려움9	트리세그먼트 트리+2	아직 제출이 없습니다	2초	256 MB	지문만 제공
Baby's First Suffix Array Problem각 질의에서 부분 문자열 s[l..r]의 접미사 중 위치 k에서 시작하는 접미사가 사전순으로 몇 번째인지 구한다.	어려움9	문자열세그먼트 트리+2	아직 제출이 없습니다	14초	512 MB	지문만 제공
Just Another Game of Stones배열에 구간 chmax 갱신이 가해지는 가운데, 각 질의마다 어떤 구간의 더미와 추가 더미 하나로 만든 님 게임에서 처음 두는 사람이 이기는 첫 수의 가짓수를 구한다.	어려움9	세그먼트 트리게임 이론+2	아직 제출이 없습니다	5초	512 MB	지문만 제공
Polynomial and Easy Queries구간에 f(x)=2x^2-1 또는 g(x)=4x^3-3을 적용하고 한 점 A[x]를 100003으로 나눈 나머지로 출력하는 쿼리를 처리한다. f와 g는 각각 각도 2배와 3배에 대응한다.	어려움9	세그먼트 트리수학+2	아직 제출이 없습니다	2초	256 MB	지문만 제공
밀림 점프오랑우탄이 현재 나무에서 왼쪽이나 오른쪽으로 가장 가까운 더 높은 나무로만 점프할 수 있을 때, 시작 구간과 도착 구간이 주어지면 최소 점프 횟수를 구한다.	어려움9	트리이분 탐색+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Crossing세 개의 유전자 문자열에서 시작해 교배로 얻을 수 있는 문자열을 만들 때, 후보 문자열에 구간 대입 갱신이 일어날 때마다 그 문자열을 얻을 수 있는지 판정한다.	어려움9	문자열세그먼트 트리+2	아직 제출이 없습니다	3초	512 MB	지문만 제공
Truck각 간선에 통행료가 있는 가중치 트리에서 통행료 변경 갱신과, G개의 금과 통행료를 함께 옮길 때 드는 최소 연료를 경로마다 구해 1e9+7로 나눈 나머지를 출력한다.	어려움9	트리동적 계획법+2	아직 제출이 없습니다	1초	512 MB	지문만 제공
Tiles3×N 격자의 흰 칸에 겹치지 않게 도미노를 놓는 경우의 수를 구간마다 세고, 칸 색을 한 칸씩 뒤집는 갱신을 처리한다.	어려움9	동적 계획법세그먼트 트리+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
May I Add a Letter?문자열 끝에 문자를 추가하거나 마지막 문자를 삭제하는 연산을 처리하면서, 매 단계마다 두 번 이상 나타나는 서로 다른 부분 문자열의 개수를 구한다.	어려움9	문자열정렬+2	아직 제출이 없습니다	2.5초	1024 MB	지문만 제공
X-percent Blooming트리가 자라며 노드가 추가될 때마다 잎까지의 거리가 O 이내인 노드 수와 F 이내인 노드 수의 비율을 구한다.	어려움9	트리DFS+2	아직 제출이 없습니다	2초	512 MB	지문만 제공
A + B이진수 A와 B가 주어지고 각각의 비트를 뒤집는 갱신이 있을 때, [A, A+B) 구간에 속하는 x의 최대 1의 개수를 구하는 질의에 답한다.	어려움9	세그먼트 트리비트 연산+2	아직 제출이 없습니다	8초	512 MB	지문만 제공
Do use segment tree가중치가 있는 트리에서 경로 전체를 같은 값으로 바꾸는 갱신과, 경로 위 가중치를 순서대로 나열했을 때 연속 부분 수열 합의 최댓값을 구하는 질의를 처리한다.	어려움9	트리세그먼트 트리+2	아직 제출이 없습니다	2초	512 MB	지문만 제공
고장난 계산기 (Calculator) 게임숫자와 연산기호로 이루어진 수식에 구간 덧셈 쿼리가 반복해서 주어질 때, 망가진 계산기의 무시 규칙과 연산 우선순위에 따라 매번 수식의 값을 1e9+7로 나눈 나머지로 구한다.	어려움9	세그먼트 트리행렬+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
장난감 오렌지 만들기각각 서로 다른 두 색 고리를 가진 N개의 장난감 블록이 주어질 때, 구간 [l,r]의 모든 블록으로 사이클을 하나 이상 만들 수 있는지와 최소 사이클 개수를 답하는 질문 Q개를 처리한다.	어려움9	그래프유니온 파인드+2	아직 제출이 없습니다	6초	1024 MB	지문만 제공
신촌 수열과 쿼리배열의 한 원소를 바꾸는 갱신과, 위치 i를 포함하면서 모든 원소가 j 이상인 구간 중 구간합이 최대인 값을 묻는 쿼리를 처리한다.	어려움9	세그먼트 트리분할 정복+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
RMQ순열 A가 주어질 때 i ≤ j인 구간의 최솟값과 최댓값의 곱 B[i][j]를 미리 구해 두고, B 위의 2차원 직사각형 합 쿼리를 10^9+7로 나눈 나머지로 답한다.	어려움9	세그먼트 트리분할 정복+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Interval Shuffle수열과 m개의 구간이 순서대로 주어지며, 각 구간마다 한 원소를 1 증가시키거나 구간을 임의로 재배열할 수 있을 때, 각 위치에서 얻을 수 있는 최종 값의 최댓값을 구한다.	어려움9	그리디동적 계획법+2	아직 제출이 없습니다	1초	256 MB	지문만 제공
Lamb’s Respite배열 a에 점 갱신이 주어질 때, 최대 체력 x와 Respite 구간 [l,r]마다 챔피언의 최종 체력을 구한다.	어려움9	세그먼트 트리누적 합+1	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Two Kilers배열의 값을 q번 갱신할 때마다 최장 증가 부분 수열의 길이를 k 이하로 잘라 출력한다. k는 20 이하다.	어려움9	동적 계획법세그먼트 트리+1	아직 제출이 없습니다	10초	512 MB	지문만 제공
Yosupo's Algorithmx좌표가 음수인 빨간 점 N개와 양수인 파란 점 N개가 각각 가중치를 가진 채 주어집니다. Q개의 질의마다 y 순서 조건과 x 분리 조건을 만족하는 빨간 점 하나와 파란 점 하나를 골라 가중치 합의 최댓값을 구합니다.	어려움9	분할 정복세그먼트 트리+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
Notebook점 갱신이 있는 배열에서 2배, 절반, xor 연산으로 구간의 수들로부터 만들 수 있는 가장 작은 수를 구하는 질의에 답한다.	어려움9	세그먼트 트리비트 연산+2	아직 제출이 없습니다	1초	128 MB	지문만 제공
Road폭설, 제설, 염화칼슘 살포, 질의를 처리해 도로 구간의 최대 적설량을 10^9+7로 나눈 나머지를 출력한다.	어려움9	세그먼트 트리구현+1	아직 제출이 없습니다	4초	512 MB	지문만 제공
Desperate Fire Survive각 질의 [l,r,k]마다 A[l..r]의 부분 구간 중 같은 레벨 인접 노드를 합치거나 노드를 지워 정확히 레벨 k 하나로 만들 수 있는 구간의 수를 센다.	어려움9	세그먼트 트리분할 정복+2	아직 제출이 없습니다	3초	256 MB	지문만 제공
Osumnjičeni각 질의 구간에 대해, 키 범위가 서로 겹치지 않도록 실현 가능한 라인업(부분 구간)들로 덮는 최소 개수를 구한다. 라인업의 실현 가능성은 구간 교차 조건으로 판정된다.	어려움9	구간그리디+2	아직 제출이 없습니다	1초	512 MB	지문만 제공
CTAHKEB** ANDREW순열의 부분 배열을 순환 이동하는 질의를 차례로 처리한 뒤, 각 질의 후에 반전이 가장 적은 전역 순환 이동의 시작 위치를 출력한다.	어려움9	동적 계획법세그먼트 트리+2	아직 제출이 없습니다	2초	512 MB	지문만 제공
연결 요소와 쿼리행이 1개에서 3개인 격자에서 점 갱신과, 주어진 부분 직사각형 안 연결 요소의 최대 가중치 합을 구하는 쿼리를 처리한다.	어려움9	세그먼트 트리동적 계획법+2	아직 제출이 없습니다	5초	1024 MB	지문만 제공
올바른 괄호 문자열2번 쿼리마다 S[l..r]의 괄호를 바꿔 전체 문자열이 올바른 괄호 문자열이 되는 경우의 수를 1,000,000,007로 나눈 나머지로 구하고, 그 사이 1번 쿼리로 한 글자를 뒤집는다.	어려움9	세그먼트 트리누적 합+2	아직 제출이 없습니다	2초	512 MB	지문만 제공
어떤 우유의 배달목록 (Hard)트리에서 u에서 v로 가는 경로의 i번째 정점에 i만큼 우유를 더하는 갱신이 여러 번 주어질 때, 특정 정점에 배달된 우유의 총량을 구한다.	어려움9	트리세그먼트 트리+2	아직 제출이 없습니다	2초	512 MB	지문만 제공
Sgame문자열과 질의 (m, k)가 주어질 때, 길이가 [m, k]에 있고 길이 k를 넘도록 확장해도 같은 횟수로 나타날 수 없는 부분문자열의 최대 등장 횟수를 구한다.	어려움9	문자열문자열 매칭+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
Even Substringsa부터 f까지의 문자로 이루어진 문자열에서 한 글자를 바꾸는 갱신과, 구간 안에서 모든 문자가 짝수 번씩 나오는 부분 문자열의 개수를 세는 질의를 처리합니다.	어려움9	누적 합비트 연산+1	아직 제출이 없습니다	7초	1024 MB	지문만 제공
Ants and Sugar직선 위에 개미와 설탕을 하나씩 추가하는 Q개의 연산이 주어질 때, 각 연산 직후 거리 L 이내의 설탕을 개미가 먹을 수 있는 최대 개수를 구한다.	어려움9	그리디세그먼트 트리+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
Fish 2물고기 크기에 대한 점 갱신이 주어질 때, 더 큰 이웃이 작은 이웃을 먹는 규칙 아래 구간 [L, R]에서 마지막까지 살아남을 수 있는 물고기 index의 가짓수를 구한다.	어려움9	그리디분할 정복+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
DJ Darko구간 덧셈 갱신과 함께 구간에서 (A_i, B_i)의 가중 중앙값을 구하고, 값이 여러 개면 더 작은 쪽을 택하는 문제입니다.	어려움9	세그먼트 트리이분 탐색+2	아직 제출이 없습니다	4초	256 MB	지문만 제공
게임의 꽃가중치가 있는 트리에서 순증가 경로의 최대 길이를 구하고, 정점 가중치를 바꾸는 M개의 질의마다 그 값을 출력한다.	어려움9	트리동적 계획법+2	아직 제출이 없습니다	6초	1024 MB	지문만 제공
Half Planem개의 반평면 질의마다 직선 아래에 있는 점들의 d를 합한 뒤, 그 점들의 d를 각각 o로 왼쪽 곱한다.	어려움9	기하세그먼트 트리+2	아직 제출이 없습니다	12초	1024 MB	지문만 제공
Connecting CablesN개의 축에 평행한 직사각형이 주어질 때, 모든 쌍마다 각 직사각형에서 점 하나씩 골라 맨해튼 거리 합의 최솟값을 998244353으로 나눈 나머지를 구한다.	어려움9	기하분할 정복+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Making Number고정된 자릿수 집합 X와 갱신되는 Y가 주어질 때, 매 갱신 후 Y 이상인 X의 순열 중 최솟값의 특정 자리를 출력하거나 없으면 -1을 출력한다.	어려움9	그리디세그먼트 트리+2	아직 제출이 없습니다	1.5초	1024 MB	지문만 제공
Tourists트리 위에서 관광객 구간 이동, 도시 전체 의견 증가, 개별 관광객 의견 질의를 입력 순서대로 온라인으로 처리한다.	어려움9	트리DFS+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
Balanced Seesaw Array배열에 구간 덧셈과 구간 대입이 반복될 때, 어떤 부분 배열이 균형 잡힌 시소 배열인지 판별하는 문제다.	어려움9	세그먼트 트리수학+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
qarentheziz zepuence구간 뒤집기 연산이 가해지는 괄호 문자열에서, 부분 문자열을 균형 문자열로 만드는 데 필요한 앞 추가, 뒤 추가, 인접 교환 횟수의 최솟값을 구한다.	어려움9	세그먼트 트리문자열+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
수열과 쿼리 41구간 chmax 갱신과 부분 구간의 최대 연속 부분합 질의를 처리한다.	어려움9	세그먼트 트리구간+1	아직 제출이 없습니다	5초	1024 MB	지문만 제공
수열과 쿼리 421부터 N까지의 순열이 주어지고, 각 쿼리마다 부분 배열 A[l..r]의 최장 증가 부분 수열 길이를 구한다.	어려움9	동적 계획법세그먼트 트리+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Sumex각 질의 구간에 포함된 모든 부분 배열의 최소 제외 값을 더한다.	어려움9	누적 합동적 계획법+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
수열과 구간과 구간과 구간과 쿼리고정된 수열이 주어지고, 각 쿼리마다 b ≤ c인 두 구간 [a,b], [c,d]가 주어질 때 시작이 [a,b], 끝이 [c,d]에 속하는 연속 부분 수열의 평균 최댓값을 구한다.	어려움9	이분 탐색누적 합+2	아직 제출이 없습니다	5초	1024 MB	지문만 제공
선물교류정점이 하나씩 삭제되는 숲에서 국왕이 있는 마을과 주어진 마을 사이를 여러 버스로 갈아타며 운송할 때 드는 최소 비용을 쿼리마다 구한다.	어려움9	트리세그먼트 트리+2	아직 제출이 없습니다	4초	512 MB	지문만 제공
Banany가중치 트리에서 도시 이익이나 도로 통행료가 갱신될 때마다, dist(이전 도시, v) + 이익[v]를 최대로 만드는 도시를 가장 작은 번호 순으로 답한다.	어려움9	트리동적 계획법+2	아직 제출이 없습니다	8초	1024 MB	지문만 제공
Grapevine가중치를 바꿀 수 있는 트리에서 노드의 포도를 켜고 끄며, 각 질의마다 가장 가까운 포도까지의 거리를 구한다.	어려움9	트리세그먼트 트리+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
한별이의 퍼펙트 수열과 쿼리 교실배열에 구간 chmin, 구간 chmax, 구간 덧셈을 적용하고 구간 최솟값, 최댓값, 합을 구하는 쿼리를 처리합니다. 이때 chmin과 chmax의 인자 X는 1 이상 10 이하입니다.	어려움9	세그먼트 트리연결 리스트	아직 제출이 없습니다	6초	1024 MB	지문만 제공
함수열과 쿼리1부터 5까지의 순열 n개가 주어질 때, 각 쿼리마다 주어진 구간의 합성이 목표 순열이 되도록 해당 위치의 순열 하나를 바꾸고 그 값을 출력한다.	어려움9	세그먼트 트리분할 정복+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
송유관 II발전소 설치 구간과 주유소별 기름 공급 이벤트를 처리하며, 각 공급 직후 처음으로 가동 조건을 채운 발전소의 개수와 번호를 오름차순으로 출력한다.	어려움9	세그먼트 트리그리디+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
Hungry Cow아주 긴 날짜 축에서 건초 배달 지점들을 갱신해 가며, 소가 건초를 먹는 날짜 번호의 합을 매 갱신 후 구한다.	어려움9	세그먼트 트리동적 계획법+2	아직 제출이 없습니다	6초	1024 MB	지문만 제공