#1083852 (C++17) No.686 Uncertain LIS

• 問題: No.686 Uncertain LIS
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:05:05
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 7,030 bytes
• コンパイル時間: 530 ms
• コンパイル使用メモリ: 78,520 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2025-05-14 13:06:51
• 合計ジャッジ時間: 3,342 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
other	AC * 8 WA * 28

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Using a vector to represent the segment tree. 
// The tree nodes are indexed starting from 1. tree[1] is the root.
// Left child of node `k` is `2*k`, right child is `2*k + 1`.
vector<int> tree; 

// The maximum coordinate value that the segment tree needs to cover. 
// The tree will represent the range [1, max_coord_val].
int max_coord_val; 

/**
 * @brief Updates the value at a specific index in the segment tree.
 * The update rule is to take the maximum of the current value and the new value.
 * This is because we are interested in the maximum LIS length ending with a value corresponding to the index.
 * 
 * @param node The index of the current node in the `tree` vector (1-based).
 * @param start The starting coordinate of the range covered by the current node.
 * @param end The ending coordinate of the range covered by the current node.
 * @param idx The coordinate (index) to update (1-based). This corresponds to L_i.
 * @param val The new value (dp_i) to potentially update with.
 */
void update(int node, int start, int end, int idx, int val) {
    // Base case: If the current node represents the single point `idx`.
    if (start == end) {
        // Update the value at this leaf node by taking the maximum.
        tree[node] = max(tree[node], val);
        return;
    }
    
    // Calculate the midpoint to decide whether to go left or right.
    int mid = start + (end - start) / 2;
    // If the index `idx` is in the left half of the current range.
    if (idx <= mid) {
        // Recurse down to the left child (node * 2).
        update(2 * node, start, mid, idx, val);
    } else { // Otherwise, the index `idx` is in the right half.
        // Recurse down to the right child (node * 2 + 1).
        update(2 * node + 1, mid + 1, end, idx, val);
    }
    
    // After updating a child node, update the current node's value.
    // The value of an internal node is the maximum of its children's values.
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

/**
 * @brief Queries the maximum value in a given range [l, r] (inclusive) in the segment tree.
 * 
 * @param node The index of the current node in the `tree` vector (1-based).
 * @param start The starting coordinate of the range covered by the current node.
 * @param end The ending coordinate of the range covered by the current node.
 * @param l The starting coordinate of the query range (1-based).
 * @param r The ending coordinate of the query range (1-based).
 * @return The maximum value found in the segment tree within the range [l, r]. Returns 0 if the range is empty or invalid.
 */
int query(int node, int start, int end, int l, int r) {
    // If the query range [l, r] is invalid (e.g., l > r), return 0.
    // This handles edge cases like querying range [1, 0] when R_i = 1.
    if (l > r) {
        return 0;
    }

    // If the query range is completely outside the node's range [start, end], return 0.
    // 0 is the identity element for max operation on non-negative LIS lengths.
    if (r < start || end < l) {
        return 0; 
    }
    
    // If the node's range [start, end] is completely contained within the query range [l, r],
    // return the value stored in this node, as it represents the maximum in its covered range.
    if (l <= start && end <= r) {
        return tree[node];
    }
    
    // Otherwise, the node's range partially overlaps the query range.
    // We need to recurse down to the children nodes.
    int mid = start + (end - start) / 2;
    // Query the left child for the intersection of its range and the query range.
    int p1 = query(2 * node, start, mid, l, r);
    // Query the right child for the intersection of its range and the query range.
    int p2 = query(2 * node + 1, mid + 1, end, l, r);
    
    // Return the maximum of the results obtained from the children.
    return max(p1, p2);
}


int main() {
    // Use fast I/O operations for potentially large inputs.
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N; // Number of elements in the sequence
    cin >> N;

    // Store pairs (L_i, R_i) for each index i.
    vector<pair<int, int>> ranges(N);
    int current_max_coord = 0; // Track the maximum coordinate value encountered in L_i and R_i.
    for (int i = 0; i < N; ++i) {
        cin >> ranges[i].first >> ranges[i].second;
        // The segment tree needs to cover all possible values of L_i and R_i.
        // We update based on L_i and query based on R_i.
        current_max_coord = max(current_max_coord, ranges[i].first);
        current_max_coord = max(current_max_coord, ranges[i].second);
    }
    
    // Handle the edge case N=0, although constraints state N >= 1.
    if (N == 0) {
        cout << 0 << endl;
        return 0;
    }
    // Since N >= 1 and L_i >= 1, the current_max_coord will be at least 1.

    // Set the maximum coordinate value the segment tree will cover. The range is [1, max_coord_val].
    max_coord_val = current_max_coord; 
    
    // Allocate the segment tree vector. The size needs to be roughly 4 times max_coord_val
    // to accommodate a full binary tree structure. Initialize all node values to 0.
    tree.assign(4 * max_coord_val + 4, 0); // Using slightly more space for safety margin.

    int overall_max_lis = 0; // Stores the overall maximum LIS length found.

    // Process each element constraint from i = 0 to N-1.
    for (int i = 0; i < N; ++i) {
        int L_i = ranges[i].first; // Lower bound for A_i
        int R_i = ranges[i].second; // Upper bound for A_i
        
        // The core DP logic: Find the maximum length of an increasing subsequence ending before index i,
        // say at index j < i, such that it's possible to choose A_j < A_i.
        // This is possible if L_j < R_i.
        // We query the segment tree for the maximum `dp[j]` value associated with any `L_j` such that `L_j` is in [1, R_i - 1].
        // The segment tree stores `dp[j]` values at indices corresponding to `L_j`.
        // The query `query(1, 1, max_coord_val, 1, R_i - 1)` finds this maximum value.
        int max_prev_dp = query(1, 1, max_coord_val, 1, R_i - 1);
        
        // Calculate dp[i], the maximum LIS length ending at index i.
        // It's 1 (for the element A_i itself) plus the maximum length found from previous elements.
        int dp_i = 1 + max_prev_dp;
        
        // Store this result `dp_i` in the segment tree. The value `dp_i` is associated with the coordinate `L_i`.
        // This information will be used for subsequent calculations of dp values.
        // The update function ensures we store the maximum dp value found so far for coordinate L_i.
        update(1, 1, max_coord_val, L_i, dp_i);
        
        // Keep track of the overall maximum LIS length found across all `dp_i`.
        overall_max_lis = max(overall_max_lis, dp_i);
    }

    // Output the final result.
    cout << overall_max_lis << endl;

    return 0;
}