fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. /**
  8.  * Giải thuật:
  9.  * - Tách bài toán thành tính toán cạnh dọc và cạnh ngang riêng biệt.
  10.  * - Với mỗi chiều, ta coi mỗi cột/hàng là một dãy các đoạn thẳng.
  11.  * - Sử dụng Segment Tree hỗ trợ đảo trạng thái đoạn (Range Flip) và đếm số lượng phần tử bằng 1.
  12.  * - Xử lý offline theo từng cột/hàng để tiết kiệm bộ nhớ.
  13.  */
  14.  
  15. struct Event {
  16.     int t, l, r;
  17. };
  18.  
  19. const int MAX_VAL = 1000005;
  20. struct Node {
  21.     int cnt1;
  22.     bool lazy;
  23. } tree[4000005];
  24.  
  25. // Đảo trạng thái một nút trong Segment Tree
  26. inline void apply(int v, int tl, int tr) {
  27.     tree[v].cnt1 = (tr - tl + 1) - tree[v].cnt1;
  28.     tree[v].lazy = !tree[v].lazy;
  29. }
  30.  
  31. // Đẩy tag lazy xuống các con
  32. inline void push_down(int v, int tl, int tr) {
  33.     if (tree[v].lazy) {
  34.         int tm = (tl + tr) >> 1;
  35.         apply(v << 1, tl, tm);
  36.         apply(v << 1 | 1, tm + 1, tr);
  37.         tree[v].lazy = false;
  38.     }
  39. }
  40.  
  41. // Cập nhật đảo trạng thái đoạn [l, r]
  42. void update(int v, int tl, int tr, int l, int r) {
  43.     if (l > r) return;
  44.     if (l == tl && r == tr) {
  45.         apply(v, tl, tr);
  46.     } else {
  47.         push_down(v, tl, tr);
  48.         int tm = (tl + tr) >> 1;
  49.         if (r <= tm) update(v << 1, tl, tm, l, r);
  50.         else if (l > tm) update(v << 1 | 1, tm + 1, tr, l, r);
  51.         else {
  52.             update(v << 1, tl, tm, l, tm);
  53.             update(v << 1 | 1, tm + 1, tr, tm + 1, r);
  54.         }
  55.         tree[v].cnt1 = tree[v << 1].cnt1 + tree[v << 1 | 1].cnt1;
  56.     }
  57. }
  58.  
  59. long long delta_ans[200005];
  60. vector<Event> events[MAX_VAL];
  61.  
  62. struct Rect {
  63.     int x1, x2, y1, y2;
  64. };
  65.  
  66. int main() {
  67.     ios::sync_with_stdio(false);
  68.     cin.tie(NULL);
  69.  
  70.     int N, M, Q;
  71.     if (!(cin >> N >> M >> Q)) return 0;
  72.  
  73.     vector<Rect> rects(Q);
  74.     for (int i = 0; i < Q; ++i) {
  75.         cin >> rects[i].x1 >> rects[i].x2 >> rects[i].y1 >> rects[i].y2;
  76.     }
  77.  
  78.     auto solve_dimension = [&](int num_groups, int line_length, bool vertical_scan) {
  79.         for (int i = 0; i <= num_groups; ++i) events[i].clear();
  80.  
  81.         for (int i = 0; i < Q; ++i) {
  82.             if (vertical_scan) {
  83.                 // Các cạnh dọc thay đổi tại cột y1-1 và y2
  84.                 events[rects[i].y1 - 1].push_back({i + 1, rects[i].x1, rects[i].x2});
  85.                 events[rects[i].y2].push_back({i + 1, rects[i].x1, rects[i].x2});
  86.             } else {
  87.                 // Các cạnh ngang thay đổi tại hàng x1-1 và x2
  88.                 events[rects[i].x1 - 1].push_back({i + 1, rects[i].y1, rects[i].y2});
  89.                 events[rects[i].x2].push_back({i + 1, rects[i].y1, rects[i].y2});
  90.             }
  91.         }
  92.  
  93.         for (int j = 0; j <= num_groups; ++j) {
  94.             if (events[j].empty()) continue;
  95.             sort(events[j].begin(), events[j].end(), [](const Event& a, const Event& b) {
  96.                 return a.t < b.t;
  97.             });
  98.  
  99.             int last_count = 0;
  100.             for (auto& ev : events[j]) {
  101.                 update(1, 1, line_length, ev.l, ev.r);
  102.                 int current_count = tree[1].cnt1;
  103.                 delta_ans[ev.t] += (current_count - last_count);
  104.                 last_count = current_count;
  105.             }
  106.             // Reset cây về 0 để xử lý cột/hàng tiếp theo
  107.             for (auto& ev : events[j]) {
  108.                 update(1, 1, line_length, ev.l, ev.r);
  109.             }
  110.         }
  111.     };
  112.  
  113.     // Bước 1: Tính toán đóng góp của các cạnh dọc vào chu vi
  114.     solve_dimension(M, N, true);
  115.     // Bước 2: Tính toán đóng góp của các cạnh ngang vào chu vi
  116.     solve_dimension(N, M, false);
  117.  
  118.     // Bước 3: Tổng hợp kết quả sau mỗi truy vấn
  119.     long long total_perimeter = 0;
  120.     for (int i = 1; i <= Q; ++i) {
  121.         total_perimeter += delta_ans[i];
  122.         cout << total_perimeter << (i == Q ? "" : " ");
  123.     }
  124.     cout << endl;
  125.  
  126.     return 0;
  127. }
  128.  
Success #stdin #stdout 0.01s 27492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0xPBBN
language:
C++14 (gcc 8.3)
created:
7 hours 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!