代码

// noi17f 【NOI2017】分身术
// Every query state is P \ D_t with |D_t| <= 100 (deleted points are restored each step),
// so a deleted point strictly inside hull(P) cannot change the answer: the answer is
// area(hull(P)) unless D_t removes vertices of hull(P) =: H0.
// Answer = shoelace over the surviving arcs of H0 plus, for every maximal deleted run
// (x = v_{a-1}, y = v_{b+1}), the convex chain of alive points inside cap(x,y) (the region
// right of chord x->y).  That chain is produced by quickhull: repeatedly take the alive
// point farthest from the current chord.  "Alive support in direction d" is answered with
// the onion layers (L_1 = H0, L_2 = hull(P\L_1), ...): min over L_j of a linear function is
// non-decreasing in j, so the walk stops as soon as no deeper layer can improve.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <sys/auxv.h>
using namespace std;
typedef long long ll;
typedef unsigned long long u64;

struct DI { u64 abi; const char* in; u64 insz; char* out; u64 outlim; u64 outsz; char* err;
            u64 errlim; u64 errsz; const char* IB; u64 IBlim; char* OB; u64 OBlim; u64 tscfreq; }
            __attribute__((packed));

static const int MAXN = 100005;
static const int MAXLAY = 512;

static int n, m;
static int px[MAXN], py[MAXN];
static int ordr[MAXN];
static unsigned char del_[MAXN], used_[MAXN];
static int layerOf[MAXN], idxIn[MAXN];
static int hh;
static int hp[MAXN];
static int hpos[MAXN];
static ll areaH0;
static int scratch[MAXN];

static vector<int> lay[MAXLAY + 2];
static int iminIdx[MAXLAY + 2], imaxIdx[MAXLAY + 2];
static int nlay = 0;
static bool capHit = false;
static int leftPts[MAXN];
static int nleft = 0;
static bool leftDone = false;

static char *ib, *ibEnd;
static inline int rd() {
    while (ib < ibEnd && (unsigned char)*ib <= ' ') ib++;
    int sgn = 1;
    if (ib < ibEnd && *ib == '-') { sgn = -1; ib++; }
    int v = 0;
    while (ib < ibEnd && (unsigned char)*ib >= '0') { v = v * 10 + (*ib - '0'); ib++; }
    return v * sgn;
}

static inline ll cr(int a, int b, int c) {
    return (ll)(px[b] - px[a]) * (ll)(py[c] - py[a]) - (ll)(py[b] - py[a]) * (ll)(px[c] - px[a]);
}
static inline ll crossv(int a, int b) { return (ll)px[a] * py[b] - (ll)py[a] * px[b]; }
static inline ll dotv(int id, ll dx, ll dy) { return (ll)px[id] * dx + (ll)py[id] * dy; }

// convex hull of points with used_==0, strict turns, CCW -> scratch, returns size
static int buildHull() {
    int hn = 0;
    for (int t = 0; t < n; t++) {
        int id = ordr[t];
        if (used_[id]) continue;
        while (hn >= 2 && cr(scratch[hn - 2], scratch[hn - 1], id) <= 0) hn--;
        scratch[hn++] = id;
    }
    if (hn < 2) return hn;      // 0 or 1 usable point
    int low = hn;
    int las = n - 1;
    while (used_[ordr[las]]) las--;
    for (int t = las - 1; t >= 0; t--) {
        int id = ordr[t];
        if (used_[id]) continue;
        while (hn >= low + 1 && cr(scratch[hn - 2], scratch[hn - 1], id) <= 0) hn--;
        scratch[hn++] = id;
    }
    hn--;
    return hn;
}

static void assignLayer(int j, int hn) {
    lay[j].assign(scratch, scratch + hn);
    for (int i = 0; i < hn; i++) {
        int id = scratch[i];
        used_[id] = 1; layerOf[id] = j; idxIn[id] = i;
    }
    int imn = 0, imx = 0;
    for (int i = 1; i < hn; i++) {
        int a = scratch[i];
        if (px[a] < px[scratch[imn]] || (px[a] == px[scratch[imn]] && py[a] < py[scratch[imn]])) imn = i;
        if (px[a] > px[scratch[imx]] || (px[a] == px[scratch[imx]] && py[a] > py[scratch[imx]])) imx = i;
    }
    iminIdx[j] = imn; imaxIdx[j] = imx;
}

static bool buildNextLayer() {
    if (leftDone) return false;
    if (nlay >= MAXLAY) { capHit = true; leftDone = true; return false; }
    int hn = buildHull();
    if (hn < 3) {   // remaining points are collinear (or <=2): they live on one line
        nleft = 0;
        for (int t = 0; t < n; t++) {
            int id = ordr[t];
            if (!used_[id]) leftPts[nleft++] = id;   // x-sorted == order along the line
        }
        leftDone = true;
        return false;
    }
    nlay++;
    assignLayer(nlay, hn);
    return true;
}

// argmin of (dx,dy).p over polygon of layer j  (polygon stored CCW; s>=3 convex)
static void argminLayer(int j, ll dx, ll dy, ll &bestVal, int &bestId) {
    const vector<int> &L = lay[j];
    int s = (int)L.size();
    if (s <= 8) {
        bestVal = (ll)4e18; bestId = -1;
        for (int i = 0; i < s; i++) {
            ll v = dotv(L[i], dx, dy);
            if (v < bestVal) { bestVal = v; bestId = L[i]; }
        }
        return;
    }
    int imn = iminIdx[j], imx = imaxIdx[j];
    bestVal = (ll)4e18; bestId = -1;
    {   // chain imn -> imx counter-clockwise (x non-decreasing)
        int len = ((imx - imn) % s + s) % s;
        int lo = 0, hi = len;
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            ll g1 = dotv(L[(imn + mid) % s], dx, dy);
            ll g2 = dotv(L[(imn + mid + 1) % s], dx, dy);
            if (g1 < g2) hi = mid; else lo = mid + 1;
        }
        ll g = dotv(L[(imn + lo) % s], dx, dy);
        if (g < bestVal) { bestVal = g; bestId = L[(imn + lo) % s]; }
    }
    {   // chain imn -> imx clockwise (x non-decreasing as well)
        int len = ((imn - imx) % s + s) % s;
        int lo = 0, hi = len;
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            ll g1 = dotv(L[((imn - mid) % s + s) % s], dx, dy);
            ll g2 = dotv(L[((imn - mid - 1) % s + s) % s], dx, dy);
            if (g1 < g2) hi = mid; else lo = mid + 1;
        }
        ll g = dotv(L[((imn - lo) % s + s) % s], dx, dy);
        if (g < bestVal) { bestVal = g; bestId = L[((imn - lo) % s + s) % s]; }
    }
}

static long long suppBudget = 0;
static bool budgetOut = false;
static int qdel[128];
static int qcnt;
static int bucketTag[MAXLAY + 2];
static int curTag = 0;
static vector<int> bucket[MAXLAY + 2];

// min of (dx,dy).p over alive points; returns value, sets bp to argmin (-1 if none)
static ll aliveSupport(ll dx, ll dy, int &bp) {
    if (--suppBudget <= 0) { budgetOut = true; return (ll)4e18; }
    ll best = (ll)4e18;
    bp = -1;
    for (int j = 1;; j++) {
        if (j > nlay) {
            if (!buildNextLayer()) {
                if (capHit) {
                    for (int id = 0; id < n; id++)
                        if (layerOf[id] < 0 && !del_[id]) {
                            ll v = dotv(id, dx, dy);
                            if (v < best) { best = v; bp = id; }
                        }
                } else if (nleft > 0) {
                    // collinear leftover: (dx,dy).p is monotone along leftPts
                    ll f0 = dotv(leftPts[0], dx, dy);
                    ll fl = dotv(leftPts[nleft - 1], dx, dy);
                    int step = (f0 <= fl) ? 1 : -1;
                    int i = (step == 1) ? 0 : nleft - 1;
                    while (i >= 0 && i < nleft && del_[leftPts[i]]) i += step;
                    if (i >= 0 && i < nleft) {
                        ll v = dotv(leftPts[i], dx, dy);
                        if (v < best) { best = v; bp = leftPts[i]; }
                    }
                }
                break;
            }
        }
        ll mu; int q;
        argminLayer(j, dx, dy, mu, q);
        if (mu >= best) break;
        ll nu = (ll)4e18; int np = -1;
        if (!del_[q]) { nu = mu; np = q; }
        else {
            const vector<int> &L = lay[j];
            int s = (int)L.size();
            if (bucketTag[j] != curTag) {
                bucketTag[j] = curTag;
                bucket[j].clear();
                for (int t = 0; t < qcnt; t++) {
                    int id = qdel[t];
                    if (layerOf[id] == j) bucket[j].push_back(idxIn[id]);
                }
                sort(bucket[j].begin(), bucket[j].end());
            }
            for (size_t z = 0; z < bucket[j].size(); z++) {
                int t = bucket[j][z];
                int c1 = L[(t - 1 + s) % s], c2 = L[(t + 1) % s];
                if (!del_[c1]) { ll v = dotv(c1, dx, dy); if (v < nu) { nu = v; np = c1; } }
                if (!del_[c2]) { ll v = dotv(c2, dx, dy); if (v < nu) { nu = v; np = c2; } }
            }
        }
        if (np >= 0 && nu < best) { best = nu; bp = np; }
    }
    return best;
}

static int stkA[2 * MAXN + 8], stkB[2 * MAXN + 8];

// cross sum of the convex chain from x to y inside cap(x,y) (endpoints included)
static int gapStepLimit = 3000;
static ll chainCross(int x, int y) {
    ll sum = 0;
    int sp = 0, steps = 0;
    stkA[sp] = x; stkB[sp] = y; sp++;
    while (sp) {
        if (budgetOut) return 0;
        if (++steps > gapStepLimit) { budgetOut = true; return 0; }
        sp--;
        int a = stkA[sp], b = stkB[sp];
        ll dx = (ll)py[a] - py[b];
        ll dy = (ll)px[b] - px[a];
        int p;
        ll mv = aliveSupport(dx, dy, p);
        ll fa = dotv(a, dx, dy);
        if (p < 0 || mv >= fa) sum += crossv(a, b);
        else {
            stkA[sp] = p; stkB[sp] = b; sp++;
            stkA[sp] = a; stkB[sp] = p; sp++;
        }
    }
    return sum;
}

static char ob[1 << 22];
static char *op = ob;
static inline void wnum(ll v) {
    char tmp[24];
    int l = 0;
    if (v == 0) tmp[l++] = '0';
    while (v) { tmp[l++] = char('0' + v % 10); v /= 10; }
    while (l) *op++ = tmp[--l];
    *op++ = '\n';
}

static int dhl[128];

int main() {
    DI *di = (DI *)getauxval(0x6b637564);
    static char *fbuf = 0;
    if (di && di->in) { ib = (char *)di->in; ibEnd = ib + di->insz; }
    else {
        fbuf = (char *)malloc(64 << 20);
        size_t got = fread(fbuf, 1, 64 << 20, stdin);
        ib = fbuf; ibEnd = fbuf + got;
    }
    n = rd(); m = rd();
    for (int i = 0; i < n; i++) { px[i] = rd(); py[i] = rd(); ordr[i] = i; }
    sort(ordr, ordr + n, [](int a, int b) {
        return px[a] != px[b] ? px[a] < px[b] : py[a] < py[b];
    });
    // layer 1 = hull(P)
    int hn = buildHull();
    nlay = 1;
    assignLayer(1, hn);
    hh = hn;
    for (int i = 0; i < n; i++) hpos[i] = -1;
    for (int i = 0; i < hh; i++) { hp[i] = scratch[i]; hpos[scratch[i]] = i; }
    areaH0 = 0;
    for (int i = 0; i < hh; i++) areaH0 += crossv(hp[i], hp[i + 1 == hh ? 0 : i + 1]);
    if (areaH0 < 0) areaH0 = -areaH0;

    ll S = -1;
    for (int step = 0; step < m; step++) {
        int k = rd();
        qcnt = 0;
        int dcnt = 0;
        for (int j = 0; j < k; j++) {
            int c = rd();
            ll t = S + (ll)c;
            int id = (int)(((t % n) + n) % n);
            if (!del_[id]) {
                del_[id] = 1;
                qdel[qcnt++] = id;
                if (hpos[id] >= 0) dhl[dcnt++] = hpos[id];
            }
        }
        curTag++;
        ll area;
        suppBudget = 20000;
        budgetOut = false;
        if (dcnt == 0) area = areaH0;
        else if (dcnt >= hh - 1) {
            // degenerate (violates the statement's guarantee): full rebuild
            int hn2 = 0;
            for (int t = 0; t < n; t++) {
                int id = ordr[t];
                if (del_[id]) continue;
                while (hn2 >= 2 && cr(scratch[hn2 - 2], scratch[hn2 - 1], id) <= 0) hn2--;
                scratch[hn2++] = id;
            }
            if (hn2 >= 2) {
                int low = hn2;
                for (int t = n - 2; t >= 0; t--) {
                    int id = ordr[t];
                    if (del_[id]) continue;
                    while (hn2 >= low + 1 && cr(scratch[hn2 - 2], scratch[hn2 - 1], id) <= 0) hn2--;
                    scratch[hn2++] = id;
                }
                hn2--;
            }
            ll s = 0;
            if (hn2 >= 3)
                for (int i = 0; i < hn2; i++) s += crossv(scratch[i], scratch[i + 1 == hn2 ? 0 : i + 1]);
            area = s < 0 ? -s : s;
        }
        else {
            sort(dhl, dhl + dcnt);
            ll total = areaH0;
            for (int i = 0; i < dcnt; i++) {
                int prev = dhl[(i + dcnt - 1) % dcnt];
                if (prev == (dhl[i] - 1 + hh) % hh) continue;   // not a run start
                int a = dhl[i];
                int b = a, idx = i, len = 1;
                while (len < dcnt) {
                    int nxtIdx = (idx + 1) % dcnt;
                    if (nxtIdx == i) break;
                    if (dhl[nxtIdx] == (b + 1) % hh) { b = dhl[nxtIdx]; idx = nxtIdx; len++; }
                    else break;
                }
                int x = hp[(a - 1 + hh) % hh];
                int y = hp[(b + 1) % hh];
                ll removed = crossv(x, hp[a]);
                if (a != b) {
                    int t = a;
                    while (t != b) { int tn = (t + 1) % hh; removed += crossv(hp[t], hp[tn]); t = tn; }
                } else {
                    // single vertex run: edges x->v_a and v_a->y
                }
                removed += crossv(hp[b], y);
                ll chain = chainCross(x, y);
                total += chain - removed;
            }
            if (budgetOut) {
                // long cap chains: a plain O(n) hull rebuild is cheaper
                int hn2 = 0;
                for (int t = 0; t < n; t++) {
                    int id = ordr[t];
                    if (del_[id]) continue;
                    while (hn2 >= 2 && cr(scratch[hn2 - 2], scratch[hn2 - 1], id) <= 0) hn2--;
                    scratch[hn2++] = id;
                }
                if (hn2 >= 2) {
                    int low = hn2;
                    for (int t = n - 2; t >= 0; t--) {
                        int id = ordr[t];
                        if (del_[id]) continue;
                        while (hn2 >= low + 1 && cr(scratch[hn2 - 2], scratch[hn2 - 1], id) <= 0) hn2--;
                        scratch[hn2++] = id;
                    }
                    hn2--;
                }
                ll s = 0;
                if (hn2 >= 3)
                    for (int i = 0; i < hn2; i++) s += crossv(scratch[i], scratch[i + 1 == hn2 ? 0 : i + 1]);
                area = s < 0 ? -s : s;
            } else {
                area = total;
                if (area < 0) area = -area;
            }
        }
        wnum(area);
        S = area;
        for (int j = 0; j < qcnt; j++) del_[qdel[j]] = 0;
        if (op - ob > (1 << 22) - 64) { fwrite(ob, 1, op - ob, stdout); op = ob; }
    }
    fwrite(ob, 1, op - ob, stdout);
    return 0;
}

评测结果