본문 바로가기

lazy propagation

BOJ)2370 시장 선거 포스터 문제:icpc.me/2370 포스터를 붙이는 순서가 주어질 때 보이는 포스터의 수를 출력하는 문제이다. 포스터의 모든 x좌표와 y좌표를 좌표압축 한 뒤 포스터를 역순으로 보면서 이미 본 포스터는 업데이트 시켜주고 내가 보이는지 여부는 이미 업데이트 된 포스터들이 나를 완전히 가리는지 확인하면 된다. 이는 세그먼트 트리를 이용하여 업데이트 된 구간의 합을 찍어냄으로 판별 가능 하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include using namespace std;int n, seg[80040], lazy[80040],.. 더보기
BOJ)13309 트리 문제:icpc.me/13309 트리에서 두 가지 쿼리를 처리하는 문제이다. 첫번 째 쿼리는 두 정점이 같은 컴포넌트에 존재하는지 여부이고 두번 째 쿼리는 두 정점이 같은 컴포넌트에 존재하는지 여부를 물음과 동시에 존재할 경우 두 정점 x,y 중 x와 x의 부모의 간선을 단절 존재하지 않을 경우 y와 y의 부모의 간선을 단절 시키는 쿼리이다. 오래 생각하다가 못 풀겠어서 풀이를 봤는데 재밌는 문제였다. 우선 루트에서 DFS를 돌면서 정점들의 번호를 방문하는 순서대로 새롭게 매겨준다. 이렇게 하면 어떤 정점 A의 자식들은 모두 A보다 큰 번호를 연속적으로 가지게 된다. 이걸 이용하여 정점 A부터 A의 자식들까지 범위를 저장해놓고 있을 수 있다. 그렇다면 두 정점이 같은 컴포넌트인지 확인하는 경우를 올라갈 수.. 더보기
BOJ)2820 자동차 공장 문제: icpc.me/2820 문제를 잘 읽어보면 1번을 루트로 가지는 트리 구조를 이룬다는걸 알 수 있다. 그럼 상사 X의 부하들은 어떻게 구분할 수 있을까? 트리 구조이기 때문에 X에서 Y로 가는 경로는 오직 하나일 것이다. 이걸 이용하여 X지점에서 시작한 DFS가 끝날 때 까지 탐색되는 모든 노드들은 X의 부하라는걸 알 수 있다. 이를 이용하여 1번 노드에서부터 DFS를 돌려 정점의 번호를 새롭게 매겨준 후 DFS가 끝나는 지점(마지막 부하)의 번호까지 알게 된다면 직원에 대한 증가연산을 구간에 대한 증가 연산으로 치환시킬 수 있다, 구간에 대한 증가 연산으로 치환을 했으니 레이지 프로퍼게이션을 이용한 세그먼트 트리나 ,펜윅 트리 등을 이용하여 쿼리를 처리해주면 된다. 1234567891011121.. 더보기
BOJ)10277 JuQueen 문제: icpc.me/10277 C개의 코어가 있을 때 쿼리를 받아 3종류의 연산을 처리해주면 되는 문제이다. 단 코어의 하한선은 0이고 상한선은 N으로 입력으로 주어진다. 쿼리는 다음과 같다 change X S 코어X를 S만큼 증가시켜라groupchange A B S 코어 A부터 코어B까지 전부 S만큼 증가시켜라state X 코어X의 값을 출력하라 단, 코어를 증가시키다가 상한이나 하한에 다다를시 증가를 멈춘다. change나 groupchange 같은 경우 증가혹은 감소시킨 계수를 출력해야 하는데 우리는 코어를 증가시키다 상한이나 하한에 도달하는 경우를 판단해야한다. 따라서 우리는 구간에 대한 최댓값 최솟값을 세그먼트 트리로 관리하여 구간을 증가 시킬 시 상한혹은 하한에 도달하는지 여부를 판단하여 상.. 더보기
BOJ)1395 스위치 문제: icpc.me/1395 1~N번까지 스위치가 존재할 때 두가지 쿼리에 따른 일을 한다. 1. S~T까지 스위치를 반전 시키는 것2. S~T까지 켜져있는 스위치의 개수를 출력하는 것 우리는 세그먼트 트리의 구간합을 통하여 켜져있는 스위치의 개수를 쉽게 구할 수 있다. 하지만 1번 쿼리의 경우 구간에 대한 갱신이 일어나기 때문에 우리는 lazy propagation을 사용하여 업데이트를 시켜줘야만 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #define MAX_N 100000using namespace std;int n, m, seg[4 * MAX_N],.. 더보기
BOJ)10999 구간 합 구하기2 문제: icpc.me/10999 구간에 대한 합을 출력하는 문제이다. 그런데 쿼리중에 구간에 대한 갱신 연산을 하는 쿼리가 있다. 우리는 세그먼트 트리를 통해 구간에 대한 갱신과 합쿼리를 빠르게 처리 할 수 있지만 구간에 대한 갱신을 세그먼트 트리로만 하려고 한다면 갱신의 경우 최악의 시간복잡도는 O(NlogN)이 될것이다. 만약 쿼리가 전부 갱신만 들어온다면 시간 복잡도는 O(N(M+K)logN)로 당연히 시간초과를 보게 될 것이다. 그래서 우리는 lazy propagation을 이용하여 구간에 대한 갱신을 조금 더 빠르게 해주는 테크닉을 이용하여 문제를 풀어야만 한다. lazy propagation에 대한 설명은 여기에 친절하게 되어있다. 1234567891011121314151617181920212.. 더보기
BOJ)3002 아날로그 다이얼 문제: icpc.me/3002 N개의 다이얼이 주어졌을 때 구간이 주어지면 구간의 합을 구한뒤 구간의 수를 전부 1씩 증가시켜주는 문제이다. 얼핏보면 구간에 대한 증가연산과 구간합을 출력하면 되니 레이지 프라퍼게이션을 이용한 구간합으로 바로 해결할 수 있을것 같지만 문제는 다이얼이기 때문에 9를 증가시키면 0이 된다는 것이다. 결국 0~8의 숫자는 증가시킬 경우 1씩증가하게 되지만 9는 증가시킬 경우 오히려 -9가 되버린다. 이래서 구간에 대한 합을 한번에 노드에 저장하고 있을 경우 증가연산이 애매해질 우려가 있다. 따라서 우리는 구간마다 노드를 10개씩 만들어 0~9까지의 개수를 저장하여 값을 증가시키는 경우 0~9 ->(0+x)%10~(9+x)%10까지로 쉬프트 시킬것이다. 물론 구간에 대한 증가가 .. 더보기
BOJ)12844 XOR 문제: icpc.me/12844 특정 구간에 XOR을 하거나 구간을 XOR한 값을 출력하는 문제이다. N,M이 50만이므로 구간에 대한 쿼리를 빠르게 처리 하기 위해 세그먼트 트리를 사용해야 한다. 이때 한 지점에 대해서가 아닌 구간에 대한 업데이트가 이루어지므로 lazy propagation을 이용하여 최적화 시켜줄 필요가 있다. 주의해야 할 점은 항상 a가 b보다 작지는 않다는 것이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include using namespace std;int n, m, a, b, c, d;in.. 더보기