結果

問題 No.1270 Range Arrange Query
ユーザー qwewe
提出日時 2025-05-14 13:20:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,091 bytes
コンパイル時間 1,116 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-14 13:22:18
合計ジャッジ時間 10,069 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const long long INF = 4e18; // Sufficiently large infinity (max N*N inversions or N*M costs)

// Fenwick tree (BIT)
struct FenwickTree {
    std::vector<int> bit;
    int size;

    FenwickTree(int n) : size(n), bit(n + 1, 0) {}

    void update(int idx, int delta) { // 1-indexed
        for (; idx <= size; idx += idx & -idx) {
            bit[idx] += delta;
        }
    }

    int query(int idx) { // 1-indexed, prefix sum up to idx
        int sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += bit[idx];
        }
        return sum;
    }

    // Query sum in [val_l, val_r]
    int query_val_range(int val_l, int val_r) { 
        if (val_l > val_r) return 0;
        return query(val_r) - query(val_l - 1);
    }
    
    void reset() { // Reset BIT to all zeros
        std::fill(bit.begin(), bit.end(), 0);
    }
};


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N_val, Q_val; // Using _val to avoid conflict with N in problem description
    std::cin >> N_val >> Q_val;

    std::vector<int> A(N_val);
    for (int i = 0; i < N_val; ++i) {
        std::cin >> A[i];
    }

    FenwickTree ft(N_val); // Max value is N_val
    
    std::vector<int> cost_val_arr(N_val + 1);
    std::vector<long long> dp_prev(N_val + 1);
    std::vector<long long> dp_curr(N_val + 1);
    std::vector<long long> min_so_far(N_val + 1);
    
    std::vector<int> freq_L(N_val + 1, 0);
    std::vector<int> freq_R(N_val + 1, 0);


    for (int q_idx = 0; q_idx < Q_val; ++q_idx) {
        int l_query, r_query;
        std::cin >> l_query >> r_query;
        // Adjust to 0-indexed
        int l_idx = l_query - 1;
        int r_idx = r_query - 1;

        long long fixed_inversions = 0;

        // 1. Inversions in A[0...l_idx-1]
        ft.reset();
        for (int i = 0; i < l_idx; ++i) {
            fixed_inversions += ft.query_val_range(A[i] + 1, N_val);
            ft.update(A[i], 1);
        }
        
        // 2. Inversions in A[r_idx+1...N_val-1]
        ft.reset();
        for (int i = r_idx + 1; i < N_val; ++i) {
            fixed_inversions += ft.query_val_range(A[i] + 1, N_val);
            ft.update(A[i], 1);
        }

        // 3. Inversions (A[i], A[j]) where i < l_idx and j > r_idx
        ft.reset();
        for (int i = r_idx + 1; i < N_val; ++i) {
            ft.update(A[i], 1);
        }
        for (int i = 0; i < l_idx; ++i) {
            if (A[i] > 1) {
                 fixed_inversions += ft.query(A[i] - 1);
            }
        }

        // Calculate Cost(v) for v = 1...N_val
        // Cost(v) = (count i < l_idx: A[i] > v) + (count j > r_idx: v > A[j])
        
        // Optimize freq_L/R fill if N_val is large vs l_idx / (N_val-1-r_idx)
        // current fill is ok as they are cleared first
        std::fill(freq_L.begin(), freq_L.end(), 0);
        std::fill(freq_R.begin(), freq_R.end(), 0);

        for (int i = 0; i < l_idx; ++i) {
            freq_L[A[i]]++;
        }
        for (int i = r_idx + 1; i < N_val; ++i) {
            freq_R[A[i]]++;
        }
        
        // Calculate first part of Cost(v): (count i < l_idx: A[i] > v)
        // cost_val_arr[v] = sum_{x=v+1 to N_val} freq_L[x]
        cost_val_arr[N_val] = 0; 
        int current_sum_L = 0;
        for(int v = N_val - 1; v >= 1; --v) {
            current_sum_L += freq_L[v+1];
            cost_val_arr[v] = current_sum_L;
        }
        
        // Add second part of Cost(v): (count j > r_idx: v > A[j])
        // sum_{x=1 to v-1} freq_R[x]
        int current_sum_R = 0;
        // For v=1, sum_{x=1 to 0} is 0. cost_val_arr[1] correctly gets current_sum_R=0 added.
        for (int v = 1; v <= N_val; ++v) {
            if (v > 1) current_sum_R += freq_R[v-1];
            cost_val_arr[v] += current_sum_R;
        }
        
        int M = r_idx - l_idx + 1;
        // M is always >= 1 because 1 <= l_query <= r_query <= N_val

        // DP part
        for (int val = 1; val <= N_val; ++val) {
            dp_prev[val] = cost_val_arr[val];
        }

        for (int k = 2; k <= M; ++k) {
            min_so_far[1] = dp_prev[1];
            for (int val = 2; val <= N_val; ++val) {
                min_so_far[val] = std::min(min_so_far[val-1], dp_prev[val]);
            }
            for (int val = 1; val <= N_val; ++val) {
                if (min_so_far[val] >= INF) { 
                    dp_curr[val] = INF;
                } else {
                    dp_curr[val] = cost_val_arr[val] + min_so_far[val];
                }
            }
            // Use std::swap or copy, std::vector assignment is a copy
            dp_prev = dp_curr; 
        }

        long long min_sum_cost_for_range = INF;
        for (int val = 1; val <= N_val; ++val) {
            min_sum_cost_for_range = std::min(min_sum_cost_for_range, dp_prev[val]);
        }
        if (M==0) min_sum_cost_for_range = 0; // Should not happen with M >= 1

        std::cout << fixed_inversions + min_sum_cost_for_range << "\n";
    }

    return 0;
}
0