CEOI '20 - The Potion of Great Power

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int K = 20; // 1 in K updates will be completely recorded

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N, D, U, Q; cin >> N >> D >> U >> Q;

    vector<int> H(N);
    for (int &x : H) cin >> x;

    vector<vector<vector<int>>> records(N, {{}});
    vector<vector<pair<int, int>>> updates(N, {{0, -1}});
    // first is day. second is update: if negative, index of record, otherwise update

    // recordIndex is from 0 in this function
    auto buildState = [&](int a, int recordIndex, int lastUpdate) {
        int prevIndex = recordIndex*K;
        assert(updates[a][prevIndex].second < 0);
        assert(lastUpdate >= prevIndex && lastUpdate-prevIndex <= K); // equal to K when building next record

        vector<int> delta;
        for (size_t i = prevIndex+1; i <= lastUpdate; ++i) {
            int v = updates[a][i].second;
            delta.push_back(v);
        }
        sort(delta.begin(), delta.end());

        vector<pair<int, bool>> delta2;
        for (int i = 0; i < delta.size(); ++i) {
            if (i+1 < (int)delta.size() && delta[i] == delta[i+1]) ++i;
            else delta2.emplace_back(delta[i], false);
        }

        vector<int> result;
        for (int x : records[a][recordIndex]) {
            int id = lower_bound(delta2.begin(), delta2.end(), pair<int, bool>{x, false}) - delta2.begin();
            if (id < (int)delta2.size() && delta2[id].first == x) {
                assert(!delta2[id].second);
                delta2[id].second = true;
            } else result.push_back(x);
        }
        for (auto [x, removed] : delta2) {
            if (!removed) result.push_back(x);
        }
        return result;
    };

    auto upd = [&](int a, int b, int day) {
        if ((int)updates[a].size() % K == 0) {
            // store entire adjacency list of a once every k updates
            updates[a].emplace_back(day, b);
            vector<int> v = buildState(a, (int)records[a].size()-1, (int)updates[a].size()-1);
            updates[a].pop_back();
            records[a].push_back(v);

            updates[a].emplace_back(day, -(int)records[a].size());
        } else {
            // simply store update as toggle
            updates[a].emplace_back(day, b);
        }
    };

    for (int day = 1; day <= U; ++day) {
        int a, b; cin >> a >> b;
        upd(a, b, day);
        upd(b, a, day);
    }

    auto getFriends = [&](int a, int day) {
        int id = upper_bound(updates[a].begin(), updates[a].end(), pair<int, int>{day, INF}) - updates[a].begin();
        --id;
        int recordID = id / K; // at update recordID * K
        return buildState(a, recordID, id);
    };

    while (Q--) {
        int x, y, v; cin >> x >> y >> v;
        vector<int> a = getFriends(x, v), b = getFriends(y, v);
        // sort by H
        for (int &u : a) u = H[u];
        for (int &u : b) u = H[u];
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        int minDist = INF;
        for (int i = 0, j = 0; i < (int)a.size(); ++i) { // j is smallest s.t. b[j] >= a[i]
            while (j < (int)b.size() && b[j] < a[i]) ++j;
            if (j) minDist = min(minDist, a[i] - b[j-1]);
            if (j < (int)b.size()) minDist = min(minDist, b[j] - a[i]);
        }
        cout << minDist << endl;
    }
    return 0;
}