본문 바로가기

전체 글

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)11505 구간 곱 구하기 문제:icpc.me/11505 구간에 대한 곱을 출력하는 문제이다. 값의 갱신이 빈번하게 일어나기 때문에 세그먼트 트리를 이용해주면 된다. 곱셈의 특성상 구간의 곱을 가지고 있으면 무수히 커질 수 있기 때문에 문제에서 모듈러연산을 요구한다. 이때 단순히 답에만 모듈러연산을 해준다면 노드가 가지고 있는 값이 오버플로우 될 수 있으므로 우리는 노드가 가진 값들을 업데이트 할 때 와 쿼리를 처리할 때도 모듈러연산을 해줘야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #define MOD 1000000007#define MAX_N 1000000typedef long long .. 더보기

티스토리툴바