代码

// NOI2017 分身术 - segment tree of convex hulls + O(log) tangent bridge merge.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static const int MAXN = 100005;

static ll PX[MAXN], PY[MAXN]; // points sorted by (x,y)

static inline ll crs2(ll ax, ll ay, ll bx, ll by) { return ax*by - ay*bx; }
static inline ll crs3(int a, int b, int c) {
    return (PX[b]-PX[a])*(PY[c]-PY[b]) - (PY[b]-PY[a])*(PX[c]-PX[b]);
}

static vector<int> lo[4*MAXN], up[4*MAXN];

// ---- build merges (linear) ----
static void merge_lo(const vector<int>& A, const vector<int>& B, vector<int>& out) {
    out = A;
    for (int p : B) {
        while (out.size() >= 2 && crs3(out[out.size()-2], out.back(), p) <= 0) out.pop_back();
        out.push_back(p);
    }
}
static void merge_up(const vector<int>& A, const vector<int>& B, vector<int>& out) {
    out = A;
    for (int p : B) {
        while (out.size() >= 2 && crs3(out[out.size()-2], out.back(), p) >= 0) out.pop_back();
        out.push_back(p);
    }
}

void build(int node, int l, int r) {
    if (r - l == 1) { lo[node].push_back(l); up[node].push_back(l); return; }
    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*node+1, mid, r);
    merge_lo(lo[2*node], lo[2*node+1], lo[node]);
    merge_up(up[2*node], up[2*node+1], up[node]);
}

// ---- O(log) tangent bridge ----
// smallest j in [0,q-1] with (j==q-1 || crs3(ai,B[j],B[j+1]) < 0)
static inline int upper_tangent_j(int ai, const vector<int>& B) {
    int q = (int)B.size();
    if (q == 1) return 0;
    int l = 0, r = q-1, ans = q-1;
    while (l <= r) {
        int mid = (l+r)>>1;
        if (mid == q-1 || crs3(ai, B[mid], B[mid+1]) < 0) { ans = mid; r = mid-1; }
        else l = mid+1;
    }
    return ans;
}
// smallest j with (j==q-1 || crs3(ai,B[j],B[j+1]) > 0)
static inline int lower_tangent_j(int ai, const vector<int>& B) {
    int q = (int)B.size();
    if (q == 1) return 0;
    int l = 0, r = q-1, ans = q-1;
    while (l <= r) {
        int mid = (l+r)>>1;
        if (mid == q-1 || crs3(ai, B[mid], B[mid+1]) > 0) { ans = mid; r = mid-1; }
        else l = mid+1;
    }
    return ans;
}

static void merge_up_bridge(const vector<int>& A, const vector<int>& B, vector<int>& out) {
    if (A.empty()) { out = B; return; }
    if (B.empty()) { out = A; return; }
    int p = (int)A.size(), q = (int)B.size();
    int l = 0, r = p-1, ans = 0;
    while (l <= r) {
        int mid = (l+r)>>1;
        int j = upper_tangent_j(A[mid], B);
        bool ok = (mid == 0) || (crs3(A[mid-1], A[mid], B[j]) < 0);
        if (ok) { ans = mid; l = mid+1; } else r = mid-1;
    }
    int i = ans, j = upper_tangent_j(A[i], B);
    out.clear();
    out.reserve(i+1 + (q-j));
    for (int k = 0; k <= i; k++) out.push_back(A[k]);
    out.push_back(B[j]);
    for (int k = j+1; k < q; k++) out.push_back(B[k]);
}

static void merge_lo_bridge(const vector<int>& A, const vector<int>& B, vector<int>& out) {
    if (A.empty()) { out = B; return; }
    if (B.empty()) { out = A; return; }
    int p = (int)A.size(), q = (int)B.size();
    int l = 0, r = p-1, ans = 0;
    while (l <= r) {
        int mid = (l+r)>>1;
        int j = lower_tangent_j(A[mid], B);
        bool ok = (mid == 0) || (crs3(A[mid-1], A[mid], B[j]) > 0);
        if (ok) { ans = mid; l = mid+1; } else r = mid-1;
    }
    int i = ans, j = lower_tangent_j(A[i], B);
    out.clear();
    out.reserve(i+1 + (q-j));
    for (int k = 0; k <= i; k++) out.push_back(A[k]);
    out.push_back(B[j]);
    for (int k = j+1; k < q; k++) out.push_back(B[k]);
}

struct HullRef { const vector<int>* lo; const vector<int>* up; };

static deque<vector<int>> arena_lo, arena_up;

HullRef query(int node, int l, int r, const vector<int>& dels) {
    auto it = lower_bound(dels.begin(), dels.end(), l);
    if (it == dels.end() || *it >= r) {
        return {&lo[node], &up[node]};
    }
    if (r - l == 1) return {nullptr, nullptr};
    int mid = (l+r)/2;
    HullRef L = query(2*node, l, mid, dels);
    HullRef R = query(2*node+1, mid, r, dels);
    if (L.lo == nullptr) return R;
    if (R.lo == nullptr) return L;
    arena_lo.emplace_back();
    merge_lo_bridge(*L.lo, *R.lo, arena_lo.back());
    arena_up.emplace_back();
    merge_up_bridge(*L.up, *R.up, arena_up.back());
    return {&arena_lo.back(), &arena_up.back()};
}

// fast int reader
static char inbuf[1<<22]; static size_t inpos=0, inlen=0;
static inline char gc() { if (inpos>=inlen) { inlen = fread(inbuf,1,sizeof(inbuf),stdin); inpos=0; if(inlen==0) return 0; } return inbuf[inpos++]; }
static inline ll rd() {
    char c; while ((c=gc()) && (c<'0'||c>'9') && c!='-') ;
    if (c==0) return 0;
    int sgn=1; if (c=='-'){ sgn=-1; c=gc(); }
    ll v=0; while (c>='0'&&c<='9'){ v=v*10+(c-'0'); c=gc(); }
    return sgn*v;
}

static char outbuf[1<<22]; static size_t outpos=0;
static inline void wl(ll v) {
    if (outpos > (1<<22) - 64) { fwrite(outbuf,1,outpos,stdout); outpos=0; }
    if (v==0) { outbuf[outpos++]='0'; outbuf[outpos++]='\n'; return; }
    char tmp[32]; int t=0;
    if (v<0){ outbuf[outpos++]='-'; v=-v; }
    while (v){ tmp[t++] = '0'+(v%10); v/=10; }
    while (t) outbuf[outpos++] = tmp[--t];
    outbuf[outpos++]='\n';
}

int main() {
    int n = (int)rd();
    int m = (int)rd();
    struct Pt { ll x,y; int id; };
    static Pt ps[MAXN];
    for (int i=0;i<n;i++){ ps[i].x=rd(); ps[i].y=rd(); ps[i].id=i; }
    sort(ps, ps+n, [](const Pt&a, const Pt&b){ return a.x!=b.x ? a.x<b.x : a.y<b.y; });
    for (int i=0;i<n;i++){ PX[i]=ps[i].x; PY[i]=ps[i].y; }
    static int pos[MAXN];
    for (int i=0;i<n;i++) pos[ps[i].id] = i;

    {
        function<void(int,int,int)> b = [&](int node,int l,int r){
            if (r-l==1){ lo[node].push_back(l); up[node].push_back(l); return; }
            int mid=(l+r)/2; b(2*node,l,mid); b(2*node+1,mid,r);
            merge_lo(lo[2*node],lo[2*node+1],lo[node]);
            merge_up(up[2*node],up[2*node+1],up[node]);
        };
        b(1,0,n);
    }

    ll S = -1;
    static int dels[MAXN];
    vector<int> dv; dv.reserve(110);
    for (int q=0;q<m;q++){
        arena_lo.clear(); arena_up.clear();
        int k = (int)rd();
        int cnt=0;
        for (int j=0;j<k;j++){
            ll c = rd();
            ll v = S + c;
            v %= n; if (v<0) v += n;
            int p = (int)v;
            dels[cnt++] = pos[p];
        }
        sort(dels, dels+cnt);
        int c2=0;
        for (int j=0;j<cnt;j++){ if (j==0 || dels[j]!=dels[j-1]) dels[c2++]=dels[j]; }
        cnt=c2;
        dv.assign(dels, dels+cnt);

        HullRef h = query(1, 0, n, dv);
        const vector<int>& hl = *h.lo;
        const vector<int>& hu = *h.up;
        int L = (int)hl.size(), U = (int)hu.size();
        ll loSum = 0, upSum = 0;
        for (int i=0;i+1<L;i++){ int a=hl[i], b=hl[i+1]; loSum += PX[a]*PY[b] - PY[a]*PX[b]; }
        for (int i=0;i+1<U;i++){ int a=hu[i], b=hu[i+1]; upSum += PX[a]*PY[b] - PY[a]*PX[b]; }
        ll area = loSum - upSum;
        if (area < 0) area = -area;
        S = area;
        wl(area);
    }
    fwrite(outbuf,1,outpos,stdout);
    return 0;
}

评测结果