/** * JOI 2016/2017 Final Round - Task 5: Rope * * Solution Logic: * 1. The problem reduces to finding a pivot k such that the cost is minimized. * 2. We solve for the "Left Alignment" case and then reverse the rope for the "Right Alignment" case. * 3. We use a threshold to distinguish between "Heavy" and "Light" colors. * - Heavy Colors: Compute exact cost for all k using prefix sums. O(N log N) per color. * - Light Colors: Identify ranges of k where the count increases using the number theory * property of the folding. Use a sweep-line with RMQ to find the min cost. */ #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; const int INF = 1e9; int N, M; vector<int> C; // Colors vector<int> final_ans; // Sparse Table for O(1) Range Minimum Query struct SparseTable { vector<vector<int>> st; vector<int> log_table; int n; void build(const vector<int>& arr) { n = arr.size(); log_table.resize(n + 1); log_table[1] = 0; for (int i = 2; i <= n; i++) log_table[i] = log_table[i / 2] + 1; int K = log_table[n]; st.assign(n, vector<int>(K + 1)); for (int i = 0; i < n; i++) st[i][0] = arr[i]; for (int j = 1; j <= K; j++) for (int i = 0; i + (1 << j) <= n; i++) st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } int query(int L, int R) { if (L > R) return INF; int j = log_table[R - L + 1]; return min(st[L][j], st[R - (1 << j) + 1][j]); } }; void solve_pass(const vector<int>& current_colors) { // 1. Calculate Total Size of Left Pile for each k [1, N-1] // The Left Pile for pivot k contains indices in [1, k], [2k+1, 3k], [4k+1, 5k], ... vector<int> total_size(N, 0); // 0-based index k corresponds to pivot k for (int k = 1; k < N; ++k) { int count = 0; for (int m = 0; ; m += 2) { int l = m * k + 1; int r = (m + 1) * k; if (l > N) break; r = min(r, N); count += (r - l + 1); } total_size[k] = count; } // Build RMQ on total_size to quickly query min(Size) in ranges SparseTable rmq; rmq.build(total_size); // Group positions by color vector<vector<int>> positions(M + 1); for (int i = 0; i < N; ++i) { positions[current_colors[i]].push_back(i + 1); // Store 1-based indices } // Threshold tuning: B ~ sqrt(N) * log(N) is usually optimal or just sqrt(N). // With N=1,000,000, sqrt(N)=1000. // Heavy colors approach takes O(N log N). Light takes O(Freq * sqrt(N)). // A threshold of ~3000 balances the two well. const int THRESHOLD = 3000; for (int c = 1; c <= M; ++c) { if (positions[c].empty()) continue; if (positions[c].size() > THRESHOLD) { // --- HEAVY COLOR STRATEGY --- // Iterate all k. Use prefix sums to count occurrences efficiently. vector<int> pref(N + 1, 0); for (int p : positions[c]) pref[p] = 1; for (int i = 1; i <= N; ++i) pref[i] += pref[i - 1]; for (int k = 1; k < N; ++k) { int cnt = 0; // Sum segments [1, k], [2k+1, 3k], ... for (int m = 0; ; m += 2) { int l = m * k + 1; int r = (m + 1) * k; if (l > N) break; r = min(r, N); cnt += (pref[r] - pref[l - 1]); } final_ans[c] = min(final_ans[c], total_size[k] - cnt); } } else { // --- LIGHT COLOR STRATEGY --- // A position p contributes to pivot k if floor((p-1)/k) is Even. // This creates ranges of k. We collect these ranges and sweep. vector<pair<int, int>> events; events.reserve(positions[c].size() * 100); // Heuristic reservation for (int p : positions[c]) { int X = p - 1; // Case q=0: k > X. Range [X+1, N-1] if (X + 1 < N) { events.push_back({X + 1, 1}); events.push_back({N, -1}); } // Iterate even q >= 2 // Valid k range for quotient q is roughly (X/(q+1), X/q] for (int q = 2; ; q += 2) { int R = X / q; if (R == 0) break; // k must be >= 1 int L = X / (q + 1) + 1; // Intersect with valid pivots [1, N-1] int r_bound = min(N - 1, R); int l_bound = max(1, L); if (l_bound <= r_bound) { events.push_back({l_bound, 1}); events.push_back({r_bound + 1, -1}); } if (L > R) continue; // Should not happen with logic but safe check } } if (events.empty()) { final_ans[c] = min(final_ans[c], rmq.query(1, N - 1)); continue; } sort(events.begin(), events.end()); int current_gain = 0; int prev_k = 1; // Sweep line for (size_t i = 0; i < events.size(); ) { int curr_k = events[i].first; // Query the minimum Size for the range where gain was constant if (curr_k > prev_k) { int min_s = rmq.query(prev_k, min(curr_k - 1, N - 1)); if (min_s != INF) { final_ans[c] = min(final_ans[c], min_s - current_gain); } } // Update gain while (i < events.size() && events[i].first == curr_k) { current_gain += events[i].second; i++; } prev_k = curr_k; } // Handle tail [Last Event, N-1] if (prev_k < N) { int min_s = rmq.query(prev_k, N - 1); if (min_s != INF) { final_ans[c] = min(final_ans[c], min_s - current_gain); } } } } } int main() { // Optimize I/O operations ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N >> M; C.resize(N); for (int i = 0; i < N; ++i) cin >> C[i]; final_ans.assign(M + 1, INF); // Pass 1: Consider "Left Aligned" folding patterns solve_pass(C); // Pass 2: Consider "Right Aligned" folding patterns (equivalent to Left Aligned on reversed rope) vector<int> C_rev = C; reverse(C_rev.begin(), C_rev.end()); solve_pass(C_rev); for (int c = 1; c <= M; ++c) { cout << final_ans[c] << "\n"; } return 0; }