Hướng dẫn giải của Plinko


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int INF = 1e9;

struct Segment {
    ll l, r;
};

struct Query {
    int a, c;
    ll b, ld, rd;

    int p = -1;          // source segment
    int lq = 1, rq = 0;  // reachable candidate segment range on row c
    ll ans = 0;
    bool done = false;
};

struct Fenwick {
    int n;
    vector<ll> bit;

    Fenwick() {}
    Fenwick(int _n) {
        init(_n);
    }

    void init(int _n) {
        n = _n;
        bit.assign(n + 1, 0);
    }

    void add(int idx, ll val) {
        idx++;
        while (idx <= n) {
            bit[idx] += val;
            idx += idx & -idx;
        }
    }

    ll sumPrefix(int idx) {
        if (idx < 0) return 0;
        ll res = 0;
        idx++;
        while (idx > 0) {
            res += bit[idx];
            idx -= idx & -idx;
        }
        return res;
    }

    ll rangeSum(int l, int r) {
        if (l > r) return 0;
        return sumPrefix(r) - sumPrefix(l - 1);
    }
};

struct MinSegTree {
    int n = 0, base = 1;
    vector<int> st;

    MinSegTree() {}

    MinSegTree(int _n) {
        init(_n);
    }

    void init(int _n) {
        n = _n;
        base = 1;
        while (base < max(1, n)) base <<= 1;
        st.assign(base << 1, INF);
    }

    void update(int pos, int val) {
        if (n == 0) return;
        pos += base;
        st[pos] = val;
        for (pos >>= 1; pos; pos >>= 1) {
            st[pos] = min(st[pos << 1], st[pos << 1 | 1]);
        }
    }

    int findFirstDfs(int id, int l, int r, int ql, int qr, int lim) {
        if (r < ql || qr < l || st[id] > lim) return -1;
        if (l == r) return l < n ? l : -1;

        int mid = (l + r) >> 1;
        int res = findFirstDfs(id << 1, l, mid, ql, qr, lim);
        if (res != -1) return res;
        return findFirstDfs(id << 1 | 1, mid + 1, r, ql, qr, lim);
    }

    int findLastDfs(int id, int l, int r, int ql, int qr, int lim) {
        if (r < ql || qr < l || st[id] > lim) return -1;
        if (l == r) return l < n ? l : -1;

        int mid = (l + r) >> 1;
        int res = findLastDfs(id << 1 | 1, mid + 1, r, ql, qr, lim);
        if (res != -1) return res;
        return findLastDfs(id << 1, l, mid, ql, qr, lim);
    }

    int findFirst(int l, int r, int lim) {
        if (n == 0 || l > r) return -1;
        return findFirstDfs(1, 0, base - 1, l, r, lim);
    }

    int findLast(int l, int r, int lim) {
        if (n == 0 || l > r) return -1;
        return findLastDfs(1, 0, base - 1, l, r, lim);
    }
};

struct MiddleRequest {
    int l, r;
    int threshold;
    int qid;
};

int N, Q;
ll M;

vector<vector<Segment>> rows;
vector<vector<int>> minRowSeg, maxRowSeg;
vector<Query> queries;
vector<vector<MiddleRequest>> middleRequests;

bool overlap(const Segment &a, const Segment &b) {
    return max(a.l, b.l) < min(a.r, b.r);
}

int findSegmentContaining(int row, ll x) {
    const auto &v = rows[row];
    int lo = 0, hi = (int)v.size() - 1;
    int ans = -1;

    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (v[mid].l <= x) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    if (ans == -1) return -1;
    if (v[ans].l <= x && x < v[ans].r) return ans;
    return -1;
}

int firstSegmentWithRGreater(int row, ll x) {
    const auto &v = rows[row];
    int lo = 0, hi = (int)v.size() - 1;
    int ans = (int)v.size();

    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (v[mid].r > x) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }

    return ans;
}

int lastSegmentWithLLessEqual(int row, ll x) {
    const auto &v = rows[row];
    int lo = 0, hi = (int)v.size() - 1;
    int ans = -1;

    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (v[mid].l <= x) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return ans;
}

ll intersectionLengthWithClosedRange(int row, int segId, ll ld, ll rd) {
    const auto &s = rows[row][segId];

    ll L = max(s.l, ld);
    ll R = min(s.r, rd + 1);

    return max(0LL, R - L);
}

void computeMaxRow() {
    maxRowSeg.assign(N, {});

    for (int i = 0; i < N; i++) {
        maxRowSeg[i].assign(rows[i].size(), i);
    }

    for (int i = N - 2; i >= 0; i--) {
        const auto &cur = rows[i];
        const auto &nxt = rows[i + 1];

        int ptr = 0;
        for (int u = 0; u < (int)cur.size(); u++) {
            while (ptr < (int)nxt.size() && nxt[ptr].r <= cur[u].l) {
                ptr++;
            }

            int k = ptr;
            while (k < (int)nxt.size() && nxt[k].l < cur[u].r) {
                maxRowSeg[i][u] = max(maxRowSeg[i][u], maxRowSeg[i + 1][k]);
                k++;
            }
        }
    }
}

void computeMinRow() {
    minRowSeg.assign(N, {});

    for (int i = 0; i < N; i++) {
        minRowSeg[i].assign(rows[i].size(), i);
    }

    for (int i = 1; i < N; i++) {
        const auto &cur = rows[i];
        const auto &pre = rows[i - 1];

        int ptr = 0;
        for (int u = 0; u < (int)cur.size(); u++) {
            while (ptr < (int)pre.size() && pre[ptr].r <= cur[u].l) {
                ptr++;
            }

            int k = ptr;
            while (k < (int)pre.size() && pre[k].l < cur[u].r) {
                minRowSeg[i][u] = min(minRowSeg[i][u], minRowSeg[i - 1][k]);
                k++;
            }
        }
    }
}

void solveDnc(int top, int bot, const vector<int> &qids) {
    if (qids.empty() || top > bot) return;

    int mid = (top + bot) >> 1;

    vector<int> leftQ, rightQ, crossQ;
    leftQ.reserve(qids.size());
    rightQ.reserve(qids.size());
    crossQ.reserve(qids.size());

    for (int id : qids) {
        const Query &q = queries[id];

        if (q.c < mid) leftQ.push_back(id);
        else if (q.a > mid) rightQ.push_back(id);
        else crossQ.push_back(id);
    }

    // Very important optimization: if no query is answered at this node,
    // do not build lt/rt for the whole interval.
    if (crossQ.empty()) {
        solveDnc(top, mid - 1, leftQ);
        solveDnc(mid + 1, bot, rightQ);
        return;
    }

    int len = bot - top + 1;

    vector<vector<int>> lt(len), rt(len);

    for (int i = top; i <= bot; i++) {
        int idx = i - top;
        int s = (int)rows[i].size();
        lt[idx].assign(s, INF);
        rt[idx].assign(s, -1);
    }

    {
        int idx = mid - top;
        for (int j = 0; j < (int)rows[mid].size(); j++) {
            lt[idx][j] = rt[idx][j] = j;
        }
    }

    for (int i = mid - 1; i >= top; i--) {
        const auto &cur = rows[i];
        const auto &nxt = rows[i + 1];

        int curIdx = i - top;
        int nxtIdx = i + 1 - top;

        int ptr = 0;
        for (int u = 0; u < (int)cur.size(); u++) {
            while (ptr < (int)nxt.size() && nxt[ptr].r <= cur[u].l) ptr++;

            int k = ptr;
            int bestL = INF, bestR = -1;
            while (k < (int)nxt.size() && nxt[k].l < cur[u].r) {
                if (lt[nxtIdx][k] != INF) {
                    bestL = min(bestL, lt[nxtIdx][k]);
                    bestR = max(bestR, rt[nxtIdx][k]);
                }
                k++;
            }
            lt[curIdx][u] = bestL;
            rt[curIdx][u] = bestR;
        }
    }

    for (int i = mid + 1; i <= bot; i++) {
        const auto &cur = rows[i];
        const auto &pre = rows[i - 1];

        int curIdx = i - top;
        int preIdx = i - 1 - top;

        int ptr = 0;
        for (int u = 0; u < (int)cur.size(); u++) {
            while (ptr < (int)pre.size() && pre[ptr].r <= cur[u].l) ptr++;

            int k = ptr;
            int bestL = INF, bestR = -1;
            while (k < (int)pre.size() && pre[k].l < cur[u].r) {
                if (lt[preIdx][k] != INF) {
                    bestL = min(bestL, lt[preIdx][k]);
                    bestR = max(bestR, rt[preIdx][k]);
                }
                k++;
            }
            lt[curIdx][u] = bestL;
            rt[curIdx][u] = bestR;
        }
    }

    // Build valid lists only for target rows that actually appear in crossing queries.
    vector<int> targetRows;
    targetRows.reserve(crossQ.size());
    for (int id : crossQ) targetRows.push_back(queries[id].c);
    sort(targetRows.begin(), targetRows.end());
    targetRows.erase(unique(targetRows.begin(), targetRows.end()), targetRows.end());

    vector<vector<int>> validIdx(targetRows.size()), validLt(targetRows.size()), validRt(targetRows.size());

    for (int t = 0; t < (int)targetRows.size(); t++) {
        int row = targetRows[t];
        int idx = row - top;
        int S = (int)rows[row].size();

        validIdx[t].reserve(S);
        validLt[t].reserve(S);
        validRt[t].reserve(S);

        for (int j = 0; j < S; j++) {
            if (lt[idx][j] != INF) {
                validIdx[t].push_back(j);
                validLt[t].push_back(lt[idx][j]);
                validRt[t].push_back(rt[idx][j]);
            }
        }
    }

    if (!rows[mid].empty()) {
        vector<int> segOrder(rows[mid].size());
        iota(segOrder.begin(), segOrder.end(), 0);

        sort(segOrder.begin(), segOrder.end(), [&](int x, int y) {
            return maxRowSeg[mid][x] > maxRowSeg[mid][y];
        });

        sort(crossQ.begin(), crossQ.end(), [&](int x, int y) {
            return queries[x].c > queries[y].c;
        });

        MinSegTree st((int)rows[mid].size());
        int ptr = 0;

        for (int id : crossQ) {
            Query &q = queries[id];

            while (ptr < (int)segOrder.size() && maxRowSeg[mid][segOrder[ptr]] >= q.c) {
                int s = segOrder[ptr];
                st.update(s, minRowSeg[mid][s]);
                ptr++;
            }

            int sourceRowIdx = q.a - top;
            int p = q.p;

            if (p < 0 || p >= (int)lt[sourceRowIdx].size()) {
                q.lq = 1;
                q.rq = 0;
                continue;
            }

            int AL = lt[sourceRowIdx][p];
            int AR = rt[sourceRowIdx][p];

            if (AL == INF || AL > AR) {
                q.lq = 1;
                q.rq = 0;
                continue;
            }

            int lst = st.findFirst(AL, AR, q.a);
            int rst = st.findLast(AL, AR, q.a);

            if (lst == -1 || rst == -1 || lst > rst) {
                q.lq = 1;
                q.rq = 0;
                continue;
            }

            int t = (int)(lower_bound(targetRows.begin(), targetRows.end(), q.c) - targetRows.begin());
            auto &vIdx = validIdx[t];
            auto &vLt = validLt[t];
            auto &vRt = validRt[t];

            if (vIdx.empty()) {
                q.lq = 1;
                q.rq = 0;
                continue;
            }

            int posL = (int)(lower_bound(vRt.begin(), vRt.end(), lst) - vRt.begin());
            int posR = (int)(upper_bound(vLt.begin(), vLt.end(), rst) - vLt.begin()) - 1;

            if (posL > posR) {
                q.lq = 1;
                q.rq = 0;
            } else {
                q.lq = vIdx[posL];
                q.rq = vIdx[posR];
            }
        }
    } else {
        for (int id : crossQ) {
            queries[id].lq = 1;
            queries[id].rq = 0;
        }
    }

    solveDnc(top, mid - 1, leftQ);
    solveDnc(mid + 1, bot, rightQ);
}

bool reachableSegmentForQuery(const Query &q, int segId) {
    if (q.lq > q.rq) return false;
    if (segId < q.lq || segId > q.rq) return false;
    return minRowSeg[q.c][segId] <= q.a;
}

void buildFinalCountingRequests() {
    middleRequests.assign(N, {});

    for (int id = 0; id < Q; id++) {
        Query &q = queries[id];

        if (q.done) continue;
        if (q.lq > q.rq) continue;
        if (rows[q.c].empty()) continue;

        int pld = firstSegmentWithRGreater(q.c, q.ld);
        int prd = lastSegmentWithLLessEqual(q.c, q.rd);

        if (pld >= (int)rows[q.c].size() || prd < 0 || pld > prd) {
            continue;
        }

        if (!overlap(rows[q.c][pld], Segment{q.ld, q.rd + 1})) {
            continue;
        }

        if (!overlap(rows[q.c][prd], Segment{q.ld, q.rd + 1})) {
            continue;
        }

        if (pld == prd) {
            if (reachableSegmentForQuery(q, pld)) {
                q.ans += intersectionLengthWithClosedRange(q.c, pld, q.ld, q.rd);
            }
            continue;
        }

        if (reachableSegmentForQuery(q, pld)) {
            q.ans += intersectionLengthWithClosedRange(q.c, pld, q.ld, q.rd);
        }

        if (reachableSegmentForQuery(q, prd)) {
            q.ans += intersectionLengthWithClosedRange(q.c, prd, q.ld, q.rd);
        }

        int L = max(q.lq, pld + 1);
        int R = min(q.rq, prd - 1);

        if (L <= R) {
            middleRequests[q.c].push_back({L, R, q.a, id});
        }
    }
}

void processFinalCountingRequests() {
    for (int row = 0; row < N; row++) {
        auto &reqs = middleRequests[row];
        if (reqs.empty()) continue;

        int S = rows[row].size();

        vector<int> ord(S);
        iota(ord.begin(), ord.end(), 0);

        sort(ord.begin(), ord.end(), [&](int x, int y) {
            return minRowSeg[row][x] < minRowSeg[row][y];
        });

        sort(reqs.begin(), reqs.end(), [&](const MiddleRequest &x, const MiddleRequest &y) {
            return x.threshold < y.threshold;
        });

        Fenwick fw(S);
        int ptr = 0;

        for (const auto &req : reqs) {
            while (ptr < S && minRowSeg[row][ord[ptr]] <= req.threshold) {
                int s = ord[ptr];
                fw.add(s, rows[row][s].r - rows[row][s].l);
                ptr++;
            }

            queries[req.qid].ans += fw.rangeSum(req.l, req.r);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("sample.in","r",stdin);
    //freopen("sample.out","w",stdout);

    cin >> N >> M;

    rows.assign(N, {});

    for (int i = 0; i < N; i++) {
        int S;
        cin >> S;

        rows[i].resize(S);
        for (int j = 0; j < S; j++) {
            cin >> rows[i][j].l >> rows[i][j].r;
        }
    }

    computeMaxRow();
    computeMinRow();

    cin >> Q;
    queries.resize(Q);

    vector<int> activeQueries;

    for (int id = 0; id < Q; id++) {
        Query &q = queries[id];
        cin >> q.a >> q.b >> q.c >> q.ld >> q.rd;

        q.p = findSegmentContaining(q.a, q.b);

        if (q.p == -1) {
            q.ans = 0;
            q.done = true;
            continue;
        }

        if (q.a == q.c) {
            q.ans = intersectionLengthWithClosedRange(q.a, q.p, q.ld, q.rd);
            q.done = true;
            continue;
        }

        activeQueries.push_back(id);
    }

    solveDnc(0, N - 1, activeQueries);

    buildFinalCountingRequests();
    processFinalCountingRequests();

    for (int i = 0; i < Q; i++) {
        cout << queries[i].ans << '\n';
    }

    return 0;
}

Loading...