Advertisement
ivnikkk

Untitled

Jun 22nd, 2022
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.26 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma GCC optimize("O3")
  3. #define debug(tl) cerr<<#tl<<' '<<tl<<'\n';
  4. #include "bits/stdc++.h"
  5. using namespace std;
  6. #define all(d) d.begin(), d.end()
  7. typedef long long ll;
  8. typedef pair<ll, ll> pll;
  9. typedef long double ld;
  10. ll b1;
  11. const ll mod = (1ll << 55);
  12. ll get_hsh(ll x, ll y) {
  13.     return (x + y * b1) % mod;
  14. }
  15.  
  16. constexpr int N = 4e5 + 10;
  17. bitset<N> u;
  18. struct Fenwick {
  19.     vector<ll> t;
  20.     map<ll, ll> get_idx;
  21.     ll n, m;
  22.     Fenwick(ll _n, ll _m) {
  23.         n = _n, m = _m;
  24.     }
  25.     void upd(ll i, ll j, ll add) {
  26.         for (ll x = i; x < n; x += x & -x) {
  27.             u[x] = 1;
  28.             for (ll y = j; y < m; y += y & -y) {
  29.                 ll h1 = get_hsh(x, y);
  30.                 if (get_idx.find(h1) == get_idx.end())get_idx[h1] = t.size(), t.push_back({});
  31.                 ll ind = get_idx[h1];
  32.                 t[ind] += add;
  33.             }
  34.         }
  35.     }
  36.     ll get(ll i, ll j) {
  37.         ll res = 0;
  38.         for (ll x = i; x > 0; x -= x & -x) {
  39.             if (!u[x])continue;
  40.             for (ll y = j; y > 0; y -= y & -y) {
  41.                 ll h1 = get_hsh(x, y);
  42.                 if (get_idx.find(h1) == get_idx.end())continue;
  43.                 ll ind = get_idx[h1];
  44.                 res += t[ind];
  45.             }
  46.         }
  47.         return res;
  48.     }
  49. };
  50. signed main() {
  51. #ifdef _DEBUG
  52.     freopen("input.txt", "r", stdin);
  53.     freopen("output.txt", "w", stdout);
  54. #endif
  55.     ios_base::sync_with_stdio(false);
  56.     cin.tie(nullptr);
  57.     cout.tie(nullptr);
  58.     srand(19937);
  59.     b1 = rand();
  60.     int n;
  61.     cin >> n;
  62.     vector<int> x, y;
  63.     vector<pair<pair<int, int>, int>> point(n);
  64.     for (int i = 0; i < n; i++) {
  65.         int x1, y1, w;
  66.         cin >> x1 >> y1 >> w;
  67.         point[i] = { {x1,y1}, w };
  68.         x.push_back(x1), y.push_back(y1);
  69.     }
  70.     struct query {
  71.         int type;
  72.         int x, y;
  73.     };
  74.     int m;
  75.     cin >> m;
  76.     vector<query> q(m);
  77.     for (int i = 0; i < m; i++) {
  78.         string s;
  79.         cin >> s;
  80.         int x1, y1;
  81.         cin >> x1 >> y1;
  82.         if (s == "get") {
  83.             x.push_back(x1), y.push_back(y1);
  84.             q[i] = { 1,x1,y1 };
  85.  
  86.         }
  87.         else {
  88.             x1--;
  89.             q[i] = { 2,x1, y1 };
  90.         }
  91.     }
  92.     sort(all(x));
  93.     x.resize(unique(all(x)) - x.begin());
  94.     sort(all(y));
  95.     y.resize(unique(all(y)) - y.begin());
  96.     Fenwick F(x.size() + 1, y.size() + 1);
  97.     for (int i = 0; i < n; i++) {
  98.         int x1 = lower_bound(all(x), point[i].first.first) - x.begin() + 1;
  99.         int y1 = lower_bound(all(y), point[i].first.second) - y.begin() + 1;
  100.         F.upd(x1, y1, point[i].second);
  101.     }
  102.     for (int i = 0; i < m; i++) {
  103.         if (q[i].type == 1) {
  104.             int x1 = lower_bound(all(x), q[i].x) - x.begin() + 1;
  105.             int y1 = lower_bound(all(y), q[i].y) - y.begin() + 1;
  106.             cout << F.get((ll)x1, (ll)y1) << '\n';
  107.         }
  108.         else {
  109.  
  110.             int x1 = lower_bound(all(x), point[q[i].x].first.first) - x.begin() + 1;
  111.             int y1 = lower_bound(all(y), point[q[i].x].first.second) - y.begin() + 1;
  112.             int w = -point[q[i].x].second + q[i].y;
  113.             F.upd((ll)x1, (ll)y1, (ll)w);
  114.             point[q[i].x].second = q[i].y;
  115.         }
  116.     }
  117. }
  118.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement