알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14268 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;int N, M;long long Tree[100001 * 4];long long left_tree[100001 * 4], right_tree[100001 * 4];long long lazy[100001 * 4];vector connect[100001];void make_order(int node, int &cnt){ left_tree[node] = ++cnt; for(int i = 0;..

문제 링크입니다. https://www.acmicpc.net/problem/14245  해당 문제를 풀기 위해선 XOR의 기본적인 특징을 하나 알아야합니다. 예를 들어, 10011 ^ 11100을 한다면 01111이 나옵니다. 이때, 11100을 다시 XOR을 한다면 01111 ^ 11100 = 10011이 됨으로 다시 원래대로 돌아옴을 알 수 있습니다.->  "같은 수를 짝수번 XOR 한다면, 원상태로 돌아온다"가 됩니다. 그러므로, 구간의 값을 가진 트리에 XOR을 한다면 구간의 길이를 통해서 XOR 여부를 확인해주면 됩니다. 쿼리의 개수가 크니, 느리게 갱신되는 세그먼트 트리를 사용하고, 이때 사용되는 lazy 배열에 해줘야하는 XOR 값을 계속 XOR 해주면, 0 또는 XOR 값으로만 남아 있을 ..

문제 링크입니다. https://www.acmicpc.net/problem/12844  해당 문제를 풀기 위해선 XOR의 기본적인 특징을 하나 알아야합니다. 예를 들어, 10011 ^ 11100을 한다면 01111이 나옵니다. 이때, 11100을 다시 XOR을 한다면 01111 ^ 11100 = 10011이 됨으로 다시 원래대로 돌아옴을 알 수 있습니다.->  "같은 수를 짝수번 XOR 한다면, 원상태로 돌아온다"가 됩니다. 그러므로, 구간의 값을 가진 트리에 XOR을 한다면 구간의 길이를 통해서 XOR 여부를 확인해주면 됩니다. 쿼리의 개수가 크니, 느리게 갱신되는 세그먼트 트리를 사용하고, 이때 사용되는 lazy 배열에 해줘야하는 XOR 값을 계속 XOR 해주면, 0 또는 XOR 값으로만 남아 있을 ..

문제 링크입니다. https://www.acmicpc.net/problem/1395 느리게 갱신되는 세그먼트 트리를 이용한 문제입니다.  처리할 일의 개수가 10^5이기에 모든 경우를 계속 갱신한다면 시간 초과가 생길 것입니다.따라서, 바꾸는 정보를 기억해 놨다가 나중에 바꿔주는 느리게 갱신되는 방법을 사용해야 합니다. 단체로 바꿨을 때, 켜지는 전구의 수는 '해당 구간 전체 전구 수 - 현재 켜진 전구 수' 입니다. lazy 배열의 값이 홀수일 때만, 전구의 상태를 바꿔주면 된다는 것을 유의해주면 됩니다.   자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #inclu..

문제 링크입니다. https://www.acmicpc.net/problem/10999 느리게 갱신되는 세그먼트 트리를 이용한 문제입니다.느리게 갱신되는 세그먼트 트리는 해당 링크를 참조해주세요. https://www.acmicpc.net/blog/view/26 느리게 갱신되는 세그먼트 트리를 사용할 수 있다면 바로 구할 수 있는 문제였습니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;int N, M, K;long long Index[1000001];vector Tree;vector lazy;long long se..