代码

// NOI2017 分身术 — persistent treap of x-monotone chains (upper/lower hulls).
// Build onion layers; store each layer's lower/upper x-monotone chain in a treap keyed by x
// with the cross-sum (2*area) pushup. Per query: recursively build the lower and upper hulls of
// the SURVIVING points by splitting the chains at deleted runs (x-intervals) and splicing the
// deeper layers' arcs with the common-tangent bridge — O((n + Σk) log n), no O(n) materialize.
#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 ll XMIN = -(1LL<<60), XMAX = (1LL<<60);

static ll X[MAXN], Y[MAXN];
static int n, m;

static int K;
static vector<int> loV[MAXK], upV[MAXK];   // x-sorted, strictly-increasing-x chains
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 X[a]*Y[b]-Y[a]*X[b]; }
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 crsP(int o,int a,int b){ return (X[a]-X[o])*(Y[b]-Y[o])-(Y[a]-Y[o])*(X[b]-X[o]); }

// ---- persistent treap (copy-on-write) ----
static const int NODE_MAX = 4000000;
static struct TN { int p; int ch[2]; unsigned prio; int sz; int first,last; ll cs; } tn[NODE_MAX];
static int tcnt = 1;
static int tcntBase = 0;
static unsigned rnd[MAXN];

static inline int newLeaf(int p){
    if(tcnt >= NODE_MAX){ fprintf(stderr,"NODE OVERFLOW %d\n", tcnt); exit(1); }
    int u = tcnt++;
    tn[u].p = p; tn[u].ch[0] = tn[u].ch[1] = 0;
    tn[u].prio = rnd[p]; tn[u].sz = 1; tn[u].first = tn[u].last = p; tn[u].cs = 0;
    return u;
}
static inline int cloneNode(int u){
    if(tcnt >= NODE_MAX){ fprintf(stderr,"NODE OVERFLOW %d\n", tcnt); exit(1); }
    int v = tcnt++;
    tn[v] = tn[u];
    return v;
}
static inline void pull(int u){
    int l = tn[u].ch[0], r = tn[u].ch[1];
    tn[u].sz = 1 + (l?tn[l].sz:0) + (r?tn[r].sz:0);
    tn[u].first = l ? tn[l].first : tn[u].p;
    tn[u].last  = r ? tn[r].last  : tn[u].p;
    ll s = 0;
    if(l) s += tn[l].cs + cross2(tn[l].last, tn[u].p);
    if(r) s += cross2(tn[u].p, tn[r].first) + tn[r].cs;
    tn[u].cs = s;
}
// merge two treaps, all keys (x) of a < all keys of b
static int mergeT(int a, int b){
    if(!a) return b; if(!b) return a;
    if(tn[a].prio > tn[b].prio){
        a = cloneNode(a);
        tn[a].ch[1] = mergeT(tn[a].ch[1], b);
        pull(a); return a;
    } else {
        b = cloneNode(b);
        tn[b].ch[0] = mergeT(a, tn[b].ch[0]);
        pull(b); return b;
    }
}
static void splitPos(int u, int k, int& a, int& b){  // a = first k elements
    if(!u){ a = b = 0; return; }
    int v = cloneNode(u);
    int lsz = tn[v].ch[0] ? tn[tn[v].ch[0]].sz : 0;
    if(k <= lsz){
        splitPos(tn[v].ch[0], k, a, tn[v].ch[0]);
        b = v; pull(b);
    } else {
        splitPos(tn[v].ch[1], k - lsz - 1, tn[v].ch[1], b);
        a = v; pull(a);
    }
}
static void splitX(int u, ll xv, int& a, int& b){  // a = x < xv
    if(!u){ a = b = 0; return; }
    int v = cloneNode(u);
    if(X[tn[v].p] < xv){
        splitX(tn[v].ch[1], xv, tn[v].ch[1], b);
        a = v; pull(a);
    } else {
        splitX(tn[v].ch[0], xv, a, tn[v].ch[0]);
        b = v; pull(b);
    }
}
static int kth(int u, int k){
    int lsz = tn[u].ch[0] ? tn[tn[u].ch[0]].sz : 0;
    if(k < lsz) return kth(tn[u].ch[0], k);
    if(k == lsz) return tn[u].p;
    return kth(tn[u].ch[1], k - lsz - 1);
}
static int clip(int root, ll xL, ll xR){  // points with xL <= x <= xR (inclusive)
    int a, bc, b, c;
    splitX(root, xL, a, bc);
    splitX(bc, xR+1, b, c);
    return b;
}
static int clipByIndex(int root, int l, int r){  // in-order positions [l..r] (0-based)
    if(l > r) return 0;
    int a, rest, before, mid;
    splitPos(root, r+1, a, rest);
    splitPos(a, l, before, mid);
    return mid;
}

// lower common tangent: i on A, j on B (all A.x < all B.x)
// O(log sz) point-to-chain tangent via direct tree descent (no kth). Returns the POSITION j.
static int lowerTangentJ(int oi, int rootB){
    int u = rootB, base = 0, ans = 0, nxt = -1;
    while(u){
        int ls = tn[u].ch[0] ? tn[tn[u].ch[0]].sz : 0;
        int p = tn[u].p;
        int succ = tn[u].ch[1] ? tn[tn[u].ch[1]].first : nxt;
        bool edgeGood = (succ < 0) || (crsP(oi, p, succ) >= 0);
        if(edgeGood){ ans = base + ls; u = tn[u].ch[0]; nxt = p; }
        else { base += ls + 1; u = tn[u].ch[1]; }
    }
    return ans;
}
// reversed tangent: from point P (right of chain A) to A, returning POSITION i.
static int revTangentLower(int rootA, int P){
    int u = rootA, base = 0, ans = 0, nxt = -1;
    while(u){
        int ls = tn[u].ch[0] ? tn[tn[u].ch[0]].sz : 0;
        int p = tn[u].p;
        int succ = tn[u].ch[1] ? tn[tn[u].ch[1]].first : nxt;
        if(succ < 0 || crs3(p, succ, P) < 0){ ans = base + ls; u = tn[u].ch[0]; nxt = p; }
        else { base += ls + 1; u = tn[u].ch[1]; }
    }
    return ans;
}
static int revTangentUpper(int rootA, int P){
    int u = rootA, base = 0, ans = 0, nxt = -1;
    while(u){
        int ls = tn[u].ch[0] ? tn[tn[u].ch[0]].sz : 0;
        int p = tn[u].p;
        int succ = tn[u].ch[1] ? tn[tn[u].ch[1]].first : nxt;
        if(succ < 0 || crs3(p, succ, P) > 0){ ans = base + ls; u = tn[u].ch[0]; nxt = p; }
        else { base += ls + 1; u = tn[u].ch[1]; }
    }
    return ans;
}
static void lowerBridge(int rootA, int rootB, int& i, int& j){
    int p = tn[rootA].sz;
    if(p == 1){ i = 0; j = lowerTangentJ(kth(rootA,0), rootB); return; }
    if(tn[rootB].sz == 1){ j = 0; i = revTangentLower(rootA, kth(rootB,0)); return; }
    int ci = 0, cj = 0;
    for(int it=0; it<64; it++){
        int jn = lowerTangentJ(kth(rootA, ci), rootB);
        int in = revTangentLower(rootA, kth(rootB, jn));
        if(in == ci && jn == cj){ i = in; j = jn; return; }
        ci = in; cj = jn;
    }
    int lo = 0, hi = p-1, ans = 0;
    while(lo <= hi){
        int mid = (lo+hi)>>1;
        int jj = lowerTangentJ(kth(rootA,mid), rootB);
        bool ok = (mid==0) || (crs3(kth(rootA,mid-1), kth(rootA,mid), kth(rootB,jj)) > 0);
        if(ok){ ans = mid; lo = mid+1; } else hi = mid-1;
    }
    i = ans; j = lowerTangentJ(kth(rootA,i), rootB);
}
static int upperTangentJ(int oi, int rootB){
    int u = rootB, base = 0, ans = 0, nxt = -1;
    while(u){
        int ls = tn[u].ch[0] ? tn[tn[u].ch[0]].sz : 0;
        int p = tn[u].p;
        int succ = tn[u].ch[1] ? tn[tn[u].ch[1]].first : nxt;
        bool edgeGood = (succ < 0) || (crsP(oi, p, succ) <= 0);
        if(edgeGood){ ans = base + ls; u = tn[u].ch[0]; nxt = p; }
        else { base += ls + 1; u = tn[u].ch[1]; }
    }
    return ans;
}
static void upperBridge(int rootA, int rootB, int& i, int& j){
    int p = tn[rootA].sz;
    if(p == 1){ i = 0; j = upperTangentJ(kth(rootA,0), rootB); return; }
    if(tn[rootB].sz == 1){ j = 0; i = revTangentUpper(rootA, kth(rootB,0)); return; }
    int ci = 0, cj = 0;
    for(int it=0; it<64; it++){
        int jn = upperTangentJ(kth(rootA, ci), rootB);
        int in = revTangentUpper(rootA, kth(rootB, jn));
        if(in == ci && jn == cj){ i = in; j = jn; return; }
        ci = in; cj = jn;
    }
    int lo = 0, hi = p-1, ans = 0;
    while(lo <= hi){
        int mid = (lo+hi)>>1;
        int jj = upperTangentJ(kth(rootA,mid), rootB);
        bool ok = (mid==0) || (crs3(kth(rootA,mid-1), kth(rootA,mid), kth(rootB,jj)) < 0);
        if(ok){ ans = mid; lo = mid+1; } else hi = mid-1;
    }
    i = ans; j = upperTangentJ(kth(rootA,i), rootB);
}
// lower hull of A ∪ B (A.x < B.x): trim at common tangent and concatenate
static int mergeChain(int rootA, int rootB){
    if(!rootA) return rootB;
    if(!rootB) return rootA;
    int i, j;
    lowerBridge(rootA, rootB, i, j);
    int Aleft, Aright, Bleft, Bright;
    splitPos(rootA, i+1, Aleft, Aright);
    splitPos(rootB, j, Bleft, Bright);
    int r = mergeT(Aleft, Bright);
    return r;
}
static int mergeChainUpper(int rootA, int rootB){
    if(!rootA) return rootB;
    if(!rootB) return rootA;
    int i, j;
    upperBridge(rootA, rootB, i, j);
    int Aleft, Aright, Bleft, Bright;
    splitPos(rootA, i+1, Aleft, Aright);
    splitPos(rootB, j, Bleft, Bright);
    return mergeT(Aleft, Bright);
}

static int loRoot[MAXK], upRoot[MAXK];
static int evD[MAXK*2+2], evK[MAXK*2+2]; static int evCnt; static int numProper;
static int envFirst[MAXK*2], envLast[MAXK*2];  // first/last surviving index helpers

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 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, lo, up;
    cur.reserve(n);
    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){
        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;
        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 && X[loV[K].back()]==X[loV[K][loV[K].size()-2]]) 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 && 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; 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++){
            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){
        vector<int> rest;
        for(int i=head; i!=-1; i=nxt[i]) rest.push_back(i);
        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++;
    }
    // build treaps (loV is x-sorted; upV is x-sorted)
    for(int d=0; d<K; d++){
        loRoot[d] = 0;
        for(int t=0;t<loLen2[d];t++) loRoot[d] = mergeT(loRoot[d], newLeaf(loV[d][t]));
        upRoot[d] = 0;
        for(int t=0;t<upLen2[d];t++) upRoot[d] = mergeT(upRoot[d], newLeaf(upV[d][t]));
    }
    tcntBase = tcnt;
    numProper = (h[K-1] < 3) ? K-1 : K;
    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++; }
    for(int d=numProper-1; d>=0; d--){ evD[evCnt]=d; evK[evCnt]=1; evCnt++; }
}

static inline int mergeEnv(int a, int b, int dir){
    return dir==+1 ? mergeChain(a,b) : mergeChainUpper(a,b);
}

// aligned chain traversal with early-stopping: process layer d's chain (kind), recursing into
// d+1 only for deleted gaps. Nested hulls mean the outer x-ranges are always empty, so no outer
// recursion is needed. Early stop at the first layer with no deletion in [xL,xR].
static int buildAligned(int d, int kind, int dir, ll xL, ll xR){
    if(d >= K) return 0;
    if(h[d] < 3){
        if(kind == 1) return 0;  // leftover has no upper chain
        int res = 0;
        for(int t=0;t<loLen2[d];t++){
            int p = loV[d][t];
            if(delMark[p]==delStamp) continue;
            if(X[p] < xL || X[p] > xR) continue;
            res = mergeT(res, newLeaf(p));
        }
        return res;
    }
    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(X[V[mid]]>=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(X[V[mid]]<=xR){ idxR=mid; lo=mid+1; } else hi=mid-1; } }
    if(idxL > idxR) return 0;
    // find first deleted index in [idxL, idxR]
    int dl = (int)del.size();
    int di = 0;
    while(di < dl && del[di] < idxL) di++;
    if(di >= dl || del[di] > idxR){
        // no deletion in range -> early stop
        return clipByIndex((kind==0)?loRoot[d]:upRoot[d], idxL, idxR);
    }
    int res = 0;
    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){
            int piece = clipByIndex((kind==0)?loRoot[d]:upRoot[d], lastIncluded+1, a-1);
            res = mergeEnv(res, piece, dir);
        }
        ll xL_gap = (a > idxL) ? X[V[a-1]]+1 : xL;
        ll xR_gap = (b < idxR) ? X[V[b+1]]-1 : xR;
        if(xL_gap <= xR_gap){
            int sub = buildAligned(d+1, kind, dir, xL_gap, xR_gap);
            res = mergeEnv(res, sub, dir);
        }
        lastIncluded = b;
        i++;
    }
    if(lastIncluded+1 <= idxR){
        int piece = clipByIndex((kind==0)?loRoot[d]:upRoot[d], lastIncluded+1, idxR);
        res = mergeEnv(res, piece, dir);
    }
    return res;
}

// add the non-aligned layer-0 chain's x-extremes (global left/right) if they extend the hull.
static int addExtremes(int res, 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 && (!res || X[gl] < X[tn[res].first])) res = mergeEnv(newLeaf(gl), res, dir);
    if(gr!=gl && (!res || X[gr] > X[tn[res].last])) res = mergeEnv(res, newLeaf(gr), dir);
    return res;
}

static int buildLower(int d, ll xL, ll xR){
    int res = buildAligned(0, 0, +1, xL, xR);
    return addExtremes(res, +1);
}
static int buildUpper(int d, ll xL, ll xR){
    int res = buildAligned(0, 1, -1, xL, xR);
    return addExtremes(res, -1);
}

static ll solveQueries(){
    ll S = -1;
    ll ret = 0;
    for(int q=0;q<m;q++){
        tcnt = tcntBase;
        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 loR = buildLower(0, XMIN, XMAX);
        int upR = buildUpper(0, XMIN, XMAX);
        ll loSum = loR ? tn[loR].cs : 0;
        ll upSum = upR ? tn[upR].cs : 0;
        int loFirst = loR ? tn[loR].first : -1;
        int loLast  = loR ? tn[loR].last  : -1;
        int upFirst = upR ? tn[upR].first : -1;
        int upLast  = upR ? tn[upR].last  : -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++){ X[i]=rd(); Y[i]=rd(); }
    {
        unsigned s = 123456789u;
        for(int i=0;i<n;i++){ s ^= s<<13; s ^= s>>17; s ^= s<<5; rnd[i]=s; }
    }
    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;
}

评测结果