代码

// 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());
}

// 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;
}

// ---- tangent + prefix-sum exposed chain ----
static int gA, gB;

static inline bool smallerAngle(int P, int a, int b){
    return (X[a]-X[P])*(Y[b]-Y[P]) - (Y[a]-Y[P])*(X[b]-X[P]) > 0;
}

static int tangentSingle(int P, int d2, int lo, int hi, bool left){
    int h2 = h[d2];
    if(hi - lo < 1) return lo;
    int l = lo, r = hi;
    while(r - l > 2){
        int m1 = l + (r-l)/3, m2 = r - (r-l)/3;
        int a = vert[d2][m1 % h2], b = vert[d2][m2 % h2];
        if(smallerAngle(P, a, b)){ if(left) r = m2; else l = m1; }
        else { if(left) l = m1; else r = m2; }
    }
    int best = l;
    for(int t=l;t<=r;t++){ int a=vert[d2][t%h2], b=vert[d2][best%h2]; if(smallerAngle(P,a,b)){ if(left) best=t; } else { if(!left) best=t; } }
    { int a=vert[d2][lo%h2], b=vert[d2][best%h2]; if(smallerAngle(P,a,b)){ if(left) best=lo; } else { if(!left) best=lo; } }
    { int a=vert[d2][hi%h2], b=vert[d2][best%h2]; if(smallerAngle(P,a,b)){ if(left) best=hi; } else { if(!left) best=hi; } }
    return best;
}

static int tangentSurviving(int P, int d2, int lo, int hi, bool left){
    static vector<int> dp; collectDeleted(d2, lo, hi, dp);
    int h2 = h[d2];
    int best = -1;
    int cur = lo;
    for(int i = 0; i <= (int)dp.size(); i++){
        int end = (i < (int)dp.size()) ? dp[i] - 1 : hi;
        if(cur <= end){
            int T = tangentSingle(P, d2, cur, end, left);
            int pos = T % h2;
            if(best == -1 || (left ? smallerAngle(P, vert[d2][pos], vert[d2][best]) : !smallerAngle(P, vert[d2][pos], vert[d2][best]))) best = pos;
        }
        cur = (i < (int)dp.size()) ? dp[i] + 1 : hi + 1;
    }
    return best;
}

static pair<int,int> tangentCombined(int P, int d2, bool left){
    if(d2 >= K) return {-1,-1};
    int fa, fb; int r = findArcFast(gA, gB, d2, fa, fb);
    if(r == 0) return {-1,-1};
    if(r == -1){ r = findArcSlow(gA, gB, d2, fa, fb); if(r == 0) return {-1,-1}; }
    int lo = fa, hi = (fb >= fa) ? fb : fb + h[d2];
    int T = tangentSurviving(P, d2, lo, hi, left);
    static vector<int> dp; collectDeleted(d2, lo, hi, dp);
    if(dp.empty()){
        if(T == -1) return {-1,-1};
        return {d2, T};
    }
    auto T2 = tangentCombined(P, d2+1, left);
    if(T == -1) return T2;
    if(T2.first == -1) return {d2, T};
    int v1 = vert[d2][T], v2 = vert[T2.first][T2.second];
    bool v1small = smallerAngle(P, v1, v2);
    if(left){ if(v1small) return {d2, T}; else return T2; }
    else { if(!v1small) return {d2, T}; else return T2; }
}

static ll interiorChain(int d, int X, int Y);
static ll exposedArea_(int d, int L, int R);
static ll chainBetween(int la, int pa, int lb, int pb);

static ll chainBetween(int la, int pa, int lb, int pb){
    if(la == lb){
        int X = pa, Y = pb; if(Y < X) Y += h[la];
        return interiorChain(la, X, Y);
    }
    if(la > lb){
        int P = vert[la][pa];
        int fa, fb; int r = findArcFast(gA, gB, lb, fa, fb);
        if(r == 0) return cross2(P, vert[lb][pb]);
        if(r == -1){ r = findArcSlow(gA, gB, lb, fa, fb); if(r == 0) return cross2(P, vert[lb][pb]); }
        int lo = fa, hi = (fb >= fa) ? fb : fb + h[lb];
        int Tb = tangentSurviving(P, lb, lo, hi, true) % h[lb];
        int X = Tb, Y = pb; if(Y < X) Y += h[lb];
        return cross2(P, vert[lb][Tb]) + interiorChain(lb, X, Y);
    } else {
        int P = vert[lb][pb];
        int fa, fb; int r = findArcFast(gA, gB, la, fa, fb);
        if(r == 0) return cross2(vert[la][pa], P);
        if(r == -1){ r = findArcSlow(gA, gB, la, fa, fb); if(r == 0) return cross2(vert[la][pa], P); }
        int lo = fa, hi = (fb >= fa) ? fb : fb + h[la];
        int Ta = tangentSurviving(P, la, lo, hi, false) % h[la];
        int X = pa, Y = Ta; if(Y < X) Y += h[la];
        return interiorChain(la, X, Y) + cross2(vert[la][Ta], P);
    }
}

static ll interiorChain(int d, int X, int Y){
    int hd = h[d];
    static vector<int> dp; collectDeleted(d, X, Y, dp);
    if(dp.empty()) return pref[d][Y] - pref[d][X];
    ll total = 0; int cur = X; 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];
        if(cur <= p-1) total += pref[d][p-1] - pref[d][cur];
        int L = (p-1 >= X) ? vert[d][(p-1) % hd] : gA;
        int R = (q+1 <= Y) ? vert[d][(q+1) % hd] : gB;
        total += exposedArea_(d, L, R);
        cur = q+1; i++;
    }
    if(cur <= Y) total += pref[d][Y] - pref[d][cur];
    return total;
}

static ll exposedArea_(int d, int L, int R){
    int d2 = d+1;
    if(d2 >= K) return cross2(L, R);
    int fa, fb; int r = findArcFast(gA, gB, d2, fa, fb);
    if(r == 0) return cross2(L, R);
    if(r == -1){ r = findArcSlow(gA, gB, d2, fa, fb); if(r == 0) return cross2(L, R); }
    auto TA = tangentCombined(L, d2, true);
    auto TB = tangentCombined(R, d2, false);
    if(TA.first == -1 || TB.first == -1) return cross2(L, R);
    int TAp = vert[TA.first][TA.second];
    int TBp = vert[TB.first][TB.second];
    if(TAp == TBp) return cross2(L, TAp) + cross2(TBp, R);
    ll ans = cross2(L, TAp);
    ans += chainBetween(TA.first, TA.second, TB.first, TB.second);
    ans += cross2(TBp, R);
    return ans;
}
// DuckInfo direct-memory IO (with local fread/fwrite fallback for local testing).
#include <sys/auxv.h>
#include <stdint.h>
struct DuckInfo {
    uint64_t abi_version;
    const char *stdin_ptr; uint64_t stdin_size;
    char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
    char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
    const char *IB_ptr; uint64_t IB_limit;
    char *OB_ptr; uint64_t OB_limit;
    uint64_t tsc_frequency;
} __attribute__((packed));

static const char* ibuf; static size_t ipos=0, ilen=0;
static char* obuf; static size_t opos=0;
static DuckInfo* duck;
static char local_in[1<<22], local_out[1<<22];

static inline char gc(){ if(ipos>=ilen) return 0; return ibuf[ipos++]; }
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 inline void wl(ll v){ if(v==0){obuf[opos++]='0';obuf[opos++]='\n';return;} char t[32];int z=0; if(v<0){obuf[opos++]='-';v=-v;} while(v){t[z++]='0'+(v%10);v/=10;} while(z)obuf[opos++]=t[--z]; obuf[opos++]='\n'; }

int main(){
    duck = (DuckInfo*)getauxval(0x6b637564);
    if(duck && duck->stdin_ptr){
        ibuf = duck->stdin_ptr; ilen = duck->stdin_size; ipos = 0;
        obuf = duck->stdout_ptr; opos = 0;
    } else {
        ilen = fread(local_in,1,sizeof(local_in),stdin); ibuf = local_in; ipos = 0;
        obuf = local_out; opos = 0;
    }
    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];
                gA = A; gB = B;
                ll newChain = exposedArea_(0, A, B);
                ans += newChain - oldArc;
            }
            ans += pref[0][h0];
        }
        if(ans < 0) ans = -ans;
        S = ans;
        wl(ans);
    }
    if(duck && duck->stdin_ptr){
        duck->stdout_size = opos;
        asm volatile("mov $60,%%rax; xor %%edi,%%edi; syscall" ::: "rax","rdi","memory");
    } else {
        fwrite(obuf,1,opos,stdout);
    }
    return 0;
}

评测结果