fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 1e5 + 5;
  5. const int BLOCK_SIZE = 450; // Xấp xỉ sqrt(M)
  6.  
  7. struct Operation {
  8.     int x, y;
  9. } ops[MAXN];
  10.  
  11. struct Event {
  12.     int op_idx, type; // type: +1 (thêm), -1 (bớt)
  13. };
  14.  
  15. struct Query {
  16.     int id, l, r;
  17. };
  18.  
  19. int n, m, q;
  20. int initial_a[MAXN];
  21. int results[MAXN];
  22. int is_active[MAXN]; // Đánh dấu thao tác có đang phủ vị trí p hay không
  23. vector<Event> events_at[MAXN];
  24. vector<Query> queries_at[MAXN];
  25.  
  26. // Cấu trúc để quản lý việc "nhảy" qua một khối thao tác
  27. struct BlockMapping {
  28.     int target[MAXN];    // target[v]: giá trị v biến thành sau khi qua khối
  29.     int timestamp[MAXN]; // Dùng để tránh memset (Lazy Reset)
  30.     int current_time = 0;
  31.  
  32.     void rebuild(int b_idx) {
  33.         current_time++;
  34.         int start = (b_idx - 1) * BLOCK_SIZE + 1;
  35.         int end = min(m, b_idx * BLOCK_SIZE);
  36.  
  37.         // Duyệt ngược từ cuối khối về đầu để xây dựng bảng ánh xạ
  38.         for (int i = end; i >= start; i--) {
  39.             if (is_active[i]) {
  40.                 int from = ops[i].x;
  41.                 int to = ops[i].y;
  42.  
  43.                 timestamp[from] = current_time;
  44.                 // Nếu 'to' đã được ánh xạ bởi một lệnh phía sau trong khối
  45.                 if (timestamp[to] == current_time) {
  46.                     target[from] = target[to];
  47.                 } else {
  48.                     target[from] = to;
  49.                 }
  50.             }
  51.         }
  52.     }
  53.  
  54.     int jump(int b_idx, int val) {
  55.         return (timestamp[val] == current_time) ? target[val] : val;
  56.     }
  57. } mapping[MAXN / BLOCK_SIZE + 5];
  58.  
  59. // Trả lời câu hỏi bằng cách duyệt trâu đoạn lẻ và nhảy qua khối nguyên
  60. int solve_query(int val, int l, int r) {
  61.     int b_l = (l - 1) / BLOCK_SIZE + 1;
  62.     int b_r = (r - 1) / BLOCK_SIZE + 1;
  63.  
  64.     if (b_l == b_r) {
  65.         for (int i = l; i <= r; i++) 
  66.             if (is_active[i] && val == ops[i].x) val = ops[i].y;
  67.         return val;
  68.     }
  69.  
  70.     // 1. Xử lý đoạn lẻ ở khối đầu
  71.     int end_l = b_l * BLOCK_SIZE;
  72.     for (int i = l; i <= end_l; i++)
  73.         if (is_active[i] && val == ops[i].x) val = ops[i].y;
  74.  
  75.     // 2. Nhảy qua các khối nguyên ở giữa
  76.     for (int b = b_l + 1; b < b_r; b++) {
  77.         val = mapping[b].jump(b, val);
  78.     }
  79.  
  80.     // 3. Xử lý đoạn lẻ ở khối cuối
  81.     int start_r = (b_r - 1) * BLOCK_SIZE + 1;
  82.     for (int i = start_r; i <= r; i++)
  83.         if (is_active[i] && val == ops[i].x) val = ops[i].y;
  84.  
  85.     return val;
  86. }
  87.  
  88. int main() {
  89.     ios::sync_with_stdio(0); cin.tie(0);
  90.  
  91.     if (!(cin >> n >> m)) return 0;
  92.     for (int i = 1; i <= n; i++) cin >> initial_a[i];
  93.  
  94.     for (int i = 1; i <= m; i++) {
  95.         int l, r, x, y;
  96.         cin >> l >> r >> x >> y;
  97.         ops[i] = {x, x + y};
  98.         events_at[l].push_back({i, 1});
  99.         events_at[r + 1].push_back({i, -1});
  100.     }
  101.  
  102.     cin >> q;
  103.     for (int i = 1; i <= q; i++) {
  104.         int p, l, r;
  105.         cin >> p >> l >> r;
  106.         queries_at[p].push_back({i, l, r});
  107.     }
  108.  
  109.     // Đường quét qua từng vị trí trên mảng A
  110.     for (int p = 1; p <= n; p++) {
  111.         if (events_at[p].empty() && queries_at[p].empty()) continue;
  112.  
  113.         set<int> changed_blocks;
  114.         for (auto &e : events_at[p]) {
  115.             is_active[e.op_idx] += e.type;
  116.             changed_blocks.insert((e.op_idx - 1) / BLOCK_SIZE + 1);
  117.         }
  118.  
  119.         // Chỉ xây dựng lại bảng ánh xạ cho những khối có sự thay đổi
  120.         for (int b_idx : changed_blocks) {
  121.             mapping[b_idx].rebuild(b_idx);
  122.         }
  123.  
  124.         for (auto &q : queries_at[p]) {
  125.             results[q.id] = solve_query(initial_a[p], q.l, q.r);
  126.         }
  127.     }
  128.  
  129.     for (int i = 1; i <= q; i++) cout << results[i] << "\n";
  130.  
  131.     return 0;
  132. }
Success #stdin #stdout 0.03s 185768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4DhKWL
language:
C++14 (gcc 8.3)
created:
2 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!