代码

// NOI2017 分身术 - convex layers + materialize exposed chain + Graham scan (correctness-first).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int MAXN = 100005;
static ll X[MAXN], Y[MAXN];
static inline ll crs3(int a,int b,int c){ return (X[b]-X[a])*(Y[c]-Y[b])-(Y[b]-Y[a])*(X[c]-X[b]); }
static inline ll cross2(int a,int b){ return X[a]*Y[b]-Y[a]*X[b]; }

static int K;
static vector<int> vert[130];
static int h[130];
static vector<ll> pref[130];
static int layer_of[MAXN], pos_of[MAXN];
static vector<pair<int,int>> dels;
static int n, m;

static void collectDeleted(int d, int lo, int hi, vector<int>& out){
    out.clear();
    int hd = h[d];
    for(auto& pr : dels){
        if(pr.first != d) continue;
        int p = pr.second;
        if(lo <= p && p <= hi) out.push_back(p);
        if(lo <= p+hd && p+hd <= hi) out.push_back(p+hd);
    }
    sort(out.begin(), out.end());
    out.erase(unique(out.begin(), out.end()), out.end());
}

// append exposed chain (surviving layer-d2 f<0 + recursive dips) between anchors A,B (excluding A,B).
// A,B are points (indices into global X/Y). d2 = layer whose f<0 we consider.
static void buildArc(int d2, int lo, int hi, int anchorL, int anchorR, vector<int>& out);

static void buildExposed(int d, int A, int B, vector<int>& out){
    int d2 = d+1;
    if(d2 >= K) return;
    int h2 = h[d2];
    int e0 = -1; bool anyNon = false;
    for(int t=0;t<h2;t++){ if(crs3(A,B,vert[d2][t]) < 0){ if(e0<0)e0=t; } else anyNon = true; }
    if(e0 == -1) return;
    int fa, fb;
    if(!anyNon){ fa = 0; fb = h2-1; }
    else {
        fa = e0; fb = e0;
        for(int st=0; st<h2 && crs3(A,B,vert[d2][(fb+1)%h2])<0; st++) fb=(fb+1)%h2;
        for(int st=0; st<h2 && crs3(A,B,vert[d2][(fa-1+h2)%h2])<0; st++) fa=(fa-1+h2)%h2;
    }
    int lo = fa, hi = (fb >= fa) ? fb : fb + h2;
    buildArc(d2, lo, hi, A, B, out);
}

static void buildArc(int d2, int lo, int hi, int A, int B, vector<int>& out){
    int h2 = h[d2];
    vector<int> dp; collectDeleted(d2, lo, hi, dp);
    if(dp.empty()){
        for(int t=lo;t<=hi;t++) out.push_back(vert[d2][t % h2]);
        return;
    }
    int cur = lo;
    int i = 0;
    while(i < (int)dp.size()){
        int p = dp[i], q = p;
        while(i+1 < (int)dp.size() && dp[i+1] == q+1) q = dp[++i];
        for(int t=cur;t<=p-1;t++) out.push_back(vert[d2][t % h2]);
        buildExposed(d2, A, B, out);
        cur = q+1;
        i++;
    }
    for(int t=cur;t<=hi;t++) out.push_back(vert[d2][t % h2]);
}

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 s=1; if(c=='-'){s=-1;c=gc();} ll v=0; while(c>='0'&&c<='9'){v=v*10+(c-'0');c=gc();} return s*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 t[32];int z=0; if(v<0){outbuf[outpos++]='-';v=-v;} while(v){t[z++]='0'+(v%10);v/=10;} while(z)outbuf[outpos++]=t[--z]; outbuf[outpos++]='\n'; }

int main(){
    n = (int)rd(); m = (int)rd();
    for(int i=0;i<n;i++){ X[i]=rd(); Y[i]=rd(); layer_of[i]=-1; }
    {
        vector<char> used(n,0);
        int rem = n; K = 0;
        while(rem >= 3 && K < 120){
            vector<int> cur;
            for(int i=0;i<n;i++) if(!used[i]) cur.push_back(i);
            sort(cur.begin(), cur.end(), [](int a,int b){ return X[a]!=X[b]?X[a]<X[b]:Y[a]<Y[b]; });
            int sz = cur.size();
            vector<int> lo;
            for(int idx:cur){ while(lo.size()>=2 && crs3(lo[lo.size()-2],lo.back(),idx)<=0) lo.pop_back(); lo.push_back(idx); }
            vector<int> up;
            for(int t=sz-1;t>=0;t--){ int idx=cur[t]; while(up.size()>=2 && crs3(up[up.size()-2],up.back(),idx)<=0) up.pop_back(); up.push_back(idx); }
            vector<int> H = lo;
            for(int t=1;t<(int)up.size()-1;t++) H.push_back(up[t]);
            if(H.size() < 3) break;
            vert[K]=H; h[K]=H.size();
            for(int t=0;t<h[K];t++){ layer_of[H[t]]=K; pos_of[H[t]]=t; used[H[t]]=1; }
            K++; rem -= H.size();
        }
        if(rem>0){
            vector<int> rest;
            for(int i=0;i<n;i++) if(!used[i]) rest.push_back(i);
            sort(rest.begin(), rest.end(), [](int a,int b){ return X[a]!=X[b]?X[a]<X[b]:Y[a]<Y[b]; });
            vert[K]=rest; h[K]=rest.size();
            for(int t=0;t<h[K];t++){ layer_of[rest[t]]=K; pos_of[rest[t]]=t; }
            K++;
        }
    }
    ll S = -1;
    dels.reserve(110);
    static vector<int> hull; hull.reserve(MAXN*2);
    for(int q=0;q<m;q++){
        int k = (int)rd();
        dels.clear();
        for(int j=0;j<k;j++){
            ll c = rd(); ll v = S + c; v %= n; if(v<0) v += n;
            int id = (int)v;
            if(layer_of[id] >= 0) dels.push_back({layer_of[id], pos_of[id]});
        }
        // build new hull in CCW order: surviving L0 + exposed
        int h0 = h[0];
        vector<int> del0;
        for(auto& pr : dels) if(pr.first==0) del0.push_back(pr.second);
        sort(del0.begin(), del0.end());
        hull.clear();
        int sz = 0;
        vector<int> surv;
        for(int t=0;t<h0;t++) if(!binary_search(del0.begin(), del0.end(), t)) surv.push_back(t);
        if(surv.size() <= 1){
            // degenerate (won't happen under the >=2-surviving guarantee): brute force
            for(int i=0;i<n;i++){ bool del=false; for(auto& pr : dels) if(vert[pr.first][pr.second]==i){ del=true; break; } if(!del) hull.push_back(i); }
        } else {
            int ssz = surv.size();
            for(int t=0;t<ssz;t++){
                int Xp = surv[t];
                int Yp = surv[(t+1)%ssz];
                hull.push_back(vert[0][Xp]);
                int A = vert[0][Xp];
                int B = vert[0][Yp];
                buildExposed(0, A, B, hull);
            }
        }
        // Andrew's convex hull of 'hull' (already CCW-ish but may have interior points) -> area
        ll ans = 0;
        if(hull.size() >= 3){
            sort(hull.begin(), hull.end(), [](int a,int b){ return X[a]!=X[b]?X[a]<X[b]:Y[a]<Y[b]; });
            hull.erase(unique(hull.begin(), hull.end()), hull.end());
            int hs = hull.size();
            if(hs >= 3){
                static int stk[MAXN*2];
                int top = 0;
                for(int idx : hull){
                    while(top>=2 && crs3(stk[top-2], stk[top-1], idx)<=0) top--;
                    stk[top++] = idx;
                }
                int lower = top;
                for(int t=hs-2;t>=0;t--){
                    int idx = hull[t];
                    while(top>lower && crs3(stk[top-2], stk[top-1], idx)<=0) top--;
                    stk[top++] = idx;
                }
                top--;
                ll s2 = 0;
                for(int i=0;i<top;i++) s2 += cross2(stk[i], stk[(i+1)%top]);
                if(s2<0) s2=-s2;
                ans = s2;
            }
        }
        S = ans;
        wl(ans);
    }
    fwrite(outbuf,1,outpos,stdout);
    return 0;
}

评测结果