fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Line {
  5.     int L = 0;                          // độ dài của đường
  6.     map<int,int> seg;                   // các đoạn 1 không giao nhau [l,r]
  7.     long long ones = 0;                 // tổng số ô 1 trên đường
  8.  
  9.     Line() {}
  10.     Line(int _L): L(_L) {}
  11.  
  12.     // Chia đoạn tại vị trí x (tạo đoạn bắt đầu ở x nếu cần), trả iterator tới
  13.     // phần tử có key >= x.
  14.     map<int,int>::iterator split(int x){
  15.         auto it = seg.lower_bound(x);
  16.         if (it != seg.end() && it->first == x) return it;
  17.         if (it == seg.begin()) return it;
  18.         auto prv = prev(it);
  19.         if (prv->second < x) return it;
  20.         if (prv->second == x-1) return it;
  21.         int l = prv->first, r = prv->second;
  22.         prv->second = x-1;
  23.         return seg.emplace(x, r).first;
  24.     }
  25.  
  26.     // Thêm đoạn [l,r] (đã biết không giao với các đoạn bên trong vùng vừa xóa),
  27.     // nhưng có thể cần gộp với hàng xóm hai bên.
  28.     void add(int l, int r){
  29.         if (l > r) return;
  30.         auto it = seg.lower_bound(l);
  31.         int nl = l, nr = r;
  32.         if (it != seg.begin()){
  33.             auto p = prev(it);
  34.             if (p->second + 1 >= nl){
  35.                 nl = min(nl, p->first);
  36.                 nr = max(nr, p->second);
  37.                 it = seg.erase(p);
  38.             }
  39.         }
  40.         while (it != seg.end() && it->first <= nr + 1){
  41.             nr = max(nr, it->second);
  42.             it = seg.erase(it);
  43.         }
  44.         seg.emplace(nl, nr);
  45.     }
  46.  
  47.     // Lật XOR đoạn [l,r], trả về độ tăng/giảm số ô 1 trên đường
  48.     long long flip(int l, int r){
  49.         if (l > r) return 0;
  50.         auto itR = split(r+1);
  51.         auto itL = split(l);
  52.  
  53.         long long covered = 0;              // số ô 1 trước khi lật trong [l,r]
  54.         int cur = l;
  55.         vector<pair<int,int>> gaps;         // các khoảng 0 trong [l,r] sẽ trở thành 1
  56.         for (auto it = itL; it != itR; ++it){
  57.             int a = it->first, b = it->second;
  58.             if (cur < a) gaps.emplace_back(cur, a-1);
  59.             covered += (long long)b - a + 1;
  60.             cur = b + 1;
  61.         }
  62.         if (cur <= r) gaps.emplace_back(cur, r);
  63.  
  64.         seg.erase(itL, itR);                // các đoạn 1 bên trong [l,r] trở thành 0
  65.         for (auto &g : gaps) add(g.first, g.second);  // các khoảng 0 trở thành 1
  66.  
  67.         long long delta = (long long)(r - l + 1) - 2*covered;
  68.         ones += delta;
  69.         return delta;
  70.     }
  71. };
  72.  
  73. int main(){
  74.     ios::sync_with_stdio(false);
  75.     cin.tie(nullptr);
  76.  
  77.     int N, M, Q;
  78.     if(!(cin >> N >> M >> Q)) return 0;
  79.  
  80.     unordered_map<int, Line> V, H;   // V: đường biên ngang (giữa hàng i và i+1), độ dài M
  81.                                      // H: đường biên dọc  (giữa cột j và j+1), độ dài N
  82.     V.reserve(Q*2+10);
  83.     H.reserve(Q*2+10);
  84.  
  85.     auto getV = [&](int i) -> Line& {
  86.         auto it = V.find(i);
  87.         if (it == V.end()) it = V.emplace(i, Line(M)).first;
  88.         return it->second;
  89.     };
  90.     auto getH = [&](int j) -> Line& {
  91.         auto it = H.find(j);
  92.         if (it == H.end()) it = H.emplace(j, Line(N)).first;
  93.         return it->second;
  94.     };
  95.  
  96.     long long ans = 0;
  97.     for (int qi = 0; qi < Q; ++qi){
  98.         int x1, x2, y1, y2;
  99.         cin >> x1 >> x2 >> y1 >> y2;   // giả sử input đã đảm bảo x1<=x2, y1<=y2
  100.  
  101.         ans += getV(x1-1).flip(y1, y2);
  102.         ans += getV(x2).flip(y1, y2);
  103.         ans += getH(y1-1).flip(x1, x2);
  104.         ans += getH(y2).flip(x1, x2);
  105.  
  106.         cout << ans << '\n';
  107.     }
  108.     return 0;
  109. }
  110.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin 
4 5 4
1 4 2 5
1 2 3 4
2 3 4 5
1 4 3 5
stdout 
16
20
24
22
https://ideone.com/0iWO0A
language:
C++14 (gcc 8.3)
created:
10 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!