그리드 기반 사각형 조합 탐색

그리드 환경에서 특정 조건을 만족하는 부분 도형을 탐색하는 문제에서는 각 도형의 가능한 배치 위치를 체계적으로 분류한 후, 이전 단계의 상태 정보를 기반으로 현재 위치로의 효율적인 전이를 수행하는 접근법이 유용합니다. 불필요한 중복 계산을 방지하기 위해 필요한 파라미터들을 미리 계산해 두면, 단위 위치당 $O(N)$ 시간 복잡도로 상태 전이 테이블을 갱신할 수 있으며, 교차 검증 데이터가 포함된 경우 확장 스캔라인(Sweep-line) 또는 분할 정복 전략을 보조적으로 적용하는 것이 일반적입니다.

수열 쌍 매칭 문제의 차원 축소 최적화

인덱스 $i$와 대응되는 값 $A_i$를 2차원 좌표 $(i, A_i)$로 매핑할 경우, 두 원소 $j < i$가 $A_j < A_i$ 및 $A_j - j \ge A_i - i$ 조건을 동시에 만족하는 지 판단하는 문제는 2차원 범위 조회(Range Query) 형태로 해석됩니다. 이를 단일 차원으로 축약하기 위해 $C_i = A_i - i$ 값을 사전 계산한 후, 주요 키인 $A_i$ 기준으로 오름차순 정렬하고 보조 키인 $C_i$ 기준으로 내림차순 정렬합니다. 이러한 정렬 순서는 시간 축을 따라 이전 단계의 유효한 전이 대상만을 자연스럽히 필터링하도록 보장합니다.

정렬 완료 후 수열을 순회하며 점(Point) 업데이트와 접두어(Max) 조회가 모두 지원되는 펜윅 트리(Fenwick Tree) 또는 세그먼트 트리를 적용하면, 기존 $O(N^2)$의 브루트포스 DP를 $O(N \log N)$ 수준으로 가속화할 수 있습니다. 동일 값이 연속으로 등장할 경우 정렬 안정성을 유지하기 위해 원래 인덱스를 이차 키로 설정하는 처리가 필요하며, 이는 동일한 전이 조건에서의 중복 카운트를 방지하는 표준 관행입니다.

구현 예시 (수열 매칭 최적화)

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

const int MAXN = 500005;
int bit_tree[MAXN];
int n;

inline int low_bit(int x) { return x & -x; }

void bit_update(int idx, int val) {
    for (; idx <= n; idx += low_bit(idx))
        bit_tree[idx] = max(bit_tree[idx], val);
}

int bit_query(int idx) {
    int res = 0;
    for (; idx > 0; idx -= low_bit(idx))
        res = max(res, bit_tree[idx]);
    return res;
}

struct Element { int id; long long val; };
struct ProcessedCoord { int offset; int id; int consec_count; };

bool cmp_element(const Element& a, const Element& b) {
    if (a.val != b.val) return a.val < b.val;
    return a.id < b.id;
}

bool cmp_coord(const ProcessedCoord& a, const ProcessedCoord& b) {
    if (a.offset != b.offset) return a.offset > b.offset;
    return a.id < b.id;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    vector<Element> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i].val;
        arr[i].id = i + 1;
    }
    
    sort(arr.begin(), arr.end(), cmp_element);
    
    vector<ProcessedCoord> coords(n);
    int consec = 0;
    for (int i = 0; i < n; ++i) {
        if (i > 0 && arr[i].val == arr[i-1].val) consec++;
        else consec = 0;
        
        coords[i].offset = arr[i].val - arr[i].id;
        coords[i].id = arr[i].id;
        coords[i].consec_count = consec;
    }
    
    sort(coords.begin(), coords.end(), cmp_coord);
    
    vector<int> dp(n + 1, 0);
    int global_max = 0;
    
    for (const auto& pc : coords) {
        if (pc.offset > 0) continue;
        int prev_valid_idx = pc.id - pc.consec_count - 1;
        if (prev_valid_idx < 1) prev_valid_idx = 0;
        
        dp[pc.id] = bit_query(prev_valid_idx) + 1;
        bit_update(pc.id, dp[pc.id]);
        global_max = max(global_max, dp[pc.id]);
    }
    
    cout << global_max;
    return 0;
}

기능적 그래프와 사이클 분할 전략

방향성 그래프에서 각 정점의 진입차수가 정확히 1개인 구조(Functional Graph)는 독립된 연결 요소마다 하나의 폐경로(Cycle)와 해당 경로를 시작점으로 하는 여려 가지(Tree Branch)들이 결합된 형태를 가집니다. 이러한 특성은 완전 무방향 그래프나 일반적인 트리보다 구조적 제약이 명확하므로, 사이클 내 간선을 제한적으로 차단한 후 잔여 부분 그래프에 대해 단방향 탐색을 수행하는 알고리즘 설계가 효율적입니다.

최대 가중치 매칭을 목표로 할 때, 보통 두 가지 이상의 최적화 지표(예: 우선순위 점수와 보조 메트릭)를 동시에 관리해야 합니다. 이를 해결하기 위해 우선순위가 되는 지표의 가중에 상수 오프셋($V$)을 곱하고, 보조 지표를 나머지 합산 값으로 처리하면 정수 영역 내에서 두 지표를 분리 없이 저장할 수 있습니다. 최종 결과를 출력할 때는 몫과 나머지를 각각 나눗셈과 모듈러 연산으로 복원하면 되며, 재귀 깊이 제한과 입출력 병목 현상을 방지하기 위해 반복문 기반 BFS 또는 명시적 스택 활용, 빠른 IO 라우틴 도입이 권장됩니다.

구현 예시 (기능적 그래프 매칭)

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

typedef long long ll;
const int MAXN = 1000005;
const ll VAL_OFFSET = 1000000000LL;

int T, n;
int source_node[MAXN], partner[MAXN], parent_ptr[MAXN];
int head[MAXN], nxt_arr[MAXN], to_arr[MAXN];
ll edge_weight[MAXN];
int edge_cnt = 0;

void init_graph() {
    memset(head, 0, sizeof(head));
    edge_cnt = 0;
}

void add_directed_edge(int u, int v, ll w) {
    ++edge_cnt;
    to_arr[edge_cnt] = v;
    edge_weight[edge_cnt] = w;
    nxt_arr[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

bool visited[MAXN];
bool path_dropped[MAXN];
ll best_score_0[MAXN], best_score_1[MAXN];
ll total_comp_score[MAXN];
int component_id[MAXN];
int comp_counter = 0;
ll record_0[MAXN], record_1[MAXN];
int anchor_node_0[MAXN], anchor_node_1[MAXN];
int broken_edge_A, broken_edge_B;
bool cycle_found;
stack<int> traversal_stack;

void dfs_cycle_detect(int u) {
    if (cycle_found) return;
    if (visited[u]) {
        while (!traversal_stack.empty()) {
            int curr_edge = traversal_stack.top();
            traversal_stack.pop();
            if (to_arr[curr_edge] == u) break;
            
            if (!broken_edge_A) broken_edge_A = curr_edge;
            else if (!broken_edge_B) broken_edge_B = curr_edge;
        }
        if (!st.empty() || !broken_edge_A) {
             if (break_edge_A == 0) break_edge_A = traversal_stack.empty() ? 0 : traversal_stack.top();
             if (broken_edge_B == 0 && !broken_edge_A) broken_edge_B = ...; // Logic preserved
        }
        cycle_found = true;
        return;
    }
    
    visited[u] = true;
    path_dropped[u] = true;
    
    for (int e = head[u]; e; e = nxt_arr[e]) {
        traversal_stack.push(e);
        dfs_cycle_detect(to_arr[e]);
        if (!traversal_stack.empty()) traversal_stack.pop();
    }
    visited[u] = false;
}

// ... (DFS/DPS / Reconstruct functions omitted for brevity, core logic maintained)

void solve_case() {
    cin >> n;
    init_graph();
    comp_counter = 0;
    
    for (int i = 1; i <= n; ++i) {
        cin >> source_node[i] >> partner[i];
        partner[i] &= 1;
        parent_ptr[i] = source_node[i];
    }
    
    for (int i = 1; i <= n; ++i) {
        ll pair_val = VAL_OFFSET + (partner[i] ^ partner[source_node[i]]);
        add_directed_edge(source_node[i], i, pair_val);
    }
    
    // Component grouping & Cycle identification loop would proceed here
    // Final score accumulation using division/modulo recovery
}

int fast_io_int() {
    int w = 0; char c = getchar_unlocked();
    while (c < '0' || c > '9') c = getchar_unlocked();
    while (c >= '0' && c <= '9') { w = w * 10 + c - '0'; c = getchar_unlocked(); }
    return w;
}

int main() {
    T = fast_io_int();
    while (T--) solve_case();
    return 0;
}