代码

// NOI2017 分身术 - clean upper/lower-hull split with persistent-treap merge.
//
// Each onion layer is stored as two strictly-x-monotone pure chains (lower = loV[d],
// upper = upV[d]); vertical edges at the x-extremes are collapsed so every chain is
// strictly x-increasing.  A query then computes the lower hull and the upper hull of
// the surviving points INDEPENDENTLY (the editorial's x-monotone upper/lower split):
//   lower hull = merge of loV[0], loV[1], ... (bottom-to-top), clipping each chain to
//     the surviving x-intervals and recursing into inner layers only where a chain is
//     deleted (so O(k) chain visits, never O(n), and no wrap/straddle bookkeeping);
//   upper hull = symmetric merge of upV[0], upV[1], ... (top-to-bottom).
// Each surviving piece is extracted from its static chain treap by an O(log n) rank
// split and merged into the running hull by a common-tangent bridge + concat, so the
// merge is O(log n) per piece; the area is read straight from the running root's csum
// (cross-sum) without ever materializing points.  Total O((n + sum k) log n).
#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] (unused here; kept for parity)
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 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;

// ---- persistent FHQ treap over chain points ----
static const int TCAP = 600000;
struct TNode { int pt, lc, rc, sz, L, R; ll csum; unsigned pri; };
static TNode TN[TCAP];
static int tcur = 1;
static int tbase = 1;
static int loRoot[MAXK], upRoot[MAXK];

static inline unsigned tpri(int pt){
    uint64_t x = (uint64_t)pt + 0x9e3779b97f4a7c15ull;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ull;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebull;
    return (unsigned)((x ^ (x >> 31)) & 0x7fffffff);
}
static inline int tnew(int pt){
    TN[tcur].pt = pt; TN[tcur].lc = TN[tcur].rc = 0; TN[tcur].sz = 1;
    TN[tcur].L = TN[tcur].R = pt; TN[tcur].csum = 0; TN[tcur].pri = tpri(pt);
    return tcur++;
}
static inline int tclone(int u){ TN[tcur] = TN[u]; return tcur++; }
static inline void tpull(int u){
    int lc = TN[u].lc, rc = TN[u].rc;
    TN[u].sz = TN[lc].sz + 1 + TN[rc].sz;
    TN[u].L = lc ? TN[lc].L : TN[u].pt;
    TN[u].R = rc ? TN[rc].R : TN[u].pt;
    ll s = TN[lc].csum + TN[rc].csum;
    if(lc) s += cross2(TN[lc].R, TN[u].pt);
    if(rc) s += cross2(TN[u].pt, TN[rc].L);
    TN[u].csum = s;
}
static void tpullRec(int u){ if(!u) return; tpullRec(TN[u].lc); tpullRec(TN[u].rc); tpull(u); }
static int tbuild(const int* arr, int len){
    static int stk[MAXN]; int top = 0;
    for(int i=0;i<len;i++){
        int u = tnew(arr[i]); int last = 0;
        while(top && TN[stk[top-1]].pri < TN[u].pri){ last = stk[--top]; }
        if(top) TN[stk[top-1]].rc = u;
        TN[u].lc = last; stk[top++] = u;
    }
    if(top) tpullRec(stk[0]);
    return top ? stk[0] : 0;
}
static void tsplit(int root, int k, int& a, int& b){
    if(!root){ a = b = 0; return; }
    int lsz = TN[TN[root].lc].sz;
    if(lsz >= k){
        b = tclone(root);
        tsplit(TN[b].lc, k, a, TN[b].lc);
        tpull(b);
    } else {
        a = tclone(root);
        tsplit(TN[a].rc, k - lsz - 1, TN[a].rc, b);
        tpull(a);
    }
}
static int tconcat(int a, int b){
    if(!a) return b; if(!b) return a;
    if(TN[a].pri > TN[b].pri){
        int c = tclone(a);
        TN[c].rc = tconcat(TN[c].rc, b);
        tpull(c); return c;
    } else {
        int c = tclone(b);
        TN[c].lc = tconcat(a, TN[c].lc);
        tpull(c); return c;
    }
}
static int tkth(int root, int k){
    while(true){
        int lsz = TN[TN[root].lc].sz;
        if(k < lsz) root = TN[root].lc;
        else if(k == lsz) return TN[root].pt;
        else { k -= lsz + 1; root = TN[root].rc; }
    }
}
// forward tangent: from point P (a point of A) to chain B, returns the leftmost index k
// with the monotone predicate Q(k) true. lower: crsP(P,B[k],B[k+1])>=0 ; upper: <=0.
static int tfwd(int P, int root, bool upper){
    int ans = TN[root].sz - 1, u = root, base = 0, succAnc = -1;
    while(u){
        int rc = TN[u].rc;
        int k = base + TN[TN[u].lc].sz;
        int succ = rc ? TN[rc].L : succAnc;
        bool q;
        if(succ == -1){ q = true; }
        else { ll c = crsP(P, TN[u].pt, succ); q = upper ? (c <= 0) : (c >= 0); }
        if(q){ ans = k; int op = TN[u].pt; u = TN[u].lc; succAnc = op; }
        else { base = k + 1; u = rc; }
    }
    return ans;
}
// reverse tangent: from point P (of B) back to chain A (rootA). lower: crs3(A[k],A[k+1],P)<0 ; upper: >0.
static int trev(int root, int P, bool upper){
    int ans = TN[root].sz - 1, u = root, base = 0, succAnc = -1;
    while(u){
        int rc = TN[u].rc;
        int k = base + TN[TN[u].lc].sz;
        int succ = rc ? TN[rc].L : succAnc;
        bool q;
        if(succ == -1){ q = true; }
        else { ll c = crs3(TN[u].pt, succ, P); q = upper ? (c > 0) : (c < 0); }
        if(q){ ans = k; int op = TN[u].pt; u = TN[u].lc; succAnc = op; }
        else { base = k + 1; u = rc; }
    }
    return ans;
}
static int tmergeLower(int rootA, int rootB){
    int i, j;
    int sa = TN[rootA].sz, sb = TN[rootB].sz;
    if(sa == 1){ i = 0; j = tfwd(tkth(rootA,0), rootB, false); }
    else if(sb == 1){ j = 0; i = trev(rootA, tkth(rootB,0), false); }
    else {
        int ci = 0, cj = 0; bool done = false;
        for(int it=0; it<64; it++){
            int jn = tfwd(tkth(rootA,ci), rootB, false);
            int in = trev(rootA, tkth(rootB,jn), false);
            if(in == ci && jn == cj){ i = in; j = jn; done = true; break; }
            ci = in; cj = jn;
        }
        if(!done){
            int lo = 0, hi = sa-1, ans = 0;
            while(lo <= hi){
                int mid = (lo+hi)>>1;
                int jj = tfwd(tkth(rootA,mid), rootB, false);
                bool ok = (mid==0) || (crs3(tkth(rootA,mid-1), tkth(rootA,mid), tkth(rootB,jj)) > 0);
                if(ok){ ans = mid; lo = mid+1; } else hi = mid-1;
            }
            i = ans; j = tfwd(tkth(rootA,i), rootB, false);
        }
    }
    int aL, aR; tsplit(rootA, i+1, aL, aR);
    int bL, bR; tsplit(rootB, j, bL, bR);
    return tconcat(aL, bR);
}
static int tmergeUpper(int rootA, int rootB){
    int i, j;
    int sa = TN[rootA].sz, sb = TN[rootB].sz;
    if(sa == 1){ i = 0; j = tfwd(tkth(rootA,0), rootB, true); }
    else if(sb == 1){ j = 0; i = trev(rootA, tkth(rootB,0), true); }
    else {
        int ci = 0, cj = 0; bool done = false;
        for(int it=0; it<64; it++){
            int jn = tfwd(tkth(rootA,ci), rootB, true);
            int in = trev(rootA, tkth(rootB,jn), true);
            if(in == ci && jn == cj){ i = in; j = jn; done = true; break; }
            ci = in; cj = jn;
        }
        if(!done){
            int lo = 0, hi = sa-1, ans = 0;
            while(lo <= hi){
                int mid = (lo+hi)>>1;
                int jj = tfwd(tkth(rootA,mid), rootB, true);
                bool ok = (mid==0) || (crs3(tkth(rootA,mid-1), tkth(rootA,mid), tkth(rootB,jj)) < 0);
                if(ok){ ans = mid; lo = mid+1; } else hi = mid-1;
            }
            i = ans; j = tfwd(tkth(rootA,i), rootB, true);
        }
    }
    int aL, aR; tsplit(rootA, i+1, aL, aR);
    int bL, bR; tsplit(rootB, j, bL, bR);
    return tconcat(aL, bR);
}

// ---- implicit envelope pieces ----
struct EPiece { int d; int kind; int s; int len; }; // kind 0=loV[d], 1=upV[d]; x-increasing
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];
}
// extract [s, s+len) of a static chain treap as a fresh (path-copied) root
static int extractPiece(const EPiece& p){
    int root = (p.kind==0) ? loRoot[p.d] : upRoot[p.d];
    int a, b, c;
    tsplit(root, p.s, a, b);
    tsplit(b, p.len, c, b);
    return c;
}

// 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);
    if(arcs.empty()){ firstPt=lastPt=-1; return 0; }
    int root = extractPiece(arcs[0]);
    for(int t=1;t<(int)arcs.size();t++){
        int proot = extractPiece(arcs[t]);
        root = (dir==+1) ? tmergeLower(root, proot) : tmergeUpper(root, proot);
    }
    firstPt = TN[root].L;
    lastPt  = TN[root].R;
    return TN[root].csum;
}

// ---- 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();
        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;
        for(int t=0;t<(int)rest.size();t++) loIdxOf[rest[t]]=t;
        K++;
    }
    // rem >= 3 here means the peel hit the PEEL cap: those points are interior to the
    // outermost PEEL layers and can never be exposed by <=100 deletions, so ignored.
    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++; }
    // build static chain treaps
    for(int d=0; d<K; d++){
        loRoot[d] = (loLen2[d]>0) ? tbuild(loV[d].data(), loLen2[d]) : 0;
        upRoot[d] = (upLen2[d]>0) ? tbuild(upV[d].data(), upLen2[d]) : 0;
    }
    tbase = tcur;
}

static ll solveQueries(){
    ll S=-1;
    ll ret=0;
    for(int q=0;q<m;q++){
        tcur = tbase;
        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;
}

评测结果