8. Areál zavlažovačov vzorové riešenie

#include<bits/stdc++.h>

using namespace std;

#define FOR(i,n)	for(int i=0;i<(int)n;i++)
#define FOB(i,n)	for(int i=n;i>=1;i--)
#define MP(x,y)	make_pair((x),(y))
#define ii pair<int, int>
#define lli long long int
#define ld long double
#define ulli unsigned long long int
#define lili pair<lli, lli>
#ifdef EBUG
#define DBG	if(1)
#else
#define DBG	if(0)
#endif
#define SIZE(x) int(x.size())
const int infinity = 2000000999;
const long long int inff = 4000000000000000999;

typedef complex<long double> point;

template<class T>
T get() {
    T a;
    cin >> a;
    return a;
}

template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {
    out << "[" << par.first << ";" << par.second << "]";
    return out;
}

template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) {
    out << "{";
    for (const auto &x:cont) out << x << ", ";
    out << "}";
    return out;
}

template <class T, class U>
ostream& operator<<(ostream& out, const map<T,U> &cont) {
    out << "{";
    for (const auto &x:cont) out << x << ", ";
    
    out << "}"; return out;
}

template <class T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  FOR(i, v.size()){
    if(i) out << " ";
    out << v[i];
  }
  out << endl;
  return out;
}

bool ccw(point p, point a, point b) {
  if((conj(a - p) * (b - p)).imag() <= 0) return false;
  else return true;
}

struct zavlahovac {
    int x, y;
    int vlaha;
    string dir;
    
    const bool operator<(const zavlahovac &z) const {
        if (dir[0] == 'H') {
            return y < z.y;
        }
        else return y > z.y;
    }
};

struct node {
    int start, range;
    int sx, ex;
    int sums;
    node *prvy, *druhy;
    
    node (int st, int rn, int n, vector<int> &coor) {
        sx = (st < n ? coor[st] : infinity);
        ex = (st + rn >= n ? infinity : coor[st + 1]);
        start = st;
        range = rn;
        if (rn == 1) {
            sums = 0;
            prvy = NULL;
            druhy = NULL;
        }
        else {
            prvy = new node(st, rn / 2, n, coor);
            druhy = new node(st + rn / 2, rn / 2, n, coor);
            sums = 0;
        }
    }
    
    node (node *old, node *newprvy, node *newdruhy, int newval) {
        start = old -> start;
        range = old -> range;
        sx = old -> sx;
        ex = old -> ex;
        sums = newval;
        prvy = newprvy;
        druhy = newdruhy;
    }
    
    node *update(int p, int vl) {
        if (range == 1) {
            return new node(this, NULL, NULL, sums + vl);
        }
        if (druhy -> start <= p) return new node(this, prvy, druhy->update(p, vl), sums + vl);
        return new node(this, prvy->update(p, vl), druhy, sums + vl);
    }
    
    int query(int st, int end) {
        DBG cout << "In [" << sx << "; " << ex << "] [" << start << " range: " << range << "] sums = " << sums << " query(" << st << ", " << end << ")" << endl;
        if (start >= end) return 0;
        if (start + range <= st) return 0;
        if (start >= st && start + range <= end) return sums;
        return prvy->query(st, end) + druhy-> query(st, end);
    }
    
    void print(string k) {
        cout << k << "In [" << start << "; " << start + range << "] with [" << sx << "; " << ex << "] sums = " << sums << endl;
        if (range != 1) {
            cout << k <<  "PRVY {\n";
            prvy -> print(k + "  ");
            cout << k << "} DRUHY {\n";
            druhy -> print(k + "  ");
            cout << k << "}" << endl;
        }
    }
};

struct intervalac {
    int N;
    int realn;
    map<int, int> xcoors, ycoors;
    vector<node *> roots;
    string dir;
    
    intervalac(int n, vector<zavlahovac> &zvs) {
        if (!n) {
            N = 0;
            return;
        }
        N = pow(2, ceil(log2(n)));
        realn = n;
        dir = zvs[0].dir;
        DBG cout << "intervalac " << dir << ":"  << endl;
        sort(zvs.begin(), zvs.end());
        vector<int> xunsort;
        FOR(i, n) {
            ycoors[zvs[i].y] = i;
            xunsort.push_back(zvs[i].x);
        }
        sort(xunsort.begin(), xunsort.end());
        FOR(i, n) {
            xcoors[xunsort[i]] = i;
        }
        roots.push_back(new node(0, N, n, xunsort));
        FOR(i, n) {
            DBG cout << "update " << i << " on pos " << xcoors[zvs[i].x] << endl;
            roots.push_back(roots[i] -> update(xcoors[zvs[i].x], zvs[i].vlaha));
        }
        if (dir[0] == 'H') ycoors[infinity] = n;
        
        DBG {
            FOR(i, n + 1) {
                cout << "Iteration " << i << ":" << endl;
                roots[i] -> print("");
            }
        }
        
    }
    
    int query(int x, int y) {
        if (!N) return 0;
        if (dir[0] == 'H') {
            auto it = ycoors.upper_bound(y); 
            int upto = (it == ycoors.begin() ? 0 : (--it)->second + 1);
            if (dir[1] == 'L') {    
                auto itx = xcoors.lower_bound(x);
                return (itx == xcoors.end() ? 0 : roots[upto] -> query(itx->second, N));
            }
            else {
                DBG cout << "[" << x << "; " << y << " ] In " << dir << " upto = " << upto << " in " << ycoors << endl;
                auto itx = xcoors.upper_bound(x);
                return roots[upto] -> query(0, (itx == xcoors.end() ? N : itx -> second));
            }
        }
        auto it = ycoors.lower_bound(y);
        int yid = (it == ycoors.end() ? 0 : it -> second + 1);
        if (dir[1] == 'L') {
            auto itx = xcoors.lower_bound(x);
            return (itx == xcoors.end() ? 0 : roots[yid] -> query(itx->second, N));
        }
        auto itx = xcoors.upper_bound(x);
        DBG cout << "query (" << x << "; " << y << ") In " << dir << " yid = " << yid << " in " << ycoors << " and itx = " << (itx == xcoors.end() ? N : itx->second) << " from " << xcoors << endl;
        return roots[yid] -> query(0, (itx == xcoors.end() ? N : itx -> second));
    }
};

int main() {
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    int n = get<int>();
    vector<zavlahovac> DL, DP, HP, HL; 
    FOR(i, n) {
        int x, y;
        int vl;
        string smer;
        cin >> x >> y >> vl >> smer;
        if (smer == "DL") {
            DL.push_back({x, y, vl, smer});
        }
        else if (smer == "DP") {
            DP.push_back({x, y, vl, smer});
        }
        else if (smer == "HP") {
            HP.push_back({x, y, vl, smer});
        }
        else HL.push_back({x, y, vl, smer});
    }
    
    intervalac iDL(DL.size(), DL);
    intervalac iDP(DP.size(), DP);
    intervalac iHL(HL.size(), HL);
    intervalac iHP(HP.size(), HP);
    
    int m = get<int>();
    int k = get<int>();
    
    int prev_ans = 0;
    
    FOR(i, m) {
        int x, y;
        cin >> x >> y;
        x ^= prev_ans * k;
        y ^= prev_ans * k;
        
        DBG cout << "Query " << i << ": " << x << " " << y << endl;
        int idl = iDL.query(x, y);
        int idp = iDP.query(x, y);
        int ihl = iHL.query(x, y);
        int ihp = iHP.query(x, y);
        
        DBG cout << "DL: " << idl << " DP: " << idp << " HL: " << ihl << " HP: " << ihp << endl;
        
        prev_ans = idl + idp + ihl + ihp;
        cout << prev_ans << endl;
    }
}