Advertisement
Guest User

Untitled

a guest
May 19th, 2019
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.91 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/detail/standard_policies.hpp>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5.  
  6. #define pb push_back
  7. #define F first
  8. #define S second
  9. #define ll long long
  10. #define ld long double
  11. #define endl '\n'
  12. #define pii pair <int, int>
  13. #define last fedgfre
  14. #define ull unsigned long long
  15. #define y1 frfuhe
  16. //#define int long long
  17.  
  18. //#pragma comment(linker, "/stack:200000000")
  19. //#pragma GCC optimize("Ofast")
  20. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  21. //#pragma GCC optimize("unroll-loops")
  22. //#pragma GCC optimize("-O3")
  23.  
  24. using namespace std;
  25. using namespace __gnu_pbds;
  26.  
  27. template <typename T>
  28. using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
  29.  
  30. mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
  31.  
  32. const int N = 5e5 + 5;
  33. const int M = 3e4 + 5;
  34. const int mod = 1e9 + 7;
  35. const int rx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
  36. const int ry[8] = {0, 0, 1, -1, 1, -1, 1, -1};
  37. const int kx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
  38. const int ky[8] = {2, -2, 2, -2, 1, -1, 1, -1};
  39. const ld pi = acos(-1.0);
  40. const int B = 2150;
  41. const ld eps = 1e-30;
  42.  
  43. struct fenwick {
  44. int t[N];
  45.  
  46. void update(int p) {
  47. for (int i = p; i < N; i += i & -i) {
  48. t[i]++;
  49. }
  50. }
  51.  
  52. int query(int p) {
  53. int res = 0;
  54. for (int i = p; i; i -= i & -i) {
  55. res += t[i];
  56. }
  57. return res;
  58. }
  59.  
  60. int query(int l, int r) {
  61. return query(r) - query(l - 1);
  62. }
  63.  
  64. fenwick() {
  65. memset(t, 0, sizeof t);
  66. }
  67. };
  68.  
  69. struct query {
  70. int t, x1, y1, x2, y2;
  71. };
  72.  
  73. vector <query> queries;
  74.  
  75. #define FILE "sum"
  76. int main() {
  77. ios_base::sync_with_stdio(0);
  78. cin.tie(0);
  79. cout.tie(0);
  80. #ifdef LOCAL
  81. freopen("input.txt", "r", stdin);
  82. freopen("output.txt", "w", stdout);
  83. #else
  84. //freopen("input.txt", "r", stdin);
  85. //freopen("output.txt", "w", stdout);
  86. #endif // LOCAL
  87. int n, m, q;
  88. cin >> n >> m >> q;
  89. vector <int> allx;
  90. vector <int> ally;
  91. for (int i = 0; i < q; i++) {
  92. int t, x;
  93. cin >> t >> x;
  94. if (t == 1) {
  95. allx.pb(x);
  96. queries.pb({t, x, -1, -1, -1});
  97. }
  98. if (t == 2) {
  99. ally.pb(x);
  100. queries.pb({t, x, -1, -1, -1});
  101. }
  102. if (t == 3) {
  103. int a, b, c;
  104. cin >> a >> b >> c;
  105. allx.pb(x);
  106. allx.pb(b);
  107. ally.pb(a);
  108. ally.pb(c);
  109. queries.pb({t, x, a, b, c});
  110. }
  111. }
  112. sort(allx.begin(), allx.end());
  113. allx.resize(unique(allx.begin(), allx.end()) - allx.begin());
  114. sort(ally.begin(), ally.end());
  115. ally.resize(unique(ally.begin(), ally.end()) - ally.begin());
  116. fenwick Tx, Ty;
  117. for (auto it : queries) {
  118. if (it.t == 1) {
  119. int x = it.x1;
  120. x = lower_bound(allx.begin(), allx.end(), x) - allx.begin() + 1;
  121. Tx.update(x);
  122. }
  123. if (it.t == 2) {
  124. int x = it.x1;
  125. x = lower_bound(ally.begin(), ally.end(), x) - ally.begin() + 1;
  126. Ty.update(x);
  127. }
  128. if (it.t == 3) {
  129. int x1 = it.x1;
  130. int x2 = it.x2;
  131. int y1 = it.y1;
  132. int y2 = it.y2;
  133. x1 = lower_bound(allx.begin(), allx.end(), x1) - allx.begin() + 1;
  134. x2 = lower_bound(allx.begin(), allx.end(), x2) - allx.begin() + 1;
  135. y1 = lower_bound(ally.begin(), ally.end(), y1) - ally.begin() + 1;
  136. y2 = lower_bound(ally.begin(), ally.end(), y2) - ally.begin() + 1;;
  137. int kx = Tx.query(x1, x2);
  138. int ky = Ty.query(y1, y2);
  139. ll res = 1ll * kx * (it.y2 - it.y1 + 1) + 1ll * ky * (it.x2 - it.x1 + 1) - 2ll * kx * ky;
  140. cout << res << endl;
  141. }
  142. }
  143. return 0;
  144. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement