fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Giải thuật offline để trả về hiệu tuyệt đối nhỏ nhất giữa hai số trong mỗi truy vấn trên mảng con
  5. // Sử dụng kỹ thuật Mo’s algorithm cải tiến với phân mảnh theo block và linked-list động
  6.  
  7. struct Query {
  8.     int left;   // vị trí trái của truy vấn
  9.     int right;  // vị trí phải của truy vấn
  10.     int index;  // chỉ số truy vấn để trả kết quả sau
  11. };
  12.  
  13. // Hằng số
  14. constexpr int MAXN = 300000 + 5;
  15. constexpr int BLOCK_SIZE = 400;
  16. constexpr int INF = 1e9;
  17.  
  18. // Mảng dữ liệu chính
  19. int nextPos[MAXN];       // nextPos[i]: chỉ số phần tử tiếp theo trong liên kết
  20. int prevPos[MAXN];       // prevPos[i]: chỉ số phần tử trước đó trong liên kết
  21. int compressed[MAXN];    // giá trị mảng đã nén tọa độ (với trùng lặp xử lý offset)
  22. int original[MAXN];      // giá trị gốc ban đầu (dùng cho tính toán độ khác nhau)
  23. int answer[MAXN];        // kết quả cho mỗi truy vấn
  24. int dp[BLOCK_SIZE + 5][MAXN];  // bảng dp tiền tính cho các đoạn ngắn (độ dài <= BLOCK_SIZE)
  25. int blockMin[MAXN];      // giá trị tối ưu khi xử lý theo block
  26. map<int,int> freqMap;    // hỗ trợ đếm số lần trùng giá trị trong nén tọa độ
  27. vector<Query> queriesByBlock[MAXN / BLOCK_SIZE + 5];  // nhóm truy vấn theo block của trái
  28.  
  29. // So sánh để sắp xếp truy vấn giảm dần theo right
  30. bool compareByRightDesc(const Query &a, const Query &b) {
  31.     return a.right > b.right;
  32. }
  33.  
  34. // Thêm vị trí x vào tập đang xét (linked list động), trả về hiệu nhỏ nhất với láng giềng
  35. int insertPosition(int x) {
  36.     int best = INF;
  37.     // Kiểm tra phần tử trước
  38.     if (prevPos[x] >= 1) {
  39.         best = min(best, original[x] - original[prevPos[x]]);
  40.     }
  41.     // Kiểm tra phần tử sau
  42.     if (nextPos[x] <= MAXN - 1) {
  43.         best = min(best, original[nextPos[x]] - original[x]);
  44.     }
  45.     // Cập nhật liên kết
  46.     nextPos[prevPos[x]] = x;
  47.     prevPos[nextPos[x]] = x;
  48.     return best;
  49. }
  50.  
  51. // Xóa vị trí x khỏi tập đang xét
  52. void removePosition(int x) {
  53.     nextPos[prevPos[x]] = nextPos[x];
  54.     prevPos[nextPos[x]] = prevPos[x];
  55. }
  56.  
  57. int main() {
  58.     ios::sync_with_stdio(false);
  59.     cin.tie(nullptr);
  60.  
  61.     int n;
  62.     cin >> n;  // đọc số phần tử mảng
  63.  
  64.     // Đọc và lưu giá trị ban đầu
  65.     for (int i = 1; i <= n; ++i) {
  66.         cin >> compressed[i];
  67.         original[i] = compressed[i];
  68.     }
  69.  
  70.     // Nén tọa độ: sort và gán lại chỉ số
  71.     sort(original + 1, original + n + 1);
  72.     original[0] = -INF;
  73.     original[n + 1] = INF;
  74.     for (int i = 1; i <= n; ++i) {
  75.         int rank = lower_bound(original + 1, original + n + 1, compressed[i]) - original;
  76.         compressed[i] = rank + (freqMap[rank]++);
  77.     }
  78.  
  79.     int q;
  80.     cin >> q;  // số truy vấn
  81.  
  82.     // Nhóm các truy vấn theo block của chỉ số trái
  83.     for (int i = 1; i <= q; ++i) {
  84.         int l, r;
  85.         cin >> l >> r;
  86.         int blockId = (l - 1) / BLOCK_SIZE;
  87.         queriesByBlock[blockId].push_back({l, r, i});
  88.     }
  89.  
  90.     // Sắp xếp truy vấn trong mỗi block giảm dần theo right
  91.     int numBlocks = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;
  92.     for (int b = 0; b < numBlocks; ++b) {
  93.         sort(queriesByBlock[b].begin(), queriesByBlock[b].end(), compareByRightDesc);
  94.     }
  95.  
  96.     // Tiền tính dp cho các đoạn ngắn độ dài <= BLOCK_SIZE
  97.     for (int len = 1; len <= min(BLOCK_SIZE, n); ++len) {
  98.         for (int start = 1; start + len - 1 <= n; ++start) {
  99.             if (len == 1) {
  100.                 dp[len][start] = INF;  // chỉ một phần tử, không có cặp
  101.             } else {
  102.                 dp[len][start] = min({
  103.                     dp[len - 1][start],
  104.                     dp[len - 1][start + 1],
  105.                     abs(compressed[start] - compressed[start + len - 1])
  106.                 });
  107.             }
  108.         }
  109.     }
  110.  
  111.     // Xử lý từng block
  112.     for (int b = 0; b < numBlocks; ++b) {
  113.         int leftBound = b * BLOCK_SIZE + 1;
  114.         int rightBound = min(n, (b + 1) * BLOCK_SIZE);
  115.  
  116.         // Khởi tạo linked list đầy đủ 0..n+1
  117.         for (int i = 0; i <= n + 1; ++i) {
  118.             prevPos[i] = i - 1;
  119.             nextPos[i] = i + 1;
  120.         }
  121.  
  122.         // Loại hết phần tử ngoài [1..rightBound]
  123.         for (int i = 1; i < leftBound; ++i) removePosition(compressed[i]);
  124.         for (int i = rightBound + 1; i <= n; ++i) removePosition(compressed[i]);
  125.  
  126.         // Tính blockMin: hiệu nhỏ nhất từ rightBound tới n
  127.         int currentMin = INF;
  128.         for (int i = rightBound + 1; i <= n; ++i) {
  129.             currentMin = min(currentMin, insertPosition(compressed[i]));
  130.             blockMin[i] = currentMin;
  131.         }
  132.  
  133.         // Duyệt các truy vấn trong block b
  134.         int ptr = n;
  135.         for (auto &query : queriesByBlock[b]) {
  136.             int l = query.left;
  137.             int r = query.right;
  138.  
  139.             // Nếu độ dài nhỏ, dùng dp sẵn
  140.             if (r - l + 1 <= BLOCK_SIZE) {
  141.                 answer[query.index] = dp[r - l + 1][l];
  142.                 continue;
  143.             }
  144.  
  145.             // Bắt đầu từ kết quả tiền tính
  146.             int res = blockMin[r];
  147.  
  148.             // Thu nhỏ ptr lại đúng r
  149.             while (ptr > r) {
  150.                 removePosition(compressed[ptr--]);
  151.             }
  152.  
  153.             // Loại các phần tử trong [leftBound..rightBound-1]
  154.             for (int i = leftBound; i < rightBound; ++i) removePosition(compressed[i]);
  155.  
  156.             // Thêm các phần tử từ r-1 xuống l và cập nhật res
  157.             int tmpMin = res;
  158.             for (int i = rightBound - 1; i >= l; --i) {
  159.                 tmpMin = min(tmpMin, insertPosition(compressed[i]));
  160.             }
  161.             res = tmpMin;
  162.  
  163.             // Khôi phục lại các phần tử đã xóa tạm
  164.             for (int i = l - 1; i >= leftBound; --i) insertPosition(compressed[i]);
  165.  
  166.             answer[query.index] = res;
  167.         }
  168.     }
  169.  
  170.     // In kết quả cho từng truy vấn theo thứ tự ban đầu
  171.     for (int i = 1; i <= q; ++i) {
  172.         cout << answer[i] << "\n";
  173.     }
  174.  
  175.     return 0;
  176. }
  177.  
Success #stdin #stdout 0.01s 5720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/ynXTx9
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!