fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. // Hằng số cho kích thước khối (block size) của Mo's Algorithm
  9. const int MAXN = 100005;
  10. const int BLOCK_SIZE = 316; // Căn bậc hai của MAXN (khoảng sqrt(10^5))
  11.  
  12. // Biến toàn cục để lưu trữ dữ liệu và kết quả
  13. int N, Q;
  14. vector<int> a;
  15. long long F_current = 0; // Giá trị F(l, r) hiện tại
  16. vector<long long> results;
  17.  
  18. // Cấu trúc cho truy vấn
  19. struct Query {
  20.     int l, r, index;
  21.     int block_l;
  22.  
  23.     // Sắp xếp truy vấn theo Mo's Algorithm
  24.     bool operator<(const Query& other) const {
  25.         if (block_l != other.block_l) {
  26.             return block_l < other.block_l;
  27.         }
  28.         // Sắp xếp zigzag: nếu block chẵn -> r tăng dần, block lẻ -> r giảm dần
  29.         if (block_l % 2 == 0) {
  30.             return r < other.r;
  31.         }
  32.         return r > other.r;
  33.     }
  34. };
  35.  
  36. // --- Hàm Cập Nhật Mo's Algorithm ---
  37.  
  38. /*
  39.  * Công thức rút gọn cuối cùng cần tính là:
  40.  * F(l, r) = sum_{j=l}^{r} (r - j + 1) * sum_{k=0}^{j-l} [a_j != a_{l+k}]
  41.  *
  42.  * Hàm cập nhật sẽ tập trung vào sự thay đổi của tổng khi l hoặc r thay đổi 1 đơn vị.
  43.  * Sự thay đổi của r tương đối dễ hơn vì chỉ thay đổi hệ số (r - j + 1) và thêm/bớt j = r hoặc j = r+1.
  44.  * Sự thay đổi của l là phức tạp nhất.
  45.  */
  46.  
  47. // Mảng/Cấu trúc dữ liệu phụ trợ:
  48. // Ta cần đếm số lần mà một cặp (a_j, a_{l+k}) xuất hiện,
  49. // nhưng cách tính này vẫn khó vì l thay đổi.
  50.  
  51. // Thay vào đó, ta sử dụng công thức ban đầu để cập nhật:
  52. // F(l, r) = sum_{x=l}^{r} sum_{y=x}^{r} d(a[x, y], a[l, r + y - x])
  53.  
  54. long long calculate_d(int x, int y, int l_base) {
  55.     long long dist = 0;
  56.     int len = y - x + 1;
  57.     int r_base = l_base + len - 1; // Chỉ số cuối của đoạn thứ hai
  58.  
  59.     // So sánh (a_x, ..., a_y) với (a_{l_base}, ..., a_{r_base})
  60.     for (int i = 0; i < len; ++i) {
  61.         if (a[x + i] != a[l_base + i]) {
  62.             dist++;
  63.         }
  64.     }
  65.     return dist;
  66. }
  67.  
  68. // Cập nhật khi r tăng
  69. void add_r(int new_r, int l_current) {
  70.     // Thêm các cặp (x, new_r) với l_current <= x <= new_r
  71.     for (int x = l_current; x <= new_r; ++x) {
  72.         // Đoạn 1: a[x, new_r]
  73.         // Đoạn 2: a[l_current, new_r + new_r - x]
  74.         F_current += calculate_d(x, new_r, l_current);
  75.     }
  76. }
  77.  
  78. // Cập nhật khi r giảm
  79. void remove_r(int old_r, int l_current) {
  80.     // Xóa các cặp (x, old_r) với l_current <= x <= old_r
  81.     for (int x = l_current; x <= old_r; ++x) {
  82.         // Đoạn 1: a[x, old_r]
  83.         // Đoạn 2: a[l_current, old_r + old_r - x]
  84.         F_current -= calculate_d(x, old_r, l_current);
  85.     }
  86. }
  87.  
  88. // Cập nhật khi l giảm (l_new = l_current - 1)
  89. void add_l(int new_l, int r_current) {
  90.     // Việc này phức tạp: l thay đổi, làm thay đổi VẾ THỨ HAI của khoảng cách Hamming
  91.     // F(new_l, r_current) = F(l_current, r_current) + Delta
  92.     // Delta = (Tổng cho x = new_l) + (Thay đổi do l_base -> new_l cho mọi cặp (x, y) cũ)
  93.  
  94.     // 1. Thêm các đóng góp mới từ x = new_l:
  95.     for (int y = new_l; y <= r_current; ++y) {
  96.         // Đoạn 1: a[new_l, y]
  97.         // Đoạn 2: a[new_l, r_current + y - new_l]
  98.         F_current += calculate_d(new_l, y, new_l);
  99.     }
  100.  
  101.     // 2. Cập nhật các đóng góp cũ (x > new_l):
  102.     // Đối với mọi cặp (x, y) cũ (l_current <= x <= y <= r_current),
  103.     // d(a[x, y], a[l_current, ...]) -> d(a[x, y], a[new_l, ...])
  104.     // Đây là phần tốn kém nhất:
  105.     for (int x = new_l + 1; x <= r_current; ++x) {
  106.         for (int y = x; y <= r_current; ++y) {
  107.             // Trừ đi giá trị cũ
  108.             F_current -= calculate_d(x, y, new_l + 1); // l_current = new_l + 1
  109.             // Cộng vào giá trị mới
  110.             F_current += calculate_d(x, y, new_l);
  111.         }
  112.     }
  113.     // *Lưu ý: Phần cập nhật này có độ phức tạp O(N^2) cho mỗi lần di chuyển l,
  114.     // điều này sẽ làm Mo's Algorithm bị TLE. Cần một cách cập nhật O(N) hoặc tốt hơn.*
  115.     // Do đó, cách tiếp cận này chỉ mang tính định hướng.
  116.     // Cách tối ưu thực sự đòi hỏi phân tích sâu hơn công thức rút gọn và sử dụng cấu trúc dữ liệu.
  117. }
  118.  
  119. // Cập nhật khi l tăng (l_new = l_current + 1)
  120. void remove_l(int old_l, int r_current) {
  121.     // Ngược lại với add_l, cũng rất phức tạp
  122.  
  123.     // 1. Xóa đóng góp từ x = old_l:
  124.     for (int y = old_l; y <= r_current; ++y) {
  125.         F_current -= calculate_d(old_l, y, old_l);
  126.     }
  127.  
  128.     // 2. Cập nhật các đóng góp cũ (x > old_l):
  129.     // Đối với mọi cặp (x, y) cũ (old_l + 1 <= x <= y <= r_current),
  130.     // d(a[x, y], a[old_l, ...]) -> d(a[x, y], a[old_l + 1, ...])
  131.     for (int x = old_l + 1; x <= r_current; ++x) {
  132.         for (int y = x; y <= r_current; ++y) {
  133.             // Trừ đi giá trị cũ
  134.             F_current -= calculate_d(x, y, old_l);
  135.             // Cộng vào giá trị mới
  136.             F_current += calculate_d(x, y, old_l + 1);
  137.         }
  138.     }
  139. }
  140.  
  141.  
  142. // --- Hàm Chính ---
  143.  
  144. void solve() {
  145.     cin >> N >> Q;
  146.     a.resize(N + 1); // Dùng 1-based indexing
  147.  
  148.     for (int i = 1; i <= N; ++i) {
  149.         cin >> a[i];
  150.     }
  151.  
  152.     vector<Query> queries(Q);
  153.     for (int i = 0; i < Q; ++i) {
  154.         cin >> queries[i].l >> queries[i].r;
  155.         queries[i].index = i;
  156.         queries[i].block_l = queries[i].l / BLOCK_SIZE;
  157.     }
  158.  
  159.     // 1. Sắp xếp các truy vấn
  160.     sort(queries.begin(), queries.end());
  161.  
  162.     results.resize(Q);
  163.     int current_l = 1;
  164.     int current_r = 0;
  165.  
  166.     // 2. Xử lý từng truy vấn
  167.     for (const auto& q : queries) {
  168.         // Di chuyển con trỏ r
  169.         while (current_r < q.r) {
  170.             current_r++;
  171.             add_r(current_r, current_l);
  172.         }
  173.         while (current_r > q.r) {
  174.             remove_r(current_r, current_l);
  175.             current_r--;
  176.         }
  177.  
  178.         // Di chuyển con trỏ l
  179.         while (current_l < q.l) {
  180.             remove_l(current_l, current_r);
  181.             current_l++;
  182.         }
  183.         while (current_l > q.l) {
  184.             current_l--;
  185.             add_l(current_l, current_r);
  186.         }
  187.  
  188.         results[q.index] = F_current;
  189.     }
  190.  
  191.     // 3. In kết quả
  192.     for (long long res : results) {
  193.         cout << res << "\n";
  194.     }
  195. }
  196.  
  197.  int main() {
  198. //     // Tăng tốc độ I/O
  199. //     ios_base::sync_with_stdio(false);
  200. //     cin.tie(NULL);
  201.  
  202.       solve();
  203.  
  204.      return 0;
  205.  }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
4 4
1 2 1 3
1 1
2 3
2 4
1 4
stdout
copy 
0
1
4
8
https://ideone.com/8r5Omg
language:
C++14 (gcc 8.3)
created:
4 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!