代码

// NOI2017 分身术 — onion layers + PIECE-BASED running hull (no per-query tree allocation).
// Each layer's lower/upper x-monotone chain is a plain ARRAY with prefix cross-sums. A query
// builds the surviving lower/upper hull by emitting PIECES (layer, chain, [l,r] ranges) in
// x-order and bridging each into the accumulated hull via an O(log) two-level tangent
// (binary search over pieces + within piece) + O(1) splice. No materialization, no path-copy.
#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 const int MAXSP = 1024;
static const ll XMIN = -(1LL<<60), XMAX = (1LL<<60);

static struct Pt { ll x, y; } P[MAXN];
static int n, m;

static int K;
static vector<int> loV[MAXK], upV[MAXK];
static vector<ll> pref[MAXK], upPref[MAXK];
static int loLen2[MAXK], upLen2[MAXK];
static int h[MAXK];
static int layer_of[MAXN];
static int gOrder[MAXN];
static int loIdxOf[MAXN], upIdxOf[MAXN];
static vector<int> delLo[MAXK], delUp[MAXK];
static int delMark[MAXN];
static int delStamp = 0;

static inline ll cross2(int a,int b){ return P[a].x*P[b].y-P[a].y*P[b].x; }
static inline ll crs3(int a,int b,int c){ return (P[b].x-P[a].x)*(P[c].y-P[b].y)-(P[b].y-P[a].y)*(P[c].x-P[b].x); }
static inline ll crsP(int o,int a,int b){ return (P[a].x-P[o].x)*(P[b].y-P[o].y)-(P[a].y-P[o].y)*(P[b].x-P[o].x); }

// ---- piece-based running hull ----
struct SPiece { int kind, d, s, len; };  // kind 0=loV, 1=upV; chain loV[d][s..s+len-1]
static SPiece spcArr[MAXSP];
static int spcSz[MAXSP+1];
static ll spcCs[MAXSP+1];
static int spcN;

static inline int spPoint(const SPiece& p, int k){ return (p.kind==0) ? loV[p.d][p.s+k] : upV[p.d][p.s+k]; }
static inline int spFirst(const SPiece& p){ return spPoint(p,0); }
static inline int spLast(const SPiece& p){ return spPoint(p,p.len-1); }
static inline ll spCS(const SPiece& p){
    if(p.len<=1) return 0;
    return (p.kind==0) ? (pref[p.d][p.s+p.len-1] - pref[p.d][p.s]) : (upPref[p.d][p.s+p.len-1] - upPref[p.d][p.s]);
}
static inline int hPoint(int k){
    int lo=0, hi=spcN;
    while(lo<hi){ int mid=(lo+hi)>>1; if(spcSz[mid] <= k) lo=mid+1; else hi=mid; }
    return spPoint(spcArr[lo-1], k - spcSz[lo-1]);
}
static int spLowerTangentJ(int oi, const SPiece& p){  // first j with crsP(oi,C[j],C[j+1]) >= 0
    int lo=0, hi=p.len-1;
    while(lo<hi){ int mid=(lo+hi)>>1; if(crsP(oi, spPoint(p,mid), spPoint(p,mid+1)) < 0) lo=mid+1; else hi=mid; }
    return lo;
}
static int spUpperTangentJ(int oi, const SPiece& p){  // first j with crsP(oi,C[j],C[j+1]) <= 0
    int lo=0, hi=p.len-1;
    while(lo<hi){ int mid=(lo+hi)>>1; if(crsP(oi, spPoint(p,mid), spPoint(p,mid+1)) > 0) lo=mid+1; else hi=mid; }
    return lo;
}
// reversed tangent from point P (right of running hull) to running hull; returns GLOBAL index
static int spRevTangentLower(int P){
    int m = spcN, sz = spcSz[spcN];
    if(sz == 1) return 0;
    int t = -1;
    if(m >= 2){
        int lo=0, hi=m-2;
        while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spLast(spcArr[mid]), spFirst(spcArr[mid+1]), P) < 0){ t=mid; hi=mid-1; } else lo=mid+1; }
    }
    if(t >= 0){
        const SPiece& q = spcArr[t]; int L = q.len; int r = -1;
        if(L >= 2){ int lo=0, hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spPoint(q,mid), spPoint(q,mid+1), P) < 0){ r=mid; hi=mid-1; } else lo=mid+1; } }
        if(r >= 0) return spcSz[t] + r;
        return spcSz[t] + L - 1;
    } else {
        const SPiece& q = spcArr[m-1]; int L = q.len; int r = -1;
        if(L >= 2){ int lo=0, hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spPoint(q,mid), spPoint(q,mid+1), P) < 0){ r=mid; hi=mid-1; } else lo=mid+1; } }
        if(r >= 0) return spcSz[m-1] + r;
        return sz - 1;
    }
}
static int spRevTangentUpper(int P){
    int m = spcN, sz = spcSz[spcN];
    if(sz == 1) return 0;
    int t = -1;
    if(m >= 2){
        int lo=0, hi=m-2;
        while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spLast(spcArr[mid]), spFirst(spcArr[mid+1]), P) > 0){ t=mid; hi=mid-1; } else lo=mid+1; }
    }
    if(t >= 0){
        const SPiece& q = spcArr[t]; int L = q.len; int r = -1;
        if(L >= 2){ int lo=0, hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spPoint(q,mid), spPoint(q,mid+1), P) > 0){ r=mid; hi=mid-1; } else lo=mid+1; } }
        if(r >= 0) return spcSz[t] + r;
        return spcSz[t] + L - 1;
    } else {
        const SPiece& q = spcArr[m-1]; int L = q.len; int r = -1;
        if(L >= 2){ int lo=0, hi=L-2; while(lo<=hi){ int mid=(lo+hi)>>1; if(crs3(spPoint(q,mid), spPoint(q,mid+1), P) > 0){ r=mid; hi=mid-1; } else lo=mid+1; } }
        if(r >= 0) return spcSz[m-1] + r;
        return sz - 1;
    }
}
static void spLowerBridge(const SPiece& p, int& i, int& j){
    int sz = spcSz[spcN];
    if(sz == 1){ i = 0; j = spLowerTangentJ(hPoint(0), p); return; }
    if(p.len == 1){ i = spRevTangentLower(spPoint(p,0)); j = 0; return; }
    int ci = sz-1, cj = 0;   // rightmost-start fixpoint
    for(int it=0; it<64; it++){
        int jn = spLowerTangentJ(hPoint(ci), p);
        int in = spRevTangentLower(spPoint(p, jn));
        if(in == ci && jn == cj){ i = in; j = jn; return; }
        ci = in; cj = jn;
    }
    int lo=0, hi=sz-1, ans=0;
    while(lo<=hi){
        int mid=(lo+hi)>>1;
        int jj = spLowerTangentJ(hPoint(mid), p);
        bool ok = (mid==0) || (crs3(hPoint(mid-1), hPoint(mid), spPoint(p,jj)) > 0);
        if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
    }
    i = ans; j = spLowerTangentJ(hPoint(i), p);
}
static void spUpperBridge(const SPiece& p, int& i, int& j){
    int sz = spcSz[spcN];
    if(sz == 1){ i = 0; j = spUpperTangentJ(hPoint(0), p); return; }
    if(p.len == 1){ i = spRevTangentUpper(spPoint(p,0)); j = 0; return; }
    int ci = sz-1, cj = 0;
    for(int it=0; it<64; it++){
        int jn = spUpperTangentJ(hPoint(ci), p);
        int in = spRevTangentUpper(spPoint(p, jn));
        if(in == ci && jn == cj){ i = in; j = jn; return; }
        ci = in; cj = jn;
    }
    int lo=0, hi=sz-1, ans=0;
    while(lo<=hi){
        int mid=(lo+hi)>>1;
        int jj = spUpperTangentJ(hPoint(mid), p);
        bool ok = (mid==0) || (crs3(hPoint(mid-1), hPoint(mid), spPoint(p,jj)) < 0);
        if(ok){ ans=mid; lo=mid+1; } else hi=mid-1;
    }
    i = ans; j = spUpperTangentJ(hPoint(i), p);
}
// truncate running hull at global index i, then append piece p's suffix p[j..end]
static void spAppend(const SPiece& p, int i, int j){
    int idxA = 0;
    { int lo=0, hi=spcN; while(lo<hi){ int mid=(lo+hi)>>1; if(spcSz[mid] <= i) lo=mid+1; else hi=mid; } idxA = lo-1; }
    spcArr[idxA].len = i - spcSz[idxA] + 1;
    spcN = idxA + 1;
    spcSz[idxA+1] = i + 1;
    spcCs[idxA+1] = spcCs[idxA] + (idxA>0 ? cross2(spLast(spcArr[idxA-1]), spFirst(spcArr[idxA])) : 0) + spCS(spcArr[idxA]);
    SPiece q = p; q.s += j; q.len -= j;
    if(q.len > 0){
        spcArr[spcN] = q;
        spcSz[spcN+1] = spcSz[spcN] + q.len;
        spcCs[spcN+1] = spcCs[spcN] + cross2(spLast(spcArr[spcN-1]), spFirst(q)) + spCS(q);
        spcN++;
    }
}
static inline void mergeIntoHull(const SPiece& p, int kind){
    if(spcN == 0){
        spcArr[0] = p;
        spcSz[0] = 0; spcSz[1] = p.len;
        spcCs[0] = 0; spcCs[1] = spCS(p);
        spcN = 1;
        return;
    }
    int i, j;
    if(kind==0) spLowerBridge(p, i, j); else spUpperBridge(p, i, j);
    spAppend(p, i, j);
}

static ll rd();
static void wl(ll v);

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 P[a].x!=P[b].x?P[a].x<P[b].x:P[a].y<P[b].y; });
    for(int i=0;i<n;i++) gOrder[i]=order[i];
    static char alive[MAXN];
    static int pos[MAXN];
    for(int i=0;i<n;i++){ alive[i]=1; pos[order[i]]=i; }
    static vector<int> lo, up;
    int rem = n; K = 0;
    for(int i=0;i<n;i++){ loIdxOf[i]=upIdxOf[i]=-1; layer_of[i]=-1; }
    while(rem >= 3 && K < PEEL){
        lo.clear();
        for(int t=0;t<n;t++){ if(!alive[t]) continue; int idx=order[t];
            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=n-1;t>=0;t--){ if(!alive[t]) continue; int idx=order[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;
        h[K] = (int)H.size();
        loV[K].clear();
        for(int t=0;t<(int)lo.size();t++) loV[K].push_back(lo[t]);
        if(loV[K].size()>=2 && P[loV[K].back()].x==P[loV[K][loV[K].size()-2]].x) loV[K].pop_back();
        upV[K].clear();
        for(int t=(int)up.size()-1;t>=0;t--) upV[K].push_back(up[t]);
        if(upV[K].size()>=2 && P[upV[K][0]].x==P[upV[K][1]].x) upV[K].erase(upV[K].begin());
        loLen2[K] = (int)loV[K].size(); upLen2[K] = (int)upV[K].size();
        for(int t=0;t<(int)loV[K].size();t++){ loIdxOf[loV[K][t]]=t; layer_of[loV[K][t]]=K; }
        for(int t=0;t<(int)upV[K].size();t++){ upIdxOf[upV[K][t]]=t; layer_of[upV[K][t]]=K; }
        for(int t=0;t<(int)H.size();t++) alive[pos[H[t]]]=0;
        K++; rem -= H.size();
    }
    if(rem > 0){
        vector<int> rest;
        for(int t=0;t<n;t++){ if(alive[t]) rest.push_back(order[t]); }
        h[K] = (int)rest.size();
        loV[K] = rest; upV[K].clear();
        loLen2[K] = (int)rest.size(); upLen2[K] = 0;
        for(int t=0;t<(int)rest.size();t++){ loIdxOf[rest[t]]=t; layer_of[rest[t]]=K; }
        K++;
    }
    // prefix cross-sums
    for(int d=0; d<K; d++){
        pref[d].resize(loLen2[d]);
        for(int t=1;t<loLen2[d];t++) pref[d][t] = pref[d][t-1] + cross2(loV[d][t-1], loV[d][t]);
        upPref[d].resize(upLen2[d]);
        for(int t=1;t<upLen2[d];t++) upPref[d][t] = upPref[d][t-1] + cross2(upV[d][t-1], upV[d][t]);
    }
}

// append the (kind,d) chain pieces in [idxL,idxR] (x-range [xL,xR]) to the running hull,
// recursing into deeper layers for deleted gaps. dir: +1 lower, -1 upper.
static void buildAligned(int d, int kind, int dir, ll xL, ll xR){
    if(d >= K) return;
    if(h[d] < 3){
        if(kind == 1) return;
        for(int t=0;t<loLen2[d];t++){
            int p = loV[d][t];
            if(delMark[p]==delStamp) continue;
            if(P[p].x < xL || P[p].x > xR) continue;
            SPiece q = {0, d, t, 1};
            mergeIntoHull(q, dir==+1 ? 0 : 1);
        }
        return;
    }
    const vector<int>& V = (kind==0) ? loV[d] : upV[d];
    const vector<int>& del = (kind==0) ? delLo[d] : delUp[d];
    int len = (int)V.size();
    int idxL = len, idxR = -1;
    { int lo=0, hi=len-1; while(lo<=hi){ int mid=(lo+hi)>>1; if(P[V[mid]].x>=xL){ idxL=mid; hi=mid-1; } else lo=mid+1; } }
    { int lo=0, hi=len-1; while(lo<=hi){ int mid=(lo+hi)>>1; if(P[V[mid]].x<=xR){ idxR=mid; lo=mid+1; } else hi=mid-1; } }
    if(idxL > idxR) return;
    int dl = (int)del.size();
    int di = 0;
    while(di < dl && del[di] < idxL) di++;
    if(di >= dl || del[di] > idxR){
        SPiece q = {kind, d, idxL, idxR-idxL+1};
        mergeIntoHull(q, kind);
        return;
    }
    int lastIncluded = idxL - 1;
    int i = di;
    while(i < dl){
        int a = del[i], b = a;
        while(i+1 < dl && del[i+1] == b+1){ b = del[++i]; }
        if(b < idxL){ i++; continue; }
        if(a > idxR) break;
        if(a-1 >= lastIncluded+1){
            SPiece q = {kind, d, lastIncluded+1, a-1-(lastIncluded+1)+1};
            mergeIntoHull(q, kind);
        }
        ll xL_gap = (a > idxL) ? P[V[a-1]].x+1 : xL;
        ll xR_gap = (b < idxR) ? P[V[b+1]].x-1 : xR;
        if(xL_gap <= xR_gap){
            buildAligned(d+1, kind, dir, xL_gap, xR_gap);
        }
        lastIncluded = b;
        i++;
    }
    if(lastIncluded+1 <= idxR){
        SPiece q = {kind, d, lastIncluded+1, idxR-(lastIncluded+1)+1};
        mergeIntoHull(q, kind);
    }
}

// add global x-extremes if they are not already the hull's endpoints (edge cases)
static void addExtremes(int dir){
    int gl=-1, gr=-1;
    for(int i=0;i<n;i++) if(delMark[gOrder[i]]!=delStamp){ gl=gOrder[i]; break; }
    for(int i=n-1;i>=0;i--) if(delMark[gOrder[i]]!=delStamp){ gr=gOrder[i]; break; }
    if(gl < 0) return;
    int bkind = (dir==+1) ? 0 : 1;   // bridge kind: 0 lower, 1 upper
    bool needGl = (spcN==0) || (P[gl].x < P[spFirst(spcArr[0])].x);
    bool needGr = (gr!=gl) && ((spcN==0) || (P[gr].x > P[spLast(spcArr[spcN-1])].x));
    if(!needGl && !needGr) return;
    static SPiece save[MAXSP]; int saveN = spcN;
    for(int t=0;t<spcN;t++) save[t] = spcArr[t];
    spcN = 0;
    // emit a single surviving point as a 1-length piece, using the chain it actually sits on
    struct Emit { static void go(int p, int bkind){
        int d = layer_of[p];
        int s = loIdxOf[p], pk = 0;
        if(s < 0){ s = upIdxOf[p]; pk = 1; }
        if(s >= 0){ SPiece q = {pk, d, s, 1}; mergeIntoHull(q, bkind); }
    }};
    if(needGl) Emit::go(gl, bkind);
    for(int t=0;t<saveN;t++) mergeIntoHull(save[t], bkind);
    if(needGr) Emit::go(gr, bkind);
}

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()); }
        }
        // lower hull
        spcN = 0;
        buildAligned(0, 0, +1, XMIN, XMAX);
        addExtremes(+1);
        ll loSum = spcCs[spcN];
        int loFirst = (spcN>0) ? spFirst(spcArr[0]) : -1;
        int loLast  = (spcN>0) ? spLast(spcArr[spcN-1]) : -1;
        // upper hull
        spcN = 0;
        buildAligned(0, 1, -1, XMIN, XMAX);
        addExtremes(-1);
        ll upSum = spcCs[spcN];
        int upFirst = (spcN>0) ? spFirst(spcArr[0]) : -1;
        int upLast  = (spcN>0) ? spLast(spcArr[spcN-1]) : -1;
        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;
}

// ---- 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<<25], local_out[1<<25];
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++){ P[i].x=rd(); P[i].y=rd(); }
    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;
}

评测结果