代码

// 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 int loLen[130];
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);

// returns 1 if found (fa,fb set), 0 if empty, -1 if fallback needed
static int findArcFast(int A, int B, int d2, int& fa, int& fb){
    int h2 = h[d2];
    if(h2 < 3) return -1;
    int LL = loLen[d2];
    auto g = [&](int t){ return crs3(A, B, vert[d2][t % h2]); };
    auto maxOn = [&](int lo,int hi){ int Ol=lo,Or=hi,l=lo,r=hi; while(r-l>2){ int m1=l+(r-l)/3, m2=r-(r-l)/3; if(g(m1)<g(m2)) l=m1; else r=m2; } int e=l; for(int t=l;t<=r;t++) if(g(t)>g(e)) e=t; if(g(Ol)>g(e)) e=Ol; if(g(Or)>g(e)) e=Or; return e; };
    auto minOn = [&](int lo,int hi){ int Ol=lo,Or=hi,l=lo,r=hi; while(r-l>2){ int m1=l+(r-l)/3, m2=r-(r-l)/3; if(g(m1)>g(m2)) l=m1; else r=m2; } int e=l; for(int t=l;t<=r;t++) if(g(t)<g(e)) e=t; if(g(Ol)<g(e)) e=Ol; if(g(Or)<g(e)) e=Or; return e; };
    int M = maxOn(0, LL-1);
    if(LL < h2){ int M2 = maxOn(LL, h2-1); if(g(M2) > g(M)) M = M2; }
    int m = minOn(0, LL-1);
    if(LL < h2){ int m2 = minOn(LL, h2-1); if(g(m2) < g(m)) m = m2; }
    ll gM = g(M), gm = g(m);
    if(gM < 0){ fa = 0; fb = h2-1; return 1; }
    if(gm > 0) return 0;
    if(gM == 0 || gm == 0) return -1;
    int start=M, end=m; if(end<start) end+=h2;
    int lo=start, hi=end;
    while(lo<hi){ int mid=(lo+hi)>>1; if(g(mid)>=0) lo=mid+1; else hi=mid; }
    fa = lo % h2;
    start=m; end=M; if(end<start) end+=h2;
    lo=start; hi=end;
    while(lo<hi){ int mid=(lo+hi)>>1; if(g(mid)<0) lo=mid+1; else hi=mid; }
    fb = (lo-1+h2) % h2;
    return 1;
}

static int findArcSlow(int A, int B, int d2, int& fa, int& fb){
    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 0;
    if(!anyNon){ fa = 0; fb = h2-1; return 1; }
    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;
    return 1;
}

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 fa, fb;
    int r = findArcFast(A, B, d2, fa, fb);
    if(r == 0) return;
    if(r == -1){ r = findArcSlow(A, B, d2, fa, fb); if(r == 0) return; }
    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]);
}

// convex chain cross-sum from A to B through the exposed set E (outside chord AB)
static ll convexChain(int A, vector<int>& E, int B){
    if(E.empty()) return cross2(A, B);
    static vector<int> pts; pts.clear();
    pts = E; pts.push_back(A); pts.push_back(B);
    sort(pts.begin(), pts.end(), [](int a,int b){ return X[a]!=X[b]?X[a]<X[b]:Y[a]<Y[b]; });
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    if(pts.size() < 3) return cross2(A, B);
    static int stk[MAXN*2]; int top=0;
    for(int idx:pts){ while(top>=2 && crs3(stk[top-2],stk[top-1],idx)<=0) top--; stk[top++]=idx; }
    int lower=top;
    for(int t=(int)pts.size()-2;t>=0;t--){ int idx=pts[t]; while(top>lower && crs3(stk[top-2],stk[top-1],idx)<=0) top--; stk[top++]=idx; }
    top--;
    int iA=-1, iB=-1;
    for(int i=0;i<top;i++){ if(stk[i]==A) iA=i; if(stk[i]==B) iB=i; }
    ll s = 0;
    if(stk[(iA+1)%top] == B){
        for(int k=iA; ; k=(k-1+top)%top){
            int nxt=(k-1+top)%top;
            s += cross2(stk[k], stk[nxt]);
            if(stk[nxt]==B) break;
        }
    } else {
        for(int k=iA; ; k=(k+1)%top){
            int nxt=(k+1)%top;
            s += cross2(stk[k], stk[nxt]);
            if(stk[nxt]==B) break;
        }
    }
    return s;
}

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(); loLen[K]=lo.size();
            pref[K].assign(2*h[K]+2, 0);
            for(int t=0;t<2*h[K]+1;t++) pref[K][t+1] = pref[K][t] + cross2(H[t % h[K]], H[(t+1)%h[K]]);
            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(); loLen[K]=rest.size();
            pref[K].assign(2*h[K]+2, 0);
            for(int t=0;t<2*h[K]+1;t++) pref[K][t+1] = pref[K][t] + cross2(rest[t % h[K]], rest[(t+1)%h[K]]);
            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);
    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]});
        }
        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());
        del0.erase(unique(del0.begin(), del0.end()), del0.end());
        ll ans = 0;
        if(del0.empty()){
            ans = pref[0][h0];
        } else {
            // group deleted L0 positions into maximal cyclic runs
            int cnt = del0.size();
            vector<pair<int,int>> runs;
            {
                int i = 0;
                while(i < cnt){
                    int p = del0[i], q = p;
                    while(i+1 < cnt && del0[i+1] == q+1) q = del0[++i];
                    runs.push_back({p, q});
                    i++;
                }
            }
            // merge cyclic wrap: first run starts at 0 and last run ends at h0-1
            if(runs.size() >= 2 && runs[0].first == 0 && runs.back().second == h0-1){
                vector<pair<int,int>> merged;
                merged.push_back({runs.back().first, runs[0].second});
                for(int j=1; j<(int)runs.size()-1; j++) merged.push_back(runs[j]);
                runs = merged;
            }
            for(auto& pr : runs){
                int p = pr.first, q = pr.second;
                int A = vert[0][(p-1+h0) % h0];
                int B = vert[0][(q+1) % h0];
                int lo = p-1; if(lo < 0) lo += h0;
                int hi = q+1; if(hi <= lo) hi += h0;
                ll oldArc = pref[0][hi] - pref[0][lo];
                static vector<int> E; E.clear();
                buildExposed(0, A, B, E);
                ll newChain = convexChain(A, E, B);
                ans += newChain - oldArc;
            }
            ans += pref[0][h0];
        }
        if(ans < 0) ans = -ans;
        S = ans;
        wl(ans);
    }
    fwrite(outbuf,1,outpos,stdout);
    return 0;
}

评测结果