https://codeforces.com/contest/276/problem/C Problem - C - Codeforces codeforces.com #include using namespace std; int n, q; int A[200005], R[200005] = {0}; int main() { int i; int x, y; cin >> n >> q; for (i = 0; i > A[i]; } // * 반복문 시간 & 메모리 줄이기 // [시작 index -1] ++ , [마지막 index] -- 후 처음부터 더해줌. for (i = 0; i > x >> y; R[x - 1] += 1; R[y] -= 1; } for (i = 1; i <..
https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net #include using namespace std; // 전체 데이터의 개수는 최대 1,000,000개 long long arr[1000001], tree[1000001]; // 데이터의 개수(n), 변경 횟수(m), 구간 합 계산 횟수(k) int n, m, k; // i번째 수까지의 누적합을 계산하는 함수 long long prefi..
https://codeforces.com/problemset/problem/486/E Problem - 486E - Codeforces codeforces.com // Longest Increasing Subsequence #include using namespace std; int n; int A[100005];// 숫자를 저장할 배열 int L[100005];// LIS(정답)를 저장할 배열 int B[100005];// 역방향으로 숫자를 저장할 배열 int M[100005];// 임시적으로 저장할 배열 int R[100005];// 역방향으로 LIS를 저장할 배열 int O[100005];// LIS를 계산할 때 사용될 수들 저장 int LeftMax[100005];// 왼쪽 전부를 보고 LIS 들..
https://codeforces.com/problemset/problem/219/D Problem - 219D - Codeforces codeforces.com #include #include using namespace std; int n; class Node { public: int pt; int dsum;// 아래쪽에서 뒤집어야 하는 개수의 합 int ans;// node마다 답을 계산해서 저장해놓아야 함 int nchild; vector AD;// 인접한 것 vector DR;// Edge의 Direction 저장 vector RS;// node마다 아래에서 받은 것 }; Node C[200005]; int dfs1(int nd, int PT) // 아래쪽에서 받아서 올리는 것만 계산. { in..
Prefix sum(구간합)이란 ? ※ Prefix sum(구간합): 구간 합이란 크기가 N인 배열(A라고 가정)이 주어졌을 때, 같은 크기 N인 배열(주로 P)로 표현한다. 각각의 index 0
