代码

// NOI2017 分身术 - full-envelope solution: compute the lower hull and upper hull of the
// surviving points independently via an x-monotone merge of each onion layer's pure
// lower/upper chains in vertical (bottom-to-top / top-to-bottom) order, then subtract.
// This is the editorial's x-monotone upper/lower split: each hull is split into two
// strictly-x-monotone chains, the recursion is clipped by X-intervals along disjoint
// x-ranges (so O(k) nodes per query, never exponential), and consecutive chains are merged
// with a two-chain common tangent (lower/upper bridge). Handles straddling gaps (deleted
// leftmost/rightmost hull vertices) naturally because there is no per-gap decomposition.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int MAXN = 100005;
static const int MAXK = 130;
static const int PEEL = 105;
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 inline ll crsP(int o,int a,int b){ return (X[a]-X[o])*(Y[b]-Y[o])-(Y[a]-Y[o])*(X[b]-X[o]); }

static int K;
static vector<int> vert[MAXK];
static int h[MAXK];
static vector<ll> pref[MAXK];        // cyclic cross-sums of vert[d] (for fallback)
static int layer_of[MAXN], pos_of[MAXN];
static int loLen[MAXK];              // Andrew lower-chain length in vert[d] (= lo.size())

// pure x-monotone chains (vertical edges collapsed at the extreme x)
static vector<int> loV[MAXK];        // lower chain, x strictly increasing (point ids)
static vector<int> upV[MAXK];        // upper chain, x strictly increasing (point ids)
static vector<ll> loPref[MAXK], upPref[MAXK];
static int loLen2[MAXK], upLen2[MAXK];
static int loIdxOf[MAXN], upIdxOf[MAXN];

static vector<int> delLo[MAXK], delUp[MAXK]; // per-query sorted chain indices of deleted pts
static int delMark[MAXN];
static int delStamp = 0;
static int gOrder[MAXN];             // points sorted by (x,y)
static int n, m;

// envelope order: bottom-to-top = loV[0..np-1], leftover, upV[np-1..0]
static int evD[MAXK*2+2], evK[MAXK*2+2]; // evK: 0=loV, 1=upV
static int evCnt;
static int numProper;
static ll xminAll, xmaxAll;

// ---- implicit envelope chains ----
struct EPiece { int d; int kind; int s; int len; }; // kind 0=loV[d], 1=upV[d]; x-increasing
struct EChain {
    vector<EPiece> pc;
    vector<int> szPref;
    vector<ll> csPref;
    int size() const { return szPref.empty() ? 0 : szPref.back(); }
    ll total() const { return csPref.empty() ? 0 : csPref.back(); }
};
static inline int ePoint(const EPiece& p, int k){
    return (p.kind==0) ? loV[p.d][p.s+k] : upV[p.d][p.s+k];
}
static inline int eFirst(const EPiece& p){ return ePoint(p,0); }
static inline int eLast(const EPiece& p){ return ePoint(p,p.len-1); }
static ll eCS(const EPiece& p){
    if(p.len<=1) return 0;
    if(p.kind==0) return loPref[p.d][p.s+p.len-1] - loPref[p.d][p.s];
    return upPref[p.d][p.s+p.len-1] - upPref[p.d][p.s];
}
static int eChainPoint(const EChain& c, int k){
    int idx=(int)(upper_bound(c.szPref.begin(),c.szPref.end(),k)-c.szPref.begin())-1;
    return ePoint(c.pc[idx], k-c.szPref[idx]);
}
static void eRebuild(EChain& c){
    int np=(int)c.pc.size();
    c.csPref.assign(np+1,0);
    for(int i=0;i<np;i++){
        ll v=0;
        if(i>0) v+=cross2(eLast(c.pc[i-1]), eFirst(c.pc[i]));
        v+=eCS(c.pc[i]);
        c.csPref[i+1]=c.csPref[i]+v;
    }
}
static void eFromPiece(const EPiece& p, EChain& c){
    c.pc.clear(); c.szPref.clear(); c.csPref.clear();
    if(p.len<=0){ eRebuild(c); return; }
    c.pc.push_back(p);
    c.szPref.push_back(0); c.szPref.push_back(p.len);
    eRebuild(c);
}
// lower common tangent (x-increasing lower chains)
static int eLowerTangentJ(int oi, const EChain& B){
    int q=B.size(); int lo=0,hi=q-1;
    while(lo<hi){ int mid=(lo+hi)>>1; if(crsP(oi,eChainPoint(B,mid),eChainPoint(B,mid+1))<0) lo=mid+1; else hi=mid; }
    return lo;
}
static pair<int,int> eLowerBridge(const EChain& A, const EChain& B){
    int p=A.size();
    if(p==1) return {0, eLowerTangentJ(eChainPoint(A,0),B)};
    int lo=0,hi=p-1,ans=0;
    while(lo<=hi){
        int mid=(lo+hi)>>1;
        int j=eLowerTangentJ(eChainPoint(A,mid),B);
        bool ok=(mid==0)||(crs3(eChainPoint(A,mid-1),eChainPoint(A,mid),eChainPoint(B,j))>0);
        if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
    }
    int i=ans, j=eLowerTangentJ(eChainPoint(A,i),B);
    return {i,j};
}
// upper common tangent (sign-flipped)
static int eUpperTangentJ(int oi, const EChain& B){
    int q=B.size(); int lo=0,hi=q-1;
    while(lo<hi){ int mid=(lo+hi)>>1; if(crsP(oi,eChainPoint(B,mid),eChainPoint(B,mid+1))>0) lo=mid+1; else hi=mid; }
    return lo;
}
static pair<int,int> eUpperBridge(const EChain& A, const EChain& B){
    int p=A.size();
    if(p==1) return {0, eUpperTangentJ(eChainPoint(A,0),B)};
    int lo=0,hi=p-1,ans=0;
    while(lo<=hi){
        int mid=(lo+hi)>>1;
        int j=eUpperTangentJ(eChainPoint(A,mid),B);
        bool ok=(mid==0)||(crs3(eChainPoint(A,mid-1),eChainPoint(A,mid),eChainPoint(B,j))<0);
        if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
    }
    int i=ans, j=eUpperTangentJ(eChainPoint(A,i),B);
    return {i,j};
}
static void eMerge(EChain& cur, const EChain& C, int i, int j){
    int idxA=(int)(upper_bound(cur.szPref.begin(),cur.szPref.end(),i)-cur.szPref.begin())-1;
    cur.pc.resize(idxA+1);
    cur.pc[idxA].len = i - cur.szPref[idxA] + 1;
    int idxB=(int)(upper_bound(C.szPref.begin(),C.szPref.end(),j)-C.szPref.begin())-1;
    { EPiece q=C.pc[idxB]; q.s+=(j-C.szPref[idxB]); q.len-=(j-C.szPref[idxB]); if(q.len>0) cur.pc.push_back(q); }
    for(int t=idxB+1;t<(int)C.pc.size();t++) cur.pc.push_back(C.pc[t]);
    cur.szPref.clear(); cur.szPref.push_back(0);
    for(auto& p:cur.pc) cur.szPref.push_back(cur.szPref.back()+p.len);
    eRebuild(cur);
}

// envelope recursion over ordered chains. dir=+1 lower (forward), -1 upper (backward).
static void envRec(int idx, int dir, ll xL, ll xR, vector<EPiece>& out){
    int step = (dir==+1) ? +1 : -1;
    while(idx >= 0 && idx < evCnt){
        int d = evD[idx], kind = evK[idx];
        const vector<int>& V = (kind==0) ? loV[d] : upV[d];
        vector<int>& del = (kind==0) ? delLo[d] : delUp[d];
        int L = (int)V.size();
        int i=L, j=-1;
        {
            int lo=0, hi=L-1;
            while(lo<=hi){ int mid=(lo+hi)>>1; if(X[V[mid]]>=xL){ i=mid; hi=mid-1; } else lo=mid+1; }
            lo=0; hi=L-1;
            while(lo<=hi){ int mid=(lo+hi)>>1; if(X[V[mid]]<=xR){ j=mid; lo=mid+1; } else hi=mid-1; }
        }
        if(i>j){ idx += step; continue; } // empty clip -> skip to next chain
        bool aligned = (h[d] < 3) || (dir==+1 ? kind==0 : kind==1);
        if(!aligned){
            int firstSurv=-1, lastSurv=-1;
            {
                int li=(int)(lower_bound(del.begin(),del.end(),i)-del.begin());
                if(delMark[V[i]]!=delStamp){ firstSurv=i; }
                else if(li<(int)del.size() && del[li]==i){
                    int qk=del[li];
                    while(li+1<(int)del.size() && del[li+1]==qk+1) qk=del[++li];
                    firstSurv=qk+1;
                }
                if(firstSurv>=0 && firstSurv<=j){
                    int ri=(int)(upper_bound(del.begin(),del.end(),j)-del.begin())-1;
                    if(delMark[V[j]]!=delStamp){ lastSurv=j; }
                    else if(ri>=0 && del[ri]==j){
                        int pk=del[ri];
                        while(ri-1>=0 && del[ri-1]==pk-1) pk=del[--ri];
                        lastSurv=pk-1;
                    }
                }
            }
            if(firstSurv<0 || firstSurv>j){ idx += step; continue; }
            if(X[V[firstSurv]] > xL) envRec(idx+step, dir, xL, X[V[firstSurv]]-1, out);
            out.push_back({d,kind,firstSurv,1});
            if(lastSurv!=firstSurv) out.push_back({d,kind,lastSurv,1});
            if(X[V[lastSurv]] < xR) envRec(idx+step, dir, X[V[lastSurv]]+1, xR, out);
            return;
        }
        if(X[V[i]] > xL && delMark[V[i]] != delStamp){
            envRec(idx+step, dir, xL, X[V[i]]-1, out);
        }
        int li=(int)(lower_bound(del.begin(),del.end(),i)-del.begin());
        int cur=i;
        while(li<(int)del.size() && del[li]<=j){
            int pk=del[li], qk=pk;
            while(li+1<(int)del.size() && del[li+1]==qk+1 && del[li+1]<=j) qk=del[++li];
            if(pk-1>=cur) out.push_back({d,kind,cur,pk-cur});
            ll xL2=(pk>i)?X[V[pk-1]]+1:xL;   // open at surviving left neighbor
            ll xR2=(qk<j)?X[V[qk+1]]-1:xR;   // open at surviving right neighbor
            envRec(idx+step, dir, xL2, xR2, out);
            cur=qk+1; li++;
        }
        if(cur<=j) out.push_back({d,kind,cur,j-cur+1});
        if(X[V[j]] < xR && delMark[V[j]] != delStamp){
            envRec(idx+step, dir, X[V[j]]+1, xR, out);
        }
        return;
    }
}

// build the lower (dir=+1) or upper (dir=-1) hull of surviving points; returns its
// cross-sum and its first/last points.
static ll buildEnvelope(int dir, int& firstPt, int& lastPt){
    static vector<EPiece> arcs;
    arcs.clear();
    envRec(dir==+1?0:evCnt-1, dir, xminAll, xmaxAll, arcs);
    static EChain cur, C;
    if(arcs.empty()){ firstPt=lastPt=-1; return 0; }
    eFromPiece(arcs[0], cur);
    for(int t=1;t<(int)arcs.size();t++){
        eFromPiece(arcs[t], C);
        pair<int,int> pr = (dir==+1) ? eLowerBridge(cur,C) : eUpperBridge(cur,C);
        eMerge(cur, C, pr.first, pr.second);
    }
    firstPt = eChainPoint(cur, 0);
    lastPt  = eChainPoint(cur, cur.size()-1);
    return cur.total();
}

// ---- IO ----
#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'; }

static void buildLayers(){
    static int order[MAXN];
    for(int i=0;i<n;i++) order[i]=i;
    sort(order, order+n, [](int a,int b){ return X[a]!=X[b]?X[a]<X[b]:Y[a]<Y[b]; });
    for(int i=0;i<n;i++) gOrder[i]=order[i];
    static int nxt[MAXN], prv[MAXN];
    for(int i=0;i<n;i++){
        nxt[order[i]] = (i+1<n) ? order[i+1] : -1;
        prv[order[i]] = (i>0) ? order[i-1] : -1;
    }
    int head=order[0];
    static vector<int> cur; cur.reserve(n);
    static vector<int> lo, up;
    int rem=n; K=0;
    for(int i=0;i<n;i++){ loIdxOf[i]=upIdxOf[i]=-1; }
    while(rem>=3 && K<PEEL){
        cur.clear();
        for(int i=head; i!=-1; i=nxt[i]) cur.push_back(i);
        int sz=(int)cur.size();
        lo.clear();
        for(int idx:cur){ while(lo.size()>=2 && crs3(lo[lo.size()-2],lo.back(),idx)<=0) lo.pop_back(); lo.push_back(idx); }
        up.clear();
        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]=(int)H.size(); loLen[K]=(int)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; }
        // pure lower chain: lo with trailing vertical edge collapsed
        loV[K].clear();
        for(int t=0;t<(int)lo.size();t++) loV[K].push_back(lo[t]);
        if(loV[K].size()>=2 && X[loV[K].back()]==X[loV[K][loV[K].size()-2]]) loV[K].pop_back();
        // pure upper chain: reverse(up) with leading vertical edge collapsed
        upV[K].clear();
        for(int t=(int)up.size()-1;t>=0;t--) upV[K].push_back(up[t]);
        if(upV[K].size()>=2 && X[upV[K][0]]==X[upV[K][1]]) upV[K].erase(upV[K].begin());
        loLen2[K]=(int)loV[K].size(); upLen2[K]=(int)upV[K].size();
        loPref[K].assign(loLen2[K]+1,0);
        for(int i=1;i<loLen2[K];i++) loPref[K][i]=loPref[K][i-1]+cross2(loV[K][i-1],loV[K][i]);
        if(loLen2[K]>=1) loPref[K][loLen2[K]]=loPref[K][loLen2[K]-1];
        upPref[K].assign(upLen2[K]+1,0);
        for(int i=1;i<upLen2[K];i++) upPref[K][i]=upPref[K][i-1]+cross2(upV[K][i-1],upV[K][i]);
        if(upLen2[K]>=1) upPref[K][upLen2[K]]=upPref[K][upLen2[K]-1];
        for(int t=0;t<(int)loV[K].size();t++) loIdxOf[loV[K][t]]=t;
        for(int t=0;t<(int)upV[K].size();t++) upIdxOf[upV[K][t]]=t;
        for(int t=0;t<h[K];t++){
            int v=H[t];
            if(prv[v]!=-1) nxt[prv[v]]=nxt[v]; else head=nxt[v];
            if(nxt[v]!=-1) prv[nxt[v]]=prv[v];
        }
        K++; rem-=H.size();
    }
    if(rem>0 && rem<3){
        vector<int> rest;
        for(int i=head; i!=-1; i=nxt[i]) rest.push_back(i);
        vert[K]=rest; h[K]=(int)rest.size(); loLen[K]=(int)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; }
        loV[K]=rest; upV[K].clear();
        loLen2[K]=(int)rest.size(); upLen2[K]=0;
        loPref[K].assign(loLen2[K]+1,0);
        for(int i=1;i<loLen2[K];i++) loPref[K][i]=loPref[K][i-1]+cross2(loV[K][i-1],loV[K][i]);
        if(loLen2[K]>=1) loPref[K][loLen2[K]]=loPref[K][loLen2[K]-1];
        for(int t=0;t<(int)rest.size();t++) loIdxOf[rest[t]]=t;
        K++;
    }
    // rem >= 3 here means the peel hit the PEEL cap (or a collinear tail): those points are
    // interior to the outermost PEEL layers and can never be exposed by <=100 deletions, so
    // they are ignored (layer_of stays -1).
    // envelope order
    numProper = (h[K-1] < 3) ? K-1 : K;
    xminAll = X[gOrder[0]]; xmaxAll = X[gOrder[n-1]];
    evCnt=0;
    for(int d=0; d<numProper; d++){ evD[evCnt]=d; evK[evCnt]=0; evCnt++; }
    if(numProper < K){ evD[evCnt]=K-1; evK[evCnt]=0; evCnt++; } // leftover as loV
    for(int d=numProper-1; d>=0; d--){ evD[evCnt]=d; evK[evCnt]=1; evCnt++; }
}

static ll solveQueries(){
    ll S=-1;
    ll ret=0;
    for(int q=0;q<m;q++){
        int k=(int)rd();
        delStamp++;
        for(int dd=0; dd<K; dd++){ delLo[dd].clear(); delUp[dd].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;
            delMark[id]=delStamp;
            int d=layer_of[id];
            if(d>=0){
                if(loIdxOf[id]>=0) delLo[d].push_back(loIdxOf[id]);
                if(upIdxOf[id]>=0) delUp[d].push_back(upIdxOf[id]);
            }
        }
        for(int dd=0; dd<K; dd++){
            if(delLo[dd].size()>1){ sort(delLo[dd].begin(),delLo[dd].end()); delLo[dd].erase(unique(delLo[dd].begin(),delLo[dd].end()),delLo[dd].end()); }
            if(delUp[dd].size()>1){ sort(delUp[dd].begin(),delUp[dd].end()); delUp[dd].erase(unique(delUp[dd].begin(),delUp[dd].end()),delUp[dd].end()); }
        }
        int loFirst, loLast, upFirst, upLast;
        ll loSum = buildEnvelope(+1, loFirst, loLast);
        ll upSum = buildEnvelope(-1, upFirst, upLast);
        ll ans = loSum - upSum;
        if(loFirst>=0 && upFirst>=0){
            ans += cross2(loLast, upLast) + cross2(upFirst, loFirst);
        }
        if(ans<0) ans=-ans;
        S=ans;
        ret=ans;
        wl(ans);
    }
    return ret;
}

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

评测结果