fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const char* task = "task";
  5. using ll = long long;
  6.  
  7. vector<int> st, L, R, lazy; // st = số 1 trong đoạn, lazy = parity flip (0/1)
  8. int n, m, q;
  9. vector<int> root, root2;    // root cho biên hàng (n+2), root2 cho biên cột (m+2)
  10.  
  11. inline int new_node() {
  12.     int cur = (int)st.size();
  13.     st.emplace_back(0);
  14.     L.emplace_back(0);
  15.     R.emplace_back(0);
  16.     lazy.emplace_back(0);
  17.     return cur;
  18. }
  19.  
  20. // Bảo đảm tồn tại 2 con trước khi push (an toàn)
  21. inline void ensure_children(int id) {
  22.     if (L[id] == 0) L[id] = new_node();
  23.     if (R[id] == 0) R[id] = new_node();
  24. }
  25.  
  26. // Đẩy lazy xuống 2 con (flip theo parity)
  27. inline void down(int id, int l, int r) {
  28.     if ((lazy[id] & 1) == 0) return;
  29.     int mid = (l + r) >> 1;
  30.     ensure_children(id);
  31.  
  32.     // lật con trái
  33.     st[L[id]] = (mid - l + 1) - st[L[id]];
  34.     lazy[L[id]] ^= 1;
  35.  
  36.     // lật con phải
  37.     st[R[id]] = (r - mid) - st[R[id]];
  38.     lazy[R[id]] ^= 1;
  39.  
  40.     lazy[id] = 0;
  41. }
  42.  
  43. // Flip đoạn [u..v] trên cây động; trả về delta (mới - cũ) trong đoạn cắt
  44. int flip(int id, int l, int r, int u, int v) {
  45.     if (r < u || v < l) return 0;
  46.  
  47.     if (l >= u && r <= v) {
  48.         lazy[id] ^= 1;
  49.         int prev = st[id];
  50.         st[id] = (r - l + 1) - st[id];   // lật cả đoạn
  51.         return st[id] - prev;            // delta
  52.     }
  53.  
  54.     down(id, l, r);
  55.     int mid = (l + r) >> 1;
  56.     ensure_children(id);
  57.  
  58.     int x = flip(L[id], l, mid, u, v);
  59.     int y = flip(R[id], mid + 1, r, u, v);
  60.     st[id] = st[L[id]] + st[R[id]];
  61.     return x + y;
  62. }
  63.  
  64. int main() {
  65.     ios::sync_with_stdio(false);
  66.     cin.tie(nullptr);
  67.  
  68.     if (fopen((string(task) + ".inp").c_str(), "r")) {
  69.         freopen((string(task) + ".inp").c_str(), "r", stdin);
  70.         freopen((string(task) + ".out").c_str(), "w", stdout);
  71.     }
  72.  
  73.     cin >> n >> m >> q;
  74.  
  75.     // cấp phát kho nút cho segtree động
  76.     st.reserve(1<<20);
  77.     L.reserve(1<<20);
  78.     R.reserve(1<<20);
  79.     lazy.reserve(1<<20);
  80.  
  81.     new_node(); // chặn id=0 làm "null"
  82.  
  83.     root.assign(n + 2 + 1, 0);   // biên hàng: 1..n+1
  84.     root2.assign(m + 2 + 1, 0);  // biên cột: 1..m+1
  85.  
  86.     for (int i = 1; i <= n + 1; ++i) root[i]  = new_node();
  87.     for (int i = 1; i <= m + 1; ++i) root2[i] = new_node();
  88.  
  89.     ll ans = 0;
  90.     while (q--) {
  91.         int a, b, c, d;
  92.         cin >> a >> b >> c >> d; // lật [a..b] x [c..d]
  93.  
  94.         // 4 biên của hình chữ nhật:
  95.         // - biên ngang: hàng a và b+1, c..d (chiều dài theo cột → phạm vi [1..m])
  96.         // - biên dọc:  cột c và d+1, a..b (chiều dài theo hàng → phạm vi [1..n])
  97.  
  98.         // Dùng delta (mới - cũ): cộng thẳng vào ans
  99.         ans += flip(root[a],   1, m, c, d);
  100.         ans += flip(root[b+1], 1, m, c, d);
  101.         ans += flip(root2[c],  1, n, a, b);
  102.         ans += flip(root2[d+1],1, n, a, b);
  103.  
  104.         cout << ans << '\n';
  105.     }
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/U35Fyy
language:
C++14 (gcc 8.3)
created:
3 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!