Advertisement
Dang_Quan_10_Tin

TABLE

Aug 17th, 2022 (edited)
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.34 KB | None | 0 0
  1. #define task "TABLE"
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. using ld = long double;
  11.  
  12. constexpr int N = 1e5 + 5;
  13. int m, n, q;
  14. int typ[N], x[N], y[N], z[N], t[N];
  15. ll w[N];
  16.  
  17. #define Unique(x) (sort(x.begin(), x.end()), x.resize(unique(x.begin(), x.end()) - x.begin()))
  18. #define Find(x, v) (lower_bound(x.begin(), x.end(), v) - x.begin() + 1)
  19.  
  20. vector<int> a[N];
  21. struct FenwickTree
  22. {
  23.     int n;
  24.     vector<ll> fen[N];
  25.     void Assign(int n)
  26.     {
  27.         this->n = n;
  28.  
  29.         for (int i = 1; i <= n; ++i)
  30.             fen[i].resize(a[i].size(), 0);
  31.     }
  32.  
  33.     void Update(int x, int y, ll v)
  34.     {
  35.         for (; x <= n; x += x & -x)
  36.             for (int i = Find(a[x], y); i <= (int)a[x].size(); i += i & -i)
  37.                 fen[x][i - 1] += v;
  38.     }
  39.  
  40.     ll Get(int x, int y)
  41.     {
  42.         ll ans(0);
  43.         for (; x; x -= x & -x)
  44.             for (int i = Find(a[x], y); i; i -= i & -i)
  45.                 ans += fen[x][i - 1];
  46.         return ans;
  47.     }
  48.  
  49.     void Update(int x, int y, int z, int t, ll v)
  50.     {
  51.         Update(x, y, v);
  52.         Update(x, t + 1, -v);
  53.         Update(z + 1, y, -v);
  54.         Update(z + 1, t + 1, v);
  55.     }
  56.  
  57. } rc, c, r, s;
  58.  
  59. void Read()
  60. {
  61.     cin >> m >> n >> q;
  62.  
  63.     for (int i = 1; i <= q; ++i)
  64.     {
  65.         cin >> typ[i] >> x[i] >> y[i] >> z[i] >> t[i];
  66.         if (typ[i] == 1)
  67.             cin >> w[i];
  68.     }
  69. }
  70.  
  71. void fake_get(int x, int y)
  72. {
  73.     for (; x; x -= x & -x)
  74.         a[x].emplace_back(y);
  75. }
  76.  
  77. void CompressTree()
  78. {
  79.     for (int i = 1; i <= q; ++i)
  80.         if (typ[i] == 2)
  81.         {
  82.             fake_get(z[i], t[i]);
  83.             fake_get(x[i] - 1, t[i]);
  84.             fake_get(z[i], y[i] - 1);
  85.             fake_get(x[i] - 1, y[i] - 1);
  86.         }
  87.  
  88.     for (int i = 1; i <= m; ++i)
  89.         Unique(a[i]);
  90.  
  91.     rc.Assign(m);
  92.     r.Assign(m);
  93.     c.Assign(m);
  94.     s.Assign(m);
  95. }
  96.  
  97. ll Get(int x, int y)
  98. {
  99.     return rc.Get(x, y) * (x + 1) * (y + 1) + r.Get(x, y) * (x + 1) + c.Get(x, y) * (y + 1) + s.Get(x, y);
  100. }
  101.  
  102. ll Get(int x, int y, int z, int t)
  103. {
  104.     return Get(z, t) - Get(x - 1, t) - Get(z, y - 1) + Get(x - 1, y - 1);
  105. }
  106.  
  107. void Solve()
  108. {
  109.     for (int i = 1; i <= q; ++i)
  110.         if (typ[i] == 1)
  111.         {
  112.             //
  113.             rc.Update(x[i], y[i], z[i], t[i], w[i]);
  114.             r.Update(x[i], y[i], z[i], t[i], -y[i] * w[i]);
  115.             c.Update(x[i], y[i], z[i], t[i], -x[i] * w[i]);
  116.             s.Update(x[i], y[i], z[i], t[i], w[i] * x[i] * y[i]);
  117.  
  118.             //
  119.             r.Update(x[i], t[i] + 1, z[i], n, w[i] * (t[i] - y[i] + 1));
  120.             s.Update(x[i], t[i] + 1, z[i], n, -w[i] * x[i] * (t[i] - y[i] + 1));
  121.  
  122.             //
  123.             c.Update(z[i] + 1, y[i], m, t[i], w[i] * (z[i] - x[i] + 1));
  124.             s.Update(z[i] + 1, y[i], m, t[i], -w[i] * y[i] * (z[i] - x[i] + 1));
  125.  
  126.             //
  127.             s.Update(z[i] + 1, t[i] + 1, m, n, w[i] * (z[i] - x[i] + 1) * (t[i] - y[i] + 1));
  128.         }
  129.         else
  130.             cout << Get(x[i], y[i], z[i], t[i]) << "\n";
  131. }
  132.  
  133. int32_t main()
  134. {
  135.     ios_base::sync_with_stdio(0);
  136.     cin.tie(0);
  137.     cout.tie(0);
  138.  
  139.     if (fopen(task ".INP", "r"))
  140.     {
  141.         freopen(task ".INP", "r", stdin);
  142.         freopen(task ".OUT", "w", stdout);
  143.     }
  144.  
  145.     Read();
  146.     CompressTree();
  147.     Solve();
  148. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement