Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/detail/standard_policies.hpp>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define pb push_back
- #define F first
- #define S second
- #define ll long long
- #define ld long double
- #define endl '\n'
- #define pii pair <int, int>
- #define last fedgfre
- #define ull unsigned long long
- #define y1 frfuhe
- //#define int long long
- //#pragma comment(linker, "/stack:200000000")
- //#pragma GCC optimize("Ofast")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- //#pragma GCC optimize("unroll-loops")
- //#pragma GCC optimize("-O3")
- using namespace std;
- using namespace __gnu_pbds;
- template <typename T>
- using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
- mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
- const int N = 5e5 + 5;
- const int M = 3e4 + 5;
- const int mod = 1e9 + 7;
- const int rx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
- const int ry[8] = {0, 0, 1, -1, 1, -1, 1, -1};
- const int kx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
- const int ky[8] = {2, -2, 2, -2, 1, -1, 1, -1};
- const ld pi = acos(-1.0);
- const int B = 2150;
- const ld eps = 1e-30;
- struct fenwick {
- int t[N];
- void update(int p) {
- for (int i = p; i < N; i += i & -i) {
- t[i]++;
- }
- }
- int query(int p) {
- int res = 0;
- for (int i = p; i; i -= i & -i) {
- res += t[i];
- }
- return res;
- }
- int query(int l, int r) {
- return query(r) - query(l - 1);
- }
- fenwick() {
- memset(t, 0, sizeof t);
- }
- };
- struct query {
- int t, x1, y1, x2, y2;
- };
- vector <query> queries;
- #define FILE "sum"
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- #endif // LOCAL
- int n, m, q;
- cin >> n >> m >> q;
- vector <int> allx;
- vector <int> ally;
- for (int i = 0; i < q; i++) {
- int t, x;
- cin >> t >> x;
- if (t == 1) {
- allx.pb(x);
- queries.pb({t, x, -1, -1, -1});
- }
- if (t == 2) {
- ally.pb(x);
- queries.pb({t, x, -1, -1, -1});
- }
- if (t == 3) {
- int a, b, c;
- cin >> a >> b >> c;
- allx.pb(x);
- allx.pb(b);
- ally.pb(a);
- ally.pb(c);
- queries.pb({t, x, a, b, c});
- }
- }
- sort(allx.begin(), allx.end());
- allx.resize(unique(allx.begin(), allx.end()) - allx.begin());
- sort(ally.begin(), ally.end());
- ally.resize(unique(ally.begin(), ally.end()) - ally.begin());
- fenwick Tx, Ty;
- for (auto it : queries) {
- if (it.t == 1) {
- int x = it.x1;
- x = lower_bound(allx.begin(), allx.end(), x) - allx.begin() + 1;
- Tx.update(x);
- }
- if (it.t == 2) {
- int x = it.x1;
- x = lower_bound(ally.begin(), ally.end(), x) - ally.begin() + 1;
- Ty.update(x);
- }
- if (it.t == 3) {
- int x1 = it.x1;
- int x2 = it.x2;
- int y1 = it.y1;
- int y2 = it.y2;
- x1 = lower_bound(allx.begin(), allx.end(), x1) - allx.begin() + 1;
- x2 = lower_bound(allx.begin(), allx.end(), x2) - allx.begin() + 1;
- y1 = lower_bound(ally.begin(), ally.end(), y1) - ally.begin() + 1;
- y2 = lower_bound(ally.begin(), ally.end(), y2) - ally.begin() + 1;;
- int kx = Tx.query(x1, x2);
- int ky = Ty.query(y1, y2);
- ll res = 1ll * kx * (it.y2 - it.y1 + 1) + 1ll * ky * (it.x2 - it.x1 + 1) - 2ll * kx * ky;
- cout << res << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement