代码

// NOI2017 分身术 - clean upper/lower-hull split, per-gap, persistent-treap merge.
//
// Onion layers are stored as strictly-x-monotone pure chains (loV[d] = lower,
// upV[d] = upper; vertical edges at the x-extremes collapsed).  A query computes
// the lower hull and upper hull of the surviving points INDEPENDENTLY:
//   - lower hull = loV[0] with each deleted run replaced by a lower-hull fill of
//     the inner layers' loV chains (clipped by the run's x-interval);
//   - upper hull = upV[0] with each deleted run replaced by an upper-hull fill of
//     the inner layers' upV chains.
// The baseline area of loV[0]/upV[0] comes from prefix cross-sums, so only the
// O(k) deleted runs are touched per query (never the whole x-range, and never the
// surviving arcs).  Each fill is the same x-monotone recursion as the full
// envelope (envRec), so deep notches that fall through to the opposite chain type
// are handled exactly as before, but started at the first inner layer and clipped
// to the run's x-range.  Pieces are extracted from static chain treaps by O(log n)
// rank splits and merged by a common-tangent bridge + concat; area is the running
// root's csum.  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 int layer_of[MAXN], pos_of[MAXN];
static int loLen[MAXK];              // Andrew lower-chain length in vert[d]

// pure x-monotone chains (vertical edges collapsed at the extreme x)
static vector<int> loV[MAXK];        // lower chain, x strictly increasing
static vector<int> upV[MAXK];        // upper chain, x strictly increasing
static int loLen2[MAXK], upLen2[MAXK];
static int loIdxOf[MAXN], upIdxOf[MAXN];
static vector<ll> loCs[MAXK], upCs[MAXK]; // loCs[d][i] = sum of first i edges of loV[d]

static vector<int> delLo[MAXK], delUp[MAXK];
static int delMark[MAXN];
static int delStamp = 0;
static int gOrder[MAXN];
static int n, m;

static int evD[MAXK*2+2], evK[MAXK*2+2];
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; }
    }
}
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;
}
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);
}

static inline int mergeLower(int a, int b){ return a ? (b ? tmergeLower(a,b) : a) : b; }
static inline int mergeUpper(int a, int b){ return a ? (b ? tmergeUpper(a,b) : a) : b; }

struct EPiece { int d; int kind; int s; int len; };
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 (same as the full-envelope reference): processes the ordered
// chains clipped to [xL,xR], recursing into the next inner chain only where the
// current one is deleted. dir=+1 lower, -1 upper.
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; }
        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;
            ll xR2=(qk<j)?X[V[qk+1]]-1:xR;
            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;
    }
}

static inline ll edgeSumLo(int d, int a, int b){
    int L = loLen2[d];
    if(L < 2) return 0;
    if(a < 0) a = 0;
    if(b > L-2) b = L-2;
    if(a > b) return 0;
    return loCs[d][b+1] - loCs[d][a];
}
static inline ll edgeSumUp(int d, int a, int b){
    int L = upLen2[d];
    if(L < 2) return 0;
    if(a < 0) a = 0;
    if(b > L-2) b = L-2;
    if(a > b) return 0;
    return upCs[d][b+1] - upCs[d][a];
}

// lower fill: chain from A (or inner leftmost if A<0) to B (or inner rightmost if B<0)
// across inner layers' loV chains clipped to [xL,xR] (falling through to upper chains
// of the same/outer layers when the lower chains are depleted). Returns root treap.
static int lowerFill(int A, int B, ll xL, ll xR, ll& csum, int& fP, int& lP){
    static vector<EPiece> arcs;
    arcs.clear();
    envRec(1, +1, xL, xR, arcs);
    int root = (A >= 0) ? tnew(A) : 0;
    for(auto& p : arcs){ root = mergeLower(root, extractPiece(p)); }
    if(B >= 0) root = mergeLower(root, tnew(B));
    csum = root ? TN[root].csum : 0;
    fP = root ? TN[root].L : -1;
    lP = root ? TN[root].R : -1;
    return root;
}
static int upperFill(int A, int B, ll xL, ll xR, ll& csum, int& fP, int& lP){
    static vector<EPiece> arcs;
    arcs.clear();
    envRec(evCnt-2, -1, xL, xR, arcs);
    int root = (A >= 0) ? tnew(A) : 0;
    for(auto& p : arcs){ root = mergeUpper(root, extractPiece(p)); }
    if(B >= 0) root = mergeUpper(root, tnew(B));
    csum = root ? TN[root].csum : 0;
    fP = root ? TN[root].L : -1;
    lP = root ? TN[root].R : -1;
    return root;
}

// ---- 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();
        for(int t=0;t<h[K];t++){ layer_of[H[t]]=K; pos_of[H[t]]=t; }
        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();
        loCs[K].assign(loLen2[K]+1,0);
        for(int i=1;i<loLen2[K];i++) loCs[K][i]=loCs[K][i-1]+cross2(loV[K][i-1],loV[K][i]);
        if(loLen2[K]>=1) loCs[K][loLen2[K]]=loCs[K][loLen2[K]-1];
        upCs[K].assign(upLen2[K]+1,0);
        for(int i=1;i<upLen2[K];i++) upCs[K][i]=upCs[K][i-1]+cross2(upV[K][i-1],upV[K][i]);
        if(upLen2[K]>=1) upCs[K][upLen2[K]]=upCs[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();
        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;
        loCs[K].assign(loLen2[K]+1,0);
        for(int i=1;i<loLen2[K];i++) loCs[K][i]=loCs[K][i-1]+cross2(loV[K][i-1],loV[K][i]);
        if(loLen2[K]>=1) loCs[K][loLen2[K]]=loCs[K][loLen2[K]-1];
        for(int t=0;t<(int)rest.size();t++) loIdxOf[rest[t]]=t;
        K++;
    }
    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++; }
    for(int d=numProper-1; d>=0; d--){ evD[evCnt]=d; evK[evCnt]=1; evCnt++; }
    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()); }
        }

        // ---- lower hull ----
        ll lowerSum = (loLen2[0] >= 2) ? loCs[0][loLen2[0]-1] : 0;
        int loFirst=-1, loLast=-1;
        if(delLo[0].empty()){
            if(loLen2[0] > 0){ loFirst = loV[0][0]; loLast = loV[0][loLen2[0]-1]; }
        } else {
            if(loLen2[0] > 0){
                if(delMark[loV[0][0]] != delStamp) loFirst = loV[0][0];
                if(delMark[loV[0][loLen2[0]-1]] != delStamp) loLast = loV[0][loLen2[0]-1];
            }
            for(size_t ri=0; ri<delLo[0].size(); ){
                int p = delLo[0][ri], q = p;
                while(ri+1 < delLo[0].size() && delLo[0][ri+1] == q+1){ q = delLo[0][++ri]; }
                ri++;
                int A = (p>0) ? loV[0][p-1] : -1;
                int B = (q+1 < loLen2[0]) ? loV[0][q+1] : -1;
                ll xL = (A>=0) ? X[A]+1 : xminAll;
                ll xR = (B>=0) ? X[B]-1 : xmaxAll;
                ll oldArc = edgeSumLo(0, p-1, q);
                ll newChain; int fP, lP;
                lowerFill(A, B, xL, xR, newChain, fP, lP);
                lowerSum += newChain - oldArc;
                if(loFirst < 0 && p == 0 && fP >= 0) loFirst = fP;
                if(loLast < 0 && q == loLen2[0]-1 && lP >= 0) loLast = lP;
            }
        }

        // ---- upper hull ----
        ll upperSum = (upLen2[0] >= 2) ? upCs[0][upLen2[0]-1] : 0;
        int upFirst=-1, upLast=-1;
        if(delUp[0].empty()){
            if(upLen2[0] > 0){ upFirst = upV[0][0]; upLast = upV[0][upLen2[0]-1]; }
        } else {
            if(upLen2[0] > 0){
                if(delMark[upV[0][0]] != delStamp) upFirst = upV[0][0];
                if(delMark[upV[0][upLen2[0]-1]] != delStamp) upLast = upV[0][upLen2[0]-1];
            }
            for(size_t ri=0; ri<delUp[0].size(); ){
                int p = delUp[0][ri], q = p;
                while(ri+1 < delUp[0].size() && delUp[0][ri+1] == q+1){ q = delUp[0][++ri]; }
                ri++;
                int A = (p>0) ? upV[0][p-1] : -1;
                int B = (q+1 < upLen2[0]) ? upV[0][q+1] : -1;
                ll xL = (A>=0) ? X[A]+1 : xminAll;
                ll xR = (B>=0) ? X[B]-1 : xmaxAll;
                ll oldArc = edgeSumUp(0, p-1, q);
                ll newChain; int fP, lP;
                upperFill(A, B, xL, xR, newChain, fP, lP);
                upperSum += newChain - oldArc;
                if(upFirst < 0 && p == 0 && fP >= 0) upFirst = fP;
                if(upLast < 0 && q == upLen2[0]-1 && lP >= 0) upLast = lP;
            }
        }

        ll ans = lowerSum - upperSum;
        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;
}

评测结果