코뚫린 앙드로이드

https://www.acmicpc.net/problem/15480

{root, a} = v1

{root, b} = v2

{a,b} = v3

라고 하였을때

depth[v1], depth[v2], depth[v3] 중 가장 큰 노드가 답이 된다.

case 1 ) a 와 b 둘다 root의 자손일 경우

case 2) a 또는 b 만 root의 자손일 경우

case 3 ) a와 b 둘다 root의 자손이 아닐 경우 

의 case를 생각해보며 식을 적용해보면 왜 그러한지 알 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_N 100001
#define swap(a,b) {int t = b; b = a; a = t;}
vector<int> vec[MAX_N];
bool visit[MAX_N];
int depth[MAX_N];
int par[MAX_N][20];

vector<pair<int, int> > tmp; // first : depth, second : node
bool cmp(pair<int, int> a, pair<int, int> b) {
     return a.first > b.first;
}

void dfs(int now, int prev, int prevDepth) {
     visit[now] = true;
     par[now][0] = prev;
     depth[now] = prevDepth;
     
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i]] == false) {
               dfs(vec[now][i], now, prevDepth + 1);
          }
     }
}

int lca(int x, int y) {
     if (depth[x] > depth[y]) swap(x, y);
     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if ((diff >= (1 << i))) y = par[y][i];
     }
     if (x == y) return x;
     for (int i = 19; i >= 0; i--) {
          if (par[x][i] != par[y][i]) {
               x = par[x][i];
               y = par[y][i];
          }
     }
     return par[x][0];
}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0); cout.tie(0);
     int N; cin >> N;
     for (int i = 0; i < N - 1; i++) {
          int a, b; cin >> a >> b;
          vec[a].push_back(b);
          vec[b].push_back(a);
     }
     dfs(1, 1, 0);
     for (int i = 1; i <= 19; i++) {
          for (int j = 1; j <= N; j++) {
               par[j][i] = par[par[j][i - 1]][i - 1];
          }
     }
     int M, ret; cin >> M;
     for (int i = 0; i < M; i++) {
          int root, a, b; cin >> root >> a >> b;
          int root_a, root_b, a_b;
          root_a = lca(root, a);
          root_b = lca(root, b);
          a_b = lca(a, b);
          tmp.push_back({ depth[root_a], root_a });
          tmp.push_back({ depth[root_b], root_b });
          tmp.push_back({ depth[a_b], a_b });
          sort(tmp.begin(), tmp.end(), cmp);
          cout << tmp[0].second << "\n";
          tmp.clear();
     }
}

논리적으로 뭔가 해보려고 한참을 고민하다 결국 구글링으로 해답을 찾아본 문제이다.

여러 솔루션들을 보았는데, 논리적 설명보단 테스트케이스를 통해 식을 유추한뒤에

답을 도출해낸 방식이 대다수 이다.

방법이 쉽게 생각나지 않는다면, 테스트 케이스 그대로 따라해보면서 식을 유도하는 것도

실력의 일부가 되는 것 같다.

https://www.acmicpc.net/problem/3176

부모 테이블을 생성할 때에

같은 논리로

MAX 와 MIN 테이블을 만들어 주면 된다.

par[ i ][ k ] : i의 2^k번째 부모의 노드

MAX[ i ][ k ] : i의 2^k번쨰 부모까지의 최대값

MIN[ i ][ k ] : i의 2^k번쨰 부모까지의 최솟값

    for (int i = 1; i <= 19; i++) {
          for (int j = 1; j <= N; j++) {
               par[j][i] = par[par[j][i - 1]][i - 1];
               MAX[j][i] = max(MAX[j][i - 1], MAX[par[j][i - 1]][i - 1]);
               MIN[j][i] = min(MIN[j][i - 1], MIN[par[j][i - 1]][i - 1]);
          }
     }

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define SWAP(a,b) {int t = b; b = a; a = t;}
#define MAX_N 100002

int depth[MAX_N];
int MAX[MAX_N][20];
int MIN[MAX_N][20];
int par[MAX_N][20];
bool visit[MAX_N];
vector<pair<int,int>> vec[MAX_N];

void dfs(int now,int prev, int prevDis, int prevDepth) {
     visit[now] = true;
     depth[now] = prevDepth;
     MAX[now][0] = prevDis;
     MIN[now][0] = prevDis;
     par[now][0] = prev;
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i].first] == false) {
               dfs(vec[now][i].first, now, vec[now][i].second, prevDepth + 1);
          }
     }
}

int lca(int x, int y) {
     if (depth[x] > depth[y]) SWAP(x, y);

     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if (diff >= (1 << i)) {
               y = par[y][i];
          }
     }
     if (x == y) return x;
     for (int i = 19; i >= 0; i--) {
          if (par[x][i] != par[y][i]) {
               x = par[x][i];
               y = par[y][i];
          }
     }
     return par[x][0];
}



int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N; cin >> N;
     for (int i = 0; i < N-1; i++) {
          int a, b, w; cin >> a >> b >> w;
          vec[a].push_back({ b,w });
          vec[b].push_back({ a,w });
     }
     dfs(1, 1, 0, 0);
     for (int i = 1; i <= 19; i++) {
          for (int j = 1; j <= N; j++) {
               par[j][i] = par[par[j][i - 1]][i - 1];
               MAX[j][i] = max(MAX[j][i - 1], MAX[par[j][i - 1]][i - 1]);
               MIN[j][i] = min(MIN[j][i - 1], MIN[par[j][i - 1]][i - 1]);
          }
     }
     int M; cin >> M;
     for (int i = 0; i < M; i++) {
          int x, y; cin >> x >> y;
          int lca_node = lca(x, y);
          int x_to_lca = depth[x] - depth[lca_node];
          int y_to_lca = depth[y] - depth[lca_node];
          int maxAns = -1;
          int minAns = 1e9;
          for (int j = 19; j >= 0; j--) {
               if (x_to_lca >= (1 << j)) {
                    maxAns = max(maxAns, MAX[x][j]);
                    minAns = min(minAns, MIN[x][j]);
                    x_to_lca -= (1 << j);
                    x = par[x][j];
               }
          }
          for (int j = 19; j >= 0; j--) {
               if (y_to_lca >= (1 << j)) {
                    maxAns = max(maxAns, MAX[y][j]);
                    minAns = min(minAns, MIN[y][j]);
                    y_to_lca -= (1 << j);
                    y = par[y][j];
               }
          }
          cout << minAns << " " << maxAns << "\n";
     }
}

https://www.acmicpc.net/problem/13511

DFS와 점화식을 이용하여 parser_table( dp table )를 할 수 없다면 다른 쉬운 LCA 문제를 먼저 푸는게 좋을 것 같다.

u에서 v로 가는데 k번째 노드번호를 출력하는 문제이다.

u에서 v로 가는 경로를 생각해보면

u -> (u와 v의 lca) -> v

의 경로가 될 것이다.

u가 1번째 노드라고 한다면

k번째 노드가 lca 보다 왼쪽에 있는지 오른쪽에 있는지 판단한 뒤에

u 또는 v 부터 diff 만큼 올라간 노드가 답이 된다 !

#include <iostream>
#include <vector>
using namespace std;

#define MAX_N 100001
#define SWAP(a,b) {int t = b;  b = a; a = t;}
typedef long long ll;

vector<pair<int,int>> vec[MAX_N];
ll dis[MAX_N];
int depth[MAX_N];
int par[MAX_N][20];
bool visit[MAX_N];

void dfs(int now, int prev, ll nowDis, int nowDepth) {
     visit[now] = true;
     par[now][0] = prev;
     dis[now] = nowDis;
     depth[now] = nowDepth;
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[ vec[now][i].first] == false) {
               dfs(vec[now][i].first, now, nowDis + vec[now][i].second, nowDepth + 1);
          }
     }

}

int lca(int x, int y) {
     if (depth[x] > depth[y]) SWAP(x, y);

     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if (diff >= (1 << i)) {
               y = par[y][i];
          }
     }
     if (x == y) return x;
     for (int i = 19; i >= 0; i--) {
          if (par[x][i] != par[y][i]) {
               x = par[x][i];
               y = par[y][i];
          }
     }
     return par[x][0];
}

int getK(int x, int y, int k) {
     int lcaNode = lca(x, y);
     int x_to_lca = depth[x] - depth[lcaNode];
     int y_to_lca = depth[y] - depth[lcaNode];
     if (k <= x_to_lca + 1) {
          int diff = k - 1;
          for (int i = 19; i >= 0; i--) {
               if (diff >= (1 << i)) {
                    diff -= (1 << i);
                    x = par[x][i];
               }
          }
          return x;
     }
     else {
          int diff = (y_to_lca)-(k - (x_to_lca + 1));
          for (int i = 19; i >= 0; i--) {
               if (diff >= (1 << i)) {
                    diff -= (1 << i);
                    y = par[y][i];
               }
          }
          return y;
     }

}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0); cout.tie(0);
     int N; cin >> N;
     for (int i = 0; i < N-1; i++) {
          int a, b, w;   cin >> a >> b >> w;
          vec[a].push_back({ b,w });
          vec[b].push_back({ a,w });
     }
     
     dfs(1, 1, 0, 0);
     for (int i = 1; i <= 19; i++) {
          for (int j = 1; j <= N; j++) {
               par[j][i] = par[par[j][i - 1]][i - 1];
          }
     }

     int M; cin >> M;
     for (int i = 0; i < M; i++) {
          int tag; cin >> tag;
          if (tag == 1) {
               int x, y; cin >> x >> y;
               cout << dis[x] + dis[y] - 2 * dis[lca(x, y)] << "\n";
          }
          else {
               int x, y, k; cin >> x >> y >> k;
               cout << getK(x, y, k) << "\n";
          }
     }
}

https://www.acmicpc.net/problem/8012

두 정점간의 거리는 ( 각 노드에서 노드가 길이가 1일경우 )

int distance = depth[node1] + depth[node2] - 2 * depth[lca(node1, node2)];

가 되는데 코드 그대로 해석하자면 

root ~ node1 까지의 거리

+

root ~ node2 까지의 거리

-

2 * (root ~ (node1과 node2의 LCA) 까지의 거리 )

가 된다.

이문제에서 헷갈렸던 점은 한동이는 root에서 첫번째 방문도시로 순간이동 한다고 가정하고 풀어야 한다..

( 문제에 설명이 부족하다고 생각한다 )

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

#define MAX_N 30001
#define SWAP(a,b) {int t = b; b = a; a = t;}
vector<int> vec[MAX_N];
bool visit[MAX_N];
int depth[MAX_N];
int par[MAX_N][20];
int dis[MAX_N];
vector<int> m_vec;
void dfs(int now, int nowDepth, int prev) {
     visit[now] = true;
     depth[now] = nowDepth;
     par[now][0] = prev;
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i]] == false) {
               dfs(vec[now][i], nowDepth + 1, now);
          }
     }
}


int lca(int x, int y) {
     int ret = 0;
     if (depth[x] > depth[y]) SWAP(x, y);

     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if (diff >= (1 << i)) {
               y = par[y][i];
          }
     }
     if (x == y) return x;
     for (int i = 19; i >= 0; i--) {
          if (par[x][i] != par[y][i]) {
               x = par[x][i];
               y = par[y][i];
          }
     }
     return par[x][0];
}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, M;
     cin >> N;
     for (int i = 0; i < N - 1; i++) {
          int a, b;
          cin >> a >> b;
          vec[a].push_back(b);
          vec[b].push_back(a);
     }
     dfs(1, 0, 1);
     for (int j = 1; j <= 19; j++) {
          for (int i = 1; i <= N; i++) {
               par[i][j] = par[par[i][j - 1]][j - 1];
          }
     }
     cin >> M;
     int prev, now;
     long long ret = 0;
     for (int i = 0; i < M; i++) {
          cin >> now;
          if (i)  ret += depth[prev] + depth[now] - 2 * depth[lca(now, prev)];
          prev = now;
     }
     cout << ret << "\n";
     
}

https://www.acmicpc.net/problem/11437

입력을 받은후

1. DFS

입력을 받은뒤, DFS를 돌면서 ( 문제에서 root는 1번노드 ) depth와 부모를 저장해준다.

void dfs(int now, int nowDepth,int prev) {
     visit[now] = true; // visit
     depth[now] = nowDepth; // 현재 노드의 깊이
     par[now][0] = prev; // 현재 노드의 [0]번째 부모( 바로 윗 부모 )
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i]] == false) {
               dfs(vec[now][i], nowDepth + 1,now);
          }
     }
}

2. 부모의 parser_table 생성

반복문으로 parser_table을 생성한다.

주석으로 자세한 설명을 해놓았다.

   // 2 ^ 19 번째 부모는 입력조건보다 한참 크다, 딱 맞게(타이트하게) 부모의 깊이를 잡으려면
     // tree가 오른쪽으로만 늬여진 일렬로된 트리라고 가정한다면, (k = log(노드갯수)) 에서 par[노드수][k]로 설정하면 된다.
     for (int j = 1; j <= 19; j++) {
          for (int i = 1; i <= N; i++) {
               // i번 노드의 2^j번째 부모 = i의 2^(j-1)번쨰 부모의 2^(j-1) 부모
               // example )
               // par[1][1] = par[par[1][0]][0] : 1번 노드의 (2^1)번째 부모 = 1번노드의 (0)번째 부모의 (0)번째 부모( 즉 부모의 부모 )
               // par[1][2] = par[par[1][1]][1] : 1번 노드의 (2^2)번째 부모 = 1번노드의 (2^1)번쨰 부모의 (2^1)번째 부모 ( 즉, 증조부모의 증조부모 )
               // ...
               par[i][j] = par[ par[i][j - 1]][j - 1];
          }
     }

3. lca 함수

(주석 참고)

int lca(int x, int y) {
     // 깊이가 더 깊은 놈 ( 루트와 거리가 먼놈이 y가 된다 )
     if (depth[x] > depth[y]) SWAP(x, y);

     // y는 현재 더 깊이 있음으로 y를 x의 depth만큼 올려줘야 한다.
     // example)
     // x와 y가 diff가 5만큼 차이 난다고 가정하면
     // y에서 par[y][2] : y의 ( 2^2 ) 번째 부모로 올라감
     // y에서 par[y][0] : y의 ( 1^1 ) 번째 부모로 올라감
     // total 5만큼 높이가 올라가게 된다.
     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if (diff >= (1 << i)) y = par[y][i];
     }
     
     // depth를 맞췄는데 같은 노드번호라면 리턴
     if (x == y) return x;
     
     // 부모가 같을테까지 같은 depth를 똑같이 올려준다
     for (int i = 19; i >= 0; i--) {
          if (par[x][i] != par[y][i]) {
               x = par[x][i];
               y = par[y][i];
          }
     }
     // 같아진 부모의 노드번호를 리턴해준다.
     return par[x][0];
}

전체코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

#define MAX_N 100001
#define SWAP(a,b) {int t = b; b = a; a = t;}

vector<int> vec[MAX_N];
bool visit[MAX_N];
int depth[MAX_N];
int par[MAX_N][21];

void dfs(int now, int nowDepth,int prev) {
     visit[now] = true; // visit
     depth[now] = nowDepth; // 현재 노드의 깊이
     par[now][0] = prev; // 현재 노드의 [0]번째 부모( 바로 윗 부모 )
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i]] == false) {
               dfs(vec[now][i], nowDepth + 1,now);
          }
     }
}

int lca(int x, int y) {
     // 깊이가 더 깊은 놈 ( 루트와 거리가 먼놈이 y가 된다 )
     if (depth[x] > depth[y]) SWAP(x, y);

     // y는 현재 더 깊이 있음으로 y를 x의 depth만큼 올려줘야 한다.
     // example)
     // x와 y가 diff가 5만큼 차이 난다고 가정하면
     // y에서 par[y][2] : y의 ( 2^2 ) 번째 부모로 올라감
     // y에서 par[y][0] : y의 ( 1^1 ) 번째 부모로 올라감
     // total 5만큼 높이가 올라가게 된다.
     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if (diff >= (1 << i)) y = par[y][i];
     }
     
     // depth를 맞췄는데 같은 노드번호라면 리턴
     if (x == y) return x;
     
     // 부모가 같을테까지 같은 depth를 똑같이 올려준다
     for (int i = 19; i >= 0; i--) {
          if (par[x][i] != par[y][i]) {
               x = par[x][i];
               y = par[y][i];
          }
     }
     // 같아진 부모의 노드번호를 리턴해준다.
     return par[x][0];
}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, M;
     cin >> N;
     for (int i = 0; i < N-1; i++) {
          int a, b;
          cin >> a >> b;
          vec[a].push_back(b);
          vec[b].push_back(a);
     }
     dfs(1, 0, 1);

     // 2 ^ 19 번째 부모는 입력조건보다 한참 크다, 딱 맞게(타이트하게) 부모의 깊이를 잡으려면
     // tree가 오른쪽으로만 늬여진 일렬로된 트리라고 가정한다면, (k = log(노드갯수)) 에서 par[노드수][k]로 설정하면 된다.
     for (int j = 1; j <= 19; j++) {
          for (int i = 1; i <= N; i++) {
               // i번 노드의 2^j번째 부모 = i의 2^(j-1)번쨰 부모의 2^(j-1) 부모
               // example )
               // par[1][1] = par[par[1][0]][0] : 1번 노드의 (2^1)번째 부모 = 1번노드의 (0)번째 부모의 (0)번째 부모( 즉 부모의 부모 )
               // par[1][2] = par[par[1][1]][1] : 1번 노드의 (2^2)번째 부모 = 1번노드의 (2^1)번쨰 부모의 (2^1)번째 부모 ( 즉, 증조부모의 증조부모 )
               // ...
               par[i][j] = par[ par[i][j - 1]][j - 1];
          }
     }
     cin >> M;
     for (int i = 0; i < M; i++) {
          int a, b; cin >> a >> b;
          cout << lca(a, b) << "\n";
     }
}

https://www.acmicpc.net/source/15427883

쿼리에서 b > c 인경우가 있다.

#include <iostream>
using namespace std;

#define swap(a,b) {int t = b; b = a; a = t;}
#define MAX_N 1000001
typedef long long ll;

ll tree[MAX_N * 4];

ll update_tree(int now, int target, int start, int end, int value) {
     if (target > end || target < start) return tree[now];
     if (start == end) {
          return tree[now] = value;
     }
     int mid = (start + end) / 2;
     return tree[now] = (
          update_tree(now * 2, target, start, mid, value) +
          update_tree(now * 2 + 1, target, mid + 1, end, value)
          );
}

ll query(int now, int left, int right, int start, int end) {
     if (left > end || right < start) return 0;
     if (left <= start && end <= right) {
          return tree[now];
     }
     int mid = (start + end) / 2;
     return (
          query(now * 2, left, right, start, mid) +
          query(now * 2 + 1, left, right, mid + 1, end)
          );
}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, M;
     cin >> N >> M;
     for (int i = 0; i < M; i++) {
          int a, b, c;
          cin >> a >> b >> c;
          if (a) { // modify
               update_tree(1, b-1, 0, N - 1, c);
          }
          else { // sum
               if (c < b) swap(b, c);
               cout << query(1, b - 1, c - 1, 0, N - 1) << "\n";
          }
     }
}

https://www.acmicpc.net/problem/2336

정렬과 세그먼트트리를 이용하여 해결 할 수 있다.

1번 학생 : 0등 1등 7등

2번 학생 : 1등 4등 4등

3번 학생 : 2등 2등 0등

4번 학생 : 3등 7등 1등

5번 학생 : 4등 9등 3등

6번 학생 : 5등 6등 2등

7번 학생 : 6등 0등 6등

8번 학생 : 7등 5등 8등

9번 학생 : 8등 8등 9등

10번 학생 : 9등 3등 5등

로 정렬한뒤에 1번학생 ~ 10번 학생을 처리 하게 되는데,

1번학생은 반드시 굉장한 학생이 될 것이다.

2번학생은 오직 1번학생보다 하나만이라도 높다면 굉장한 학생이 될 것이다.

3번학생은 1,2번학생보다 등수가 모두 높다면 높다면 굉장한 학생이 될 것이다.

...

N번 학생은 N-1학생보다 등수가 다 높다면 굉장한 학생이 될 것이다.

< 1번 학생 >

1번째 리프노드 7로 update

< 2번 학생 >

0~3번 중 최솟값이 현재 7이므로 굉장한 학생이다

4번쨰 리프노드 4로 update

< 3번 학생 >

0~1번중 최솟값이 현재 7이므로 굉장한 학생이다

2번째 리프노드 0으로 update( 이학생 때문에 뒤의 학생들은 대부분 굉장한 학생이 아니게 된다 )

< 4번 학생 >

0~5번중 최솟값이 0이므로 이학생은 굉장한 학생이 아니다.

7번째 리프노드를 1로 update

.... 반복 ....

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX_N 500000

class Info {
public :
     int x, y, z;
     Info() {}
     Info(int x, int y, int z) {
          this->x = x;
          this->y = y;
          this->z = z;
     }
     bool operator < (const Info & b) const {
          return this->x < b.x;
     }
};

Info arr[MAX_N];
int tree[MAX_N * 4];

void init_tree(int now, int start, int end) {
     if (start > end) return;
     if (start == end) {
          tree[now] = 1e9;
          return;
     }
     int mid = (start + end) / 2;
     tree[now] = 1e9;
     init_tree(now * 2, start, mid);
     init_tree(now * 2 + 1, mid + 1, end);
}

int update_tree(int now, int target, int start, int end, int value) {
     if (target > end || target < start) return tree[now];
     if (start == end) {
          return tree[now] = value;
     }
     int mid = (start + end) / 2;
     tree[now] = min(
          update_tree(now * 2, target, start, mid, value),
          update_tree(now * 2 + 1, target, mid + 1, end, value)
     );
     return tree[now];
}

int getMin(int now, int left, int right, int start, int end) {
     if (left > end || right < start) return 1e9;
     if (left <= start && end <= right) return tree[now];
     int mid = (start + end) / 2;
     return min(
          getMin(now * 2 , left, right, start, mid),
          getMin(now * 2 + 1, left, right, mid + 1, end)
     );
}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N; cin >> N;
     for (int i = 0; i < N; i++) {
          int t; cin >> t; t--; arr[t].x = i;
     }
     for (int i = 0; i < N; i++) {
          int t; cin >> t; t--; arr[t].y = i;
     }
     for (int i = 0; i < N; i++) {
          int t; cin >> t; t--; arr[t].z = i;
     }
     sort(arr, arr + N);
     init_tree(1,0,N-1);
     int ans = 0;
     for (int i = 0; i < N; i++) {
          int y = arr[i].y;
          int z = arr[i].z;
          if (getMin(1, 0, y, 0, N - 1) > z) ans++;
          update_tree(1, y, 0, N - 1, z);
     }
     cout << ans << "\n";

}

나한텐 너무 어려운 문제였지만, x,y,z를 묶어서 sort뒤의

출력물을 보고나서 쉽게 접근 할 수 있었다.

https://www.acmicpc.net/problem/3392

처음 보는 세그먼트 트리의 유형에 굉장히 어려움을 겪었다.

밑의 글을 참고해서 풀어보았다.

모든 직사각형의 세로선분과 가로선분으로 생기는 부분을 나누어서 생각하는게 핵심이다.

 x축으로 정렬된 vector에는

4개의 선분이 들어가게된다

vector의 0번인덱스부터 2*n-1번 인덱스부터 선분하나하나씩을 처리해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_LEAF 30000

class Info {
public:
     int x, y1, y2;
     bool left;
     Info() {}
     Info(int x, int y1, int y2, bool left) {
          this->x = x;
          this->y1 = y1;
          this->y2 = y2;
          this->left = left;
     }
     bool operator < (const Info & b) const {
        return this->x < b.x;
     }
};

int tree[MAX_LEAF * 4];
int cnt[MAX_LEAF * 4];
void update_tree(int now, int left,int right, int start, int end, int value) {
     // 범위 체크
     if (left > end || right < start) return;

     // 해당 범위에 들어온다면 현재 cnt를 증가 또는 감소 시켜줌
     if (left <= start && end <= right) {
          cnt[now] += value;
     }

     // 범위에 들어올 지언정 " range_update " 를위해 하단 리프노드까지 내려가야 한다.
     else{
          int mid = (start + end) / 2;
          update_tree(now * 2, left, right, start, mid, value);
          update_tree(now * 2 + 1, left, right, mid+1, end, value);
     }

     // 해당 노드가 0 인데 리프노드라면 그냥 0으로 해주면되고
     //                   리프노드가 아니라면 ( 왼쪾자식 + 오른쪽자식 ) 이 자신의 cnt가 된다.
     if (!cnt[now]) {
          if (start != end)  tree[now] = tree[now * 2] + tree[now * 2 + 1];
          else  tree[now] = 0;
     }
     // 만약 자신이 해당범위에 들어와서 위에서 "cnt[now] += value" 로인해 1이상이 되었다면
     // 자기 하위의 모든 노드들은 범위에 포함되므로, 끝 - 시작 + 1 이 cnt가 된다.
     else  tree[now] = end - start + 1;
}


vector<Info> vec;
int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N;
     cin >> N;
     for (int i = 0; i < N; i++) {
          int x1, y1, x2, y2;
          cin >> x1 >> y1 >> x2 >> y2;
          vec.push_back(Info(x1, y1, y2, true));
          vec.push_back(Info(x2, y1, y2, false));
     }
     // x축 정렬 ( for 라인스위핑 )
     sort(vec.begin(), vec.end());
     Info prev;

     int ans = 0;
     for (int i = 0; i < vec.size(); i++) {
          if (i) ans += (vec[i].x - vec[i - 1].x) * tree[1];
          // 왼쪽 선분인경우 : +1, 오른쪽선분인 경우 : -1
          int value = (vec[i].left == true) ? 1 : -1;
          update_tree(1, vec[i].y1, vec[i].y2 - 1, 0, MAX_LEAF - 1, value);
     }
     cout << ans << "\n";
}