2017/06/05 썸네일형 리스트형 BOJ)13538 XOR 쿼리 문제: icpc.me/13538 5가지 종류의 쿼리를 처리하는 문제이다. 1번 쿼리를 x의 위치에 업데이트 시키는 새로운 세그먼트 트리를 생성한다고 가정하면 persistent segment tree 자료구조를 이용할 수 있다. 고로 1번 쿼리의 경우 트리의 개수 n을 증가시켜주면서 n번째 세그먼트 트리의 x의 위치에 업데이트 시켜준다. 이 방식으로 persistent segment tree를 구축시켜주면 3번 쿼리는 자연스럽게 n=n-k가 된다. 이제 2,4,5의 쿼리를 생각해보자 4번 쿼리의 경우 r번째 세그먼트 트리에서의 0~x의 sum에서 l-1번째 세그먼트 트리에서의 0~x의 sum을 빼줌으로서 처리가능하다. 5번 쿼리의 경우는 r번째 세그먼트 트리가 가지는 값에서 l-1번째 세그먼트 트리가 가.. 더보기 Persistent Segment Tree 먼저 시작하기 전에 .. -오늘 공부한 내용을 제 멍청한 머리가 기억하지 못할까봐 기록하는 개인용 글입니다. -해당 자료구조에 대하여 완벽하게 알고 적는 글이 아니기 때문에 Persistent segment tree를 공부하는 용도로는 좋지 못한 글이 될 확률이 높습니다.-BOJ 11932 문제를 풀기 위해 https://hongjun7.tistory.com/m/64와 http://blog.myungwoo.kr/100 를 많은 부분에서 참고하였습니다. persistent segment tree가 뭔지는 알고있었지만 귀찮아서 공부를 미루다가 오늘 BOJ 11932번을 접하고 도전하게 되었다. persistent segment tree는 가상의 N개의 세그먼트 트리를 O(NlogN)의 공간복잡도로 유지하는 .. 더보기 BOJ)1322 X와K 문제: icpc.me/1322 X가 정해져 있을 때 X+Y = X | Y 를 만족하는 Y는 2진수에서의 연산을 생각한다면 X가 0인 비트에만 1이 채워져있는 수일 것이다. 고로 K번째로 큰 Y를 찾는다면 K를 이진수로 표현하였을 때 1이 채워진 순서를 X에서 0인 부분에 순서대로 채운 수가 된다. 이는 투 포인터로 구해줄 수 있다. 12345678910111213141516#include #include using namespace std;typedef long long ll;ll x, y, k;int main() { scanf("%lld%lld", &x, &k); for (int i = 0, j = 0; j 더보기 BOJ)1837 암호제작 문제: icpc.me/1837 P가 너무 크기 때문에 K를 이용하여 답을 구해내야 한다. 우선 K이하의 소수를 에라토스테네스의 체를 이용하여 구해준 뒤 P가 해당 소수들 중 하나라도 나누어 떨어지는 수가 있다면 BAD를 출력하게 된다. 12345678910111213141516171819202122232425262728293031#include #include using namespace std;char a[110];int k, p[2000000];bool chk(const char *s, int p) { int ret = 0; for (int i = 0; s[i]; i++) ret = (ret * 10 + s[i] - '0') % p; return !ret ? true : false;}int main(.. 더보기 이전 1 다음