代码

// noi17f 【NOI2017】分身术  -- v1: rebuild-only-when-a-hull-vertex-dies
// n points, m steps; step deletes k points (ids adaptive: p_i=((S+c_i) mod n)+1),
// print 2*area(hull(alive)) each step.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long u64;

static const int MAXN = 100005;
static int n, m;
static int px[MAXN], py[MAXN];
static int ord_[MAXN];
static unsigned char del_[MAXN], isHull[MAXN];
static int hull[MAXN];
static int curHull[MAXN];
static int curHsz = 0;
static ll curArea = 0;

static char *ib;
static inline int rd(char *&p) {
    while ((unsigned char)*p <= ' ') p++;
    int sgn = 1;
    if (*p == '-') { sgn = -1; p++; }
    int v = 0;
    while ((unsigned char)*p >= '0') { v = v * 10 + (*p - '0'); p++; }
    return v * sgn;
}

static inline ll cr(int a, int b, int c) {
    return (ll)(px[b] - px[a]) * (ll)(py[c] - py[a]) - (ll)(py[b] - py[a]) * (ll)(px[c] - px[a]);
}

static void rebuild() {
    for (int i = 0; i < curHsz; i++) isHull[curHull[i]] = 0;
    int hn = 0;
    for (int t = 0; t < n; t++) {
        int id = ord_[t];
        if (del_[id]) continue;
        while (hn >= 2 && cr(hull[hn - 2], hull[hn - 1], id) <= 0) hn--;
        hull[hn++] = id;
    }
    if (hn >= 2) {
        int lower = hn;
        for (int t = n - 2; t >= 0; t--) {
            int id = ord_[t];
            if (del_[id]) continue;
            while (hn >= lower + 1 && cr(hull[hn - 2], hull[hn - 1], id) <= 0) hn--;
            hull[hn++] = id;
        }
        hn--;
    }
    curHsz = hn;
    ll s = 0;
    if (hn >= 3) {
        for (int i = 0; i < hn; i++) {
            int a = hull[i], b = hull[i + 1 == hn ? 0 : i + 1];
            s += (ll)px[a] * py[b] - (ll)py[a] * px[b];
        }
        if (s < 0) s = -s;
    }
    curArea = s;
    for (int i = 0; i < hn; i++) { curHull[i] = hull[i]; isHull[hull[i]] = 1; }
}

static char ob[1 << 22];
static char *op = ob;
static inline void wnum(ll v) {
    char tmp[24];
    int l = 0;
    if (v == 0) tmp[l++] = '0';
    while (v) { tmp[l++] = char('0' + v % 10); v /= 10; }
    while (l) *op++ = tmp[--l];
    *op++ = '\n';
}

int main() {
    ib = (char *)malloc(64 << 20);
    size_t got = 0, r;
    while ((r = fread(ib + got, 1, (64u << 20) - got, stdin)) > 0) got += r;
    char *p = ib;
    n = rd(p); m = rd(p);
    for (int i = 0; i < n; i++) { px[i] = rd(p); py[i] = rd(p); ord_[i] = i; }
    sort(ord_, ord_ + n, [](int a, int b) {
        return px[a] != px[b] ? px[a] < px[b] : py[a] < py[b];
    });
    rebuild();
    // isHull now marks the vertices of hull(P); every query state is P \ D_t, so the
    // answer is area(H0) unless D_t removes one of those vertices.
    static unsigned char inH0[MAXN];
    memcpy(inH0, isHull, sizeof(inH0));
    ll h0Area = curArea;
    ll S = -1;
    int dl[128];
    for (int step = 0; step < m; step++) {
        int k = rd(p);
        int need = 0, cnt = 0;
        for (int j = 0; j < k; j++) {
            int c = rd(p);
            ll t = S + (ll)c;
            int id = (int)(((t % n) + n) % n);
            if (!del_[id]) { del_[id] = 1; dl[cnt++] = id; }
            if (inH0[id]) need = 1;
        }
        if (need) { rebuild(); } else { curArea = h0Area; }
        wnum(curArea);
        S = curArea;
        for (int j = 0; j < cnt; j++) del_[dl[j]] = 0;
        if (op - ob > (1 << 22) - 64) { fwrite(ob, 1, op - ob, stdout); op = ob; }
    }
    fwrite(ob, 1, op - ob, stdout);
    return 0;
}

评测结果