代码

// NOI2017 分身术 - clean upper/lower-hull split, per-gap, ARRAY-based running-hull 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.  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 merged into a running
// x-monotone hull kept as a fixed array of pieces (no treap, no path copying):
// each merge is a common-tangent bridge (alternating fixpoint, O(log) in practice)
// + an O(1)-amortized truncate/append with prefix cross-sums; area is read from the
// running prefix sum.  Total O((n + sum k) log n) with a small constant.
#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 = 2048;
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];

static vector<int> loV[MAXK];
static vector<int> upV[MAXK];
static int loLen2[MAXK], upLen2[MAXK];
static int loIdxOf[MAXN], upIdxOf[MAXN];
static vector<ll> loCs[MAXK], upCs[MAXK];

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;

struct EPiece { int d; int kind; int s; int len; };

// ---- running hull as fixed arrays of pieces ----
static EPiece spcArr[MAXSP];
static int spcSz[MAXSP+1];
static ll spcCs[MAXSP+1];
static int spcN;
static inline int spPoint(const EPiece& p, int k){ return (p.kind==0) ? loV[p.d][p.s+k] : upV[p.d][p.s+k]; }
static inline int spFirst(const EPiece& p){ return spPoint(p,0); }
static inline int spLast(const EPiece& p){ return spPoint(p,p.len-1); }
static inline ll spCS(const EPiece& p){
    if(p.len<=1) return 0;
    if(p.kind==0) return loCs[p.d][p.s+p.len-1] - loCs[p.d][p.s];
    return upCs[p.d][p.s+p.len-1] - upCs[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; }
    int idx=lo-1;
    return spPoint(spcArr[idx], k - spcSz[idx]);
}
static int spLowerTangentJ(int oi, const EPiece& p){
    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 EPiece& p){
    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 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 EPiece& 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 EPiece& 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 EPiece& 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 EPiece& 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 EPiece& 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 = 0, cj = 0;
    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 EPiece& 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 = 0, 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);
}
static void spAppend(const EPiece& 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]);
    EPiece 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 spInit(){
    spcN = 0; spcSz[0] = 0; spcCs[0] = 0;
}
static inline void spPushPiece(const EPiece& p, int kind){
    if(spcN == 0){ spcArr[0] = p; spcSz[1] = p.len; 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);
}

// envelope recursion (same as the full-envelope reference)
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];
}

static ll lowerFill(int A, int B, ll xL, ll xR, int& fP, int& lP){
    static vector<EPiece> arcs;
    arcs.clear();
    envRec(1, +1, xL, xR, arcs);
    spInit();
    if(A >= 0) spPushPiece({0,0,loIdxOf[A],1}, 0);
    for(auto& p : arcs) spPushPiece(p, 0);
    if(B >= 0) spPushPiece({0,0,loIdxOf[B],1}, 0);
    fP = spcN ? spFirst(spcArr[0]) : -1;
    lP = spcN ? spLast(spcArr[spcN-1]) : -1;
    return spcN ? spcCs[spcN] : 0;
}
static ll upperFill(int A, int B, ll xL, ll xR, int& fP, int& lP){
    static vector<EPiece> arcs;
    arcs.clear();
    envRec(evCnt-2, -1, xL, xR, arcs);
    spInit();
    if(A >= 0) spPushPiece({0,1,upIdxOf[A],1}, 1);
    for(auto& p : arcs) spPushPiece(p, 1);
    if(B >= 0) spPushPiece({0,1,upIdxOf[B],1}, 1);
    fP = spcN ? spFirst(spcArr[0]) : -1;
    lP = spcN ? spLast(spcArr[spcN-1]) : -1;
    return spcN ? spcCs[spcN] : 0;
}

// ---- 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++; }
}

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

        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;
                newChain = lowerFill(A, B, xL, xR, 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;
            }
        }

        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;
                newChain = upperFill(A, B, xL, xR, 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;
}

评测结果