Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #pragma GCC optimize("O3")
- #define debug(tl) cerr<<#tl<<' '<<tl<<'\n';
- #include "bits/stdc++.h"
- using namespace std;
- #define all(d) d.begin(), d.end()
- typedef long long ll;
- typedef pair<ll, ll> pll;
- typedef long double ld;
- ll b1;
- const ll mod = (1ll << 55);
- ll get_hsh(ll x, ll y) {
- return (x + y * b1) % mod;
- }
- constexpr int N = 4e5 + 10;
- bitset<N> u;
- struct Fenwick {
- vector<ll> t;
- map<ll, ll> get_idx;
- ll n, m;
- Fenwick(ll _n, ll _m) {
- n = _n, m = _m;
- }
- void upd(ll i, ll j, ll add) {
- for (ll x = i; x < n; x += x & -x) {
- u[x] = 1;
- for (ll y = j; y < m; y += y & -y) {
- ll h1 = get_hsh(x, y);
- if (get_idx.find(h1) == get_idx.end())get_idx[h1] = t.size(), t.push_back({});
- ll ind = get_idx[h1];
- t[ind] += add;
- }
- }
- }
- ll get(ll i, ll j) {
- ll res = 0;
- for (ll x = i; x > 0; x -= x & -x) {
- if (!u[x])continue;
- for (ll y = j; y > 0; y -= y & -y) {
- ll h1 = get_hsh(x, y);
- if (get_idx.find(h1) == get_idx.end())continue;
- ll ind = get_idx[h1];
- res += t[ind];
- }
- }
- return res;
- }
- };
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- srand(19937);
- b1 = rand();
- int n;
- cin >> n;
- vector<int> x, y;
- vector<pair<pair<int, int>, int>> point(n);
- for (int i = 0; i < n; i++) {
- int x1, y1, w;
- cin >> x1 >> y1 >> w;
- point[i] = { {x1,y1}, w };
- x.push_back(x1), y.push_back(y1);
- }
- struct query {
- int type;
- int x, y;
- };
- int m;
- cin >> m;
- vector<query> q(m);
- for (int i = 0; i < m; i++) {
- string s;
- cin >> s;
- int x1, y1;
- cin >> x1 >> y1;
- if (s == "get") {
- x.push_back(x1), y.push_back(y1);
- q[i] = { 1,x1,y1 };
- }
- else {
- x1--;
- q[i] = { 2,x1, y1 };
- }
- }
- sort(all(x));
- x.resize(unique(all(x)) - x.begin());
- sort(all(y));
- y.resize(unique(all(y)) - y.begin());
- Fenwick F(x.size() + 1, y.size() + 1);
- for (int i = 0; i < n; i++) {
- int x1 = lower_bound(all(x), point[i].first.first) - x.begin() + 1;
- int y1 = lower_bound(all(y), point[i].first.second) - y.begin() + 1;
- F.upd(x1, y1, point[i].second);
- }
- for (int i = 0; i < m; i++) {
- if (q[i].type == 1) {
- int x1 = lower_bound(all(x), q[i].x) - x.begin() + 1;
- int y1 = lower_bound(all(y), q[i].y) - y.begin() + 1;
- cout << F.get((ll)x1, (ll)y1) << '\n';
- }
- else {
- int x1 = lower_bound(all(x), point[q[i].x].first.first) - x.begin() + 1;
- int y1 = lower_bound(all(y), point[q[i].x].first.second) - y.begin() + 1;
- int w = -point[q[i].x].second + q[i].y;
- F.upd((ll)x1, (ll)y1, (ll)w);
- point[q[i].x].second = q[i].y;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement