fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. // Kích thước khối cho thuật toán chia căn
  6. const int BLOCK_SIZE = 400; 
  7. // Số phần tử tối đa
  8. const int MAXN = 3e5 + 5; 
  9. // Giá trị vô cùng lớn
  10. const int INF = 1e9;
  11.  
  12. // Cấu trúc để lưu một truy vấn
  13. struct Query {
  14.     int l, r; // [l, r] là đoạn truy vấn
  15.     int id;   // ID ban đầu của truy vấn để trả về kết quả đúng thứ tự
  16. };
  17.  
  18. // --- Biến toàn cục ---
  19. int n, q; // Số phần tử của mảng và số lượng truy vấn
  20.  
  21. int original_array[MAXN]; // Mảng ban đầu
  22. int sorted_values[MAXN];  // Mảng chứa các giá trị đã được sắp xếp
  23. int rank_in_sorted[MAXN]; // rank_in_sorted[i] = vị trí của original_array[i] trong mảng đã sắp xếp
  24. int ans[MAXN];            // Mảng lưu kết quả cho các truy vấn
  25.  
  26. // Mảng cho cấu trúc dữ liệu danh sách liên kết đôi (trên các giá trị đã sắp xếp)
  27. int next_val[MAXN];
  28. int prev_val[MAXN];
  29.  
  30. // Mảng DP: dp[len][start] = kết quả cho đoạn [start, start + len - 1]
  31. int dp[BLOCK_SIZE + 5][MAXN]; 
  32. // Mảng f: f[i] dùng để tính trước kết quả cho phần bên phải của block
  33. int f[MAXN];
  34.  
  35. // Vector chứa các truy vấn được nhóm theo block
  36. vector<Query> queries_by_block[MAXN / BLOCK_SIZE + 5];
  37.  
  38. // --- Hàm chức năng ---
  39.  
  40. // Hàm so sánh để sắp xếp các truy vấn trong một block
  41. // Sắp xếp theo r giảm dần để tối ưu việc di chuyển con trỏ
  42. bool compareQueries(const Query& a, const Query& b) {
  43.     return a.r > b.r;
  44. }
  45.  
  46. // Hàm "thêm" một phần tử vào cấu trúc dữ liệu (danh sách liên kết đôi)
  47. // và trả về chênh lệch nhỏ nhất mới được tạo ra
  48. int addElement(int val_rank) {
  49.     int min_diff = INF;
  50.     // Chênh lệch với phần tử đứng trước nó trong dãy đã sắp xếp
  51.     if (prev_val[val_rank] >= 1) {
  52.         min_diff = min(min_diff, sorted_values[val_rank] - sorted_values[prev_val[val_rank]]);
  53.     }
  54.     // Chênh lệch với phần tử đứng sau nó trong dãy đã sắp xếp
  55.     if (next_val[val_rank] <= n) {
  56.         min_diff = min(min_diff, sorted_values[next_val[val_rank]] - sorted_values[val_rank]);
  57.     }
  58.     // Cập nhật con trỏ của các phần tử lân cận để trỏ đến phần tử vừa thêm
  59.     next_val[prev_val[val_rank]] = val_rank;
  60.     prev_val[next_val[val_rank]] = val_rank;
  61.     return min_diff;
  62. }
  63.  
  64. // Hàm "xóa" một phần tử khỏi cấu trúc dữ liệu
  65. void removeElement(int val_rank) {
  66.     // Nối phần tử trước và sau lại với nhau
  67.     next_val[prev_val[val_rank]] = next_val[val_rank];
  68.     prev_val[next_val[val_rank]] = prev_val[val_rank];
  69. }
  70.  
  71. int main() {
  72.     ios::sync_with_stdio(0);
  73.     cin.tie(0);
  74.     cout.tie(0);
  75.  
  76.     // --- Đọc dữ liệu và tiền xử lý ---
  77.     cin >> n;
  78.     for (int i = 1; i <= n; i++) {
  79.         cin >> original_array[i];
  80.         sorted_values[i] = original_array[i];
  81.     }
  82.  
  83.     // Sắp xếp các giá trị để tìm chênh lệch
  84.     sort(sorted_values + 1, sorted_values + n + 1);
  85.  
  86.     // Thêm các giá trị biên để tránh xử lý các trường hợp đặc biệt
  87.     sorted_values[0] = -INF;
  88.     sorted_values[n + 1] = INF * 2;
  89.  
  90.     // Map để xử lý các giá trị trùng lặp
  91.     // Gán cho mỗi phần tử original_array[i] một "rank" duy nhất trong mảng đã sắp xếp
  92.     map<int, int> duplicate_counter;
  93.     for (int i = 1; i <= n; i++) {
  94.         int base_rank = lower_bound(sorted_values + 1, sorted_values + n + 1, original_array[i]) - sorted_values;
  95.         rank_in_sorted[i] = base_rank + (duplicate_counter[base_rank]++);
  96.     }
  97.  
  98.     // --- Đọc và phân loại truy vấn vào các block ---
  99.     cin >> q;
  100.     for (int i = 1; i <= q; i++) {
  101.         int l, r;
  102.         cin >> l >> r;
  103.         int block_id = (l - 1) / BLOCK_SIZE;
  104.         queries_by_block[block_id].push_back({l, r, i});
  105.     }
  106.  
  107.     // Sắp xếp các truy vấn trong mỗi block
  108.     for (int i = 0; i <= n / BLOCK_SIZE; i++) {
  109.         sort(queries_by_block[i].begin(), queries_by_block[i].end(), compareQueries);
  110.     }
  111.  
  112.     // --- Quy hoạch động cho các truy vấn ngắn ---
  113.     for (int len = 1; len <= BLOCK_SIZE; len++) {
  114.         if (len == 1) {
  115.             for (int i = 1; i <= n; i++) dp[len][i] = INF;
  116.         } else {
  117.             for (int i = 1; i <= n - len + 1; i++) {
  118.                 // Kết quả cho đoạn dài `len` tại `i` được tính từ:
  119.                 // 1. Kết quả của đoạn dài `len-1` tại `i`
  120.                 // 2. Kết quả của đoạn dài `len-1` tại `i+1`
  121.                 // 3. Chênh lệch giữa phần tử đầu và cuối của đoạn hiện tại
  122.                 dp[len][i] = min({dp[len - 1][i], dp[len - 1][i + 1], abs(original_array[i] - original_array[i + len - 1])});
  123.             }
  124.         }
  125.     }
  126.  
  127.     // --- Xử lý các truy vấn theo từng block ---
  128.     for (int block_id = 0; block_id * BLOCK_SIZE < n; block_id++) {
  129.         int block_start = block_id * BLOCK_SIZE + 1;
  130.         int block_end = min(n, (block_id + 1) * BLOCK_SIZE);
  131.         int current_r = n;
  132.  
  133.         // Khởi tạo danh sách liên kết đôi cho toàn bộ dải giá trị
  134.         for (int j = 0; j <= n + 1; j++) {
  135.             prev_val[j] = j - 1;
  136.             next_val[j] = j + 1;
  137.         }
  138.  
  139.         // Tạm thời "xóa" các phần tử không thuộc phạm vi [block_end, n]
  140.         // để chuẩn bị tính mảng f
  141.         for (int j = 1; j < block_end; j++) removeElement(rank_in_sorted[j]);
  142.  
  143.         // Tính trước mảng f[i] = min_diff trong đoạn [block_end, i]
  144.         f[block_end] = INF;
  145.         for (int j = block_end + 1; j <= n; j++) {
  146.             f[j] = min(f[j - 1], addElement(rank_in_sorted[j]));
  147.         }
  148.  
  149.         // Thêm lại các phần tử của block hiện tại để chuẩn bị xử lý truy vấn
  150.         for (int j = block_end - 1; j >= block_start; j--) {
  151.             addElement(rank_in_sorted[j]);
  152.         }
  153.  
  154.         // Xử lý từng truy vấn trong block hiện tại
  155.         for (const auto& query : queries_by_block[block_id]) {
  156.             // Trường hợp 1: Truy vấn ngắn, đã có kết quả từ DP
  157.             if (query.r - query.l + 1 <= BLOCK_SIZE) {
  158.                 ans[query.id] = dp[query.r - query.l + 1][query.l];
  159.                 continue;
  160.             }
  161.  
  162.             // Trường hợp 2: Truy vấn dài, l nằm trong block, r nằm ngoài
  163.             // Kết quả ban đầu là min_diff trong [block_end, query.r]
  164.             ans[query.id] = f[query.r];
  165.  
  166.             // Di chuyển con trỏ `current_r` về `query.r`
  167.             // Xóa các phần tử từ (current_r, query.r] khỏi cấu trúc
  168.             while (current_r > query.r) {
  169.                 removeElement(rank_in_sorted[current_r--]);
  170.             }
  171.  
  172.             // Xóa tạm thời các phần tử bên trái của block
  173.             for (int j = block_start; j < block_end; j++) {
  174.                 removeElement(rank_in_sorted[j]);
  175.             }
  176.  
  177.             // Thêm các phần tử từ [query.l, block_end - 1] vào và cập nhật kết quả
  178.             for (int j = block_end - 1; j >= query.l; j--) {
  179.                 ans[query.id] = min(ans[query.id], addElement(rank_in_sorted[j]));
  180.             }
  181.  
  182.             // Khôi phục lại trạng thái cho các phần tử bên trái block cho truy vấn tiếp theo
  183.             for (int j = query.l - 1; j >= block_start; j--) {
  184.                 addElement(rank_in_sorted[j]);
  185.             }
  186.         }
  187.     }
  188.  
  189.     // --- In kết quả ---
  190.     for (int i = 1; i <= q; i++) {
  191.         cout << ans[i] << "\n";
  192.     }
  193.  
  194.     return 0;
  195. }
Success #stdin #stdout 0.01s 5588KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/t5D2ET
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!