#1084031 (C++17) No.1838 Modulo Straight

• 問題: No.1838 Modulo Straight
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:15:02
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,688 bytes
• コンパイル時間: 676 ms
• コンパイル使用メモリ: 77,124 KB
• 実行使用メモリ: 18,804 KB
• 最終ジャッジ日時: 2025-05-14 13:16:21
• 合計ジャッジ時間: 5,659 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 8 TLE * 1 -- * 29

ソースコード

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

// Fenwick tree (BIT) implementation
// Uses 1-based indexing internally
// Template allows using different integer types (e.g., int, long long) for counts
template <typename T>
struct FenwickTree {
    int size;          // The maximum index the BIT supports (size = N for values 1 to N)
    std::vector<T> tree; // The BIT array itself

    // Initialize BIT with size n (supports indices 1 to n)
    FenwickTree(int n) : size(n), tree(n + 1, 0) {}

    // Add delta to element at index idx
    // Time complexity: O(log size)
    void update(int idx, T delta) {
        // Index must be positive and within bounds
        if (idx <= 0 || idx > size) return; // Or throw an error for invalid index
        
        // Standard BIT update logic
        for (; idx <= size; idx += idx & -idx) {
            tree[idx] += delta;
        }
    }

    // Query prefix sum up to index idx (sum of elements from 1 to idx)
    // Time complexity: O(log size)
    T query(int idx) {
        T sum = 0;
        // Clamp idx to valid range [0, size]. Query at 0 or less should yield 0.
        idx = std::max(0, std::min(idx, size)); 
        
        // Standard BIT query logic
        for (; idx > 0; idx -= idx & -idx) {
            sum += tree[idx];
        }
        return sum;
    }
    
    // Query sum in range [l, r] (sum of elements from index l to r, inclusive)
    // Time complexity: O(log size)
    T query_range(int l, int r) {
         // If range is invalid, return 0
         if (l > r) return 0;
         // Clamp range boundaries to valid indices [1, size]
        l = std::max(1, l);
        r = std::min(size, r);
        // If after clamping range is still invalid (e.g., l > r), return 0
        if (l > r) return 0; 
        
        // Compute range sum using prefix sums
        // Note: T should support subtraction and potentially negative values if delta can be negative.
        // For inversion counting, delta is usually +1, so T=int or long long is fine.
        return query(r) - query(l - 1);
    }
};

// Function to count inversions in a vector p
// Uses Fenwick Tree. Values in p represent target positions and must be in range [1, N_max_val].
// N_max_val is the maximum possible value in p, which is MK in this problem.
// Returns the total number of inversions as a long long.
// Time complexity: O(n log N_max_val), where n is the size of p.
long long count_inversions(const std::vector<int>& p, int N_max_val) { 
    int n = p.size();
    if (n == 0) return 0LL; // No inversions in an empty sequence
    
    // Initialize Fenwick Tree with size N_max_val
    FenwickTree<int> bit(N_max_val);
    long long inversions = 0; // Use long long for inversion count, can exceed 2^31
    
    // Iterate through the sequence p from left to right
    for (int i = 0; i < n; ++i) {
        // The value p[i] is the target position for the element originally at index i.
        // Check if p[i] is within the expected range [1, N_max_val].
        if (p[i] <= 0 || p[i] > N_max_val) {
           // This indicates a potential logic error or invalid input.
           // In a contest setting, may need specific error handling or assume validity.
           // For safety, you could skip this element or throw an exception.
           // Let's assume p[i] is always valid based on problem logic.
        }

        // An inversion involving p[i] occurs with an element p[j] where j < i and p[j] > p[i].
        // We count how many elements processed so far (indices j < i) have a value p[j] greater than p[i].
        // This is achieved by querying the sum in the range [p[i] + 1, N_max_val] in the BIT.
        // The BIT stores counts of elements seen so far at their respective positions.
        inversions += bit.query_range(p[i] + 1, N_max_val);

        // After processing p[i], mark its position p[i] as seen in the BIT by adding 1.
        bit.update(p[i], 1);
    }
    return inversions;
}


int main() {
    // Use faster I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int M;
    long long K_ll; // Read K as long long to potentially handle larger values if needed, although problem constraints imply K fits in int.
    std::cin >> M >> K_ll;
    int K = (int)K_ll; // Cast K to int. Max MK is 4e5, so K is at most 4e5.
    
    // Total number of elements in the sequence A
    int N = M * K;

    // Check constraints: M >= 2, MK >= 2. So N >= 2.
    if (N <= 0) { // Defensive check, should not happen based on constraints
         std::cout << 0 << std::endl;
         return 0;
    }

    // Read the input sequence A
    std::vector<int> A(N);
    
    // To determine the target position for each element A[i], we need to know
    // its value v = A[i] and which occurrence (k-th) of value v it is.
    std::vector<int> occurrence_counter(M, 0); // Counter for each value 0 to M-1
    std::vector<int> element_k(N); // Stores the k-th occurrence number (0-based) for element A[i]

    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
        // Check if input value A[i] is valid (0 <= A[i] < M)
        if (A[i] < 0 || A[i] >= M) {
             // Handle error: Invalid input value. Exit or provide error message.
             return 1; // Example: exit with non-zero status
        }
        // Record that this element A[i] is the k-th occurrence (0-based) of its value.
        element_k[i] = occurrence_counter[A[i]]++;
    }

    // Variable to store the minimum number of inversions found across all possible target sequences T_x
    long long min_inversions = -1; // Initialize with -1 to indicate no value found yet

    // This vector will store the computed target positions P_x for a given x
    std::vector<int> target_indices(N);
    
    // Iterate through all possible starting values x for the target sequence T_x
    for (int x = 0; x < M; ++x) {
        // For the current x, determine the target position for each element A[i]
        for (int i = 0; i < N; ++i) {
             int v = A[i];            // Value of the element
             int k = element_k[i];    // Its 0-based occurrence number

             // Calculate the base target position (smallest position for value v in T_x)
             // Formula derived: j = v - x + 1 (mod M). Adjust for 1-based indexing and 0 result.
             long long base_val_mod = (long long)v - x + 1; // Use long long for intermediate calculation
             // Compute modulo M correctly for potentially negative results of v-x+1
             int j_base = (base_val_mod % M + M) % M; 
             // If modulo result is 0, the position corresponds to M in 1-based indexing
             if (j_base == 0) {
                  j_base = M; 
             }
            
             // The target position for the k-th occurrence (0-based k) is j_base + k * M
             // Use long long for k * M part to prevent potential overflow if M*K is large, although N <= 4e5 fits int.
             target_indices[i] = j_base + (long long)k * M; 
        }
        
        // Calculate the number of inversions for the sequence of target positions P_x
        // The maximum value in target_indices is N = MK.
        long long current_inversions = count_inversions(target_indices, N);

        // Update the minimum inversion count if the current one is smaller or if it's the first one calculated
        if (min_inversions == -1 || current_inversions < min_inversions) {
            min_inversions = current_inversions;
        }
    }

    // Output the minimum number of inversions found
    std::cout << min_inversions << std::endl;

    return 0;
}