代码

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define CLOCKWISE 1
#define ANTICLOCKWISE -1
#define LEFT_CONVEX 1
#define RIGHT_CONVEX -1
#define CONSTRUCT_LAYERS 1
#define SINGLE_QUERY -1
#define MAX_N 100000
#define MAX_LAYERS 100
#define INF (~0U>>1)
using namespace std;

struct Point {
    int x, y;
    int layer, pos;
    int idx;
};
long long cx(Point *a, Point *b, Point *c) {
    return (long long) (b->x-a->x)*(c->y-a->y) - (long long) (b->y-a->y)*(c->x-a->x);
}
long long dj(Point *a, Point *b, Point *c) {
    return (long long) (b->x-a->x)*(c->x-a->x) + (long long) (b->y-a->y)*(c->y-a->y);
}
struct Hull {
    Point **p;
    int n;
    Hull (int n) {
        p = (Point **) malloc(sizeof(Point *) * (n+2));
        this->n = n;
    }
    Point *pos(int x) { while (x <= 0) x += n; while (x >= n) x -= n; return p[x]; }
};
struct Convex {
    Point **p;
    int h, t;
    int sign;
    bool refine(Point *a) { bool dom = false; while (h < t && cx(p[t-1], p[t], a) * sign >= 0) --t, dom = true; return dom; }
    void push(Point *a)   { refine(a); p[++t] = a; }
    Point *peek() 		  { return h == t ? NULL : p[h+1]; }
    Point *pop()          { return p[++h]; }
    Point *top()		  { return p[t]; }
};
struct Opening {
    Point *a, *b;
    int apos, bpos;
    Convex *a_con, *b_con;
};
struct Segment {
    int l, r;
};

long long *v[MAX_LAYERS+10];
long long area;
int removed[MAX_N+10];
int idx[MAX_N+10];

Point *o;
Point *p[MAX_N+10], *p2[MAX_N+10], *q[MAX_N+10], *rp[MAX_N+10];
Point **point_heap;
int p_point_heap;

Hull *layer[MAX_LAYERS+10];

Opening *opening[MAX_LAYERS+10];
Opening **s_op, **t_op, **n_op;

Convex *convex[MAX_LAYERS+10];
int n_convex;

Segment segment[MAX_LAYERS+10];


bool cmp_pointrp(Point *a, Point *b) {
    return a->layer == b->layer ? a->pos < b->pos : a->layer < b->layer;
}
bool cmp_point2d(Point *a, Point *b) {
    return a->x == b->x ? a->y < b->y : a->x < b->x;
}
bool cmp_opening(Opening *a, Opening *b) {
    return a->apos < b->apos;
}
void init() {
    o = new Point();
    o->x = o->y = 0;
    point_heap = (Point **) malloc(sizeof(Point*) * (4 * MAX_LAYERS * MAX_LAYERS));
    opening[0] = new Opening();
    opening[0]->apos = -INF;
    opening[0]->bpos = INF;
}
void clear_for_query() {
    s_op = n_op = opening;
    t_op = s_op+1;
    p_point_heap = 0;
    area = v[1][0];
}
Point **point_malloc(int n) {
    Point **p = point_heap + (p_point_heap);
    p_point_heap += n;
    return p;
}
Convex *new_convex(int sign, Point *a) {
    Convex *con = new Convex();
    con->p = point_malloc(MAX_LAYERS+2);
    con->h = 1, con->t = 0;
    con->sign = sign;
    con->push(a);
    return con;
}
Opening *new_opening(Point *a, Point *b, Point *pa, Point *pb, Convex *a_con, Convex *b_con) {
    Opening *op = new Opening();
    op->a = a, op->b = b;
    op->apos = pa->pos, op->bpos = pb->pos;
    op->a_con = a_con;
    op->b_con = b_con;
    if (op->apos > op->bpos)
        op->bpos += layer[pa->layer]->n;
    return op;
}
long long cxsum(Point *a, Point *b) {
    long long *vp = v[a->layer];
    return a->pos <= b->pos ? vp[b->pos]-vp[a->pos] : vp[0] - (vp[a->pos]-vp[b->pos]);
}
Point *find_tangle(Hull *hull, Point *a, int sign) {
    int n = hull->n;
    int bias = sign == -1;
    if (n == 0)
        return NULL;
    if (n == 1)
        return hull->p[n];
    
    Point *b = hull->pos(sign+bias);

    bool dom = cx(a, hull->pos(sign+bias), hull->pos(bias)) * sign <= 0;
    int l = 2, r = n, j, an = 1;
    
    for (; j = (l+r)>>1, l <= r; ) {
        if (cx(a, b, hull->pos(sign*j+bias)) * sign <= 0) {
            if (dom) r = j-1;
            else l = j+1;
        }
        else if (cx(a, hull->pos(sign*j+bias), hull->pos(sign*(j-1)+bias)) * sign <= 0)
            an = j, l = j+1;
        else r = j-1;
    }	return hull->pos(sign*an+bias);
}
bool find_new_opening(Hull *hull, Point *a, Point *b, Convex *a_con, Convex *b_con) {
    Point *s1 = a, *s2 = b;
    Point *pa, *pb;
    while (a->idx != b->idx) {
        pa = find_tangle(hull, a, CLOCKWISE);
        pb = find_tangle(hull, b, ANTICLOCKWISE);

        if (a_con->peek() && (pa == NULL || cx(a, pa, a_con->peek()) >= 0)) {
            area += cx(o, a, a_con->peek());
            a = a_con->pop();
        }
        else if (b_con->peek() && (pb == NULL || cx(b, b_con->peek(), pb) >= 0)) {
            area += cx(o, b_con->peek(), b);
            b = b_con->pop();
        }
        else {
            area += cx(o, a, pa) + cx(o, pb, b) + cxsum(pa, pb);
            *(++n_op) = new_opening(a, b, pa, pb, a_con, b_con);
            return 1;
        }
    }
    return 0;
}
void layer_by_layer(int m, Point **rp) {
    Point *a, *b, *ia, *ib, *a_del, *b_del;
    Convex *a_con, *b_con;
    Segment *seg_s, *seg, *seg_end;
    Hull *cur, *hull;
    sort(rp+1, rp+m+1, cmp_pointrp);
    int s = 1, t;
    
    for (int i = 1; i < MAX_LAYERS; ++i, s = t) {
        cur = layer[i], hull = layer[i+1];
        if (s > m || rp[s]->layer != i)
            break;
        t = s;
        while (t <= m && rp[t]->layer == rp[s]->layer)
            ++t;
        if (t == s)
            break;

        if (t - s == cur->n) {
            for (Opening **p_op = s_op; p_op != t_op; ++p_op) {
                Opening *op = *p_op;
                area -= cx(o, op->a, cur->pos(op->apos));
                area -= cx(o, cur->pos(op->bpos), op->b);
                area -= cxsum(cur->pos(op->apos), cur->pos(op->bpos));
                find_new_opening(hull, op->a, op->b, op->a_con, op->b_con);
            }
            s_op = t_op;
            t_op = n_op + 1;
            sort(s_op, t_op, cmp_opening);
            continue;
        }
        
        seg_s = seg = segment;
        for (int j = s+1; j < t; ++j)
            if (rp[j]->pos != rp[j-1]->pos+1) {
                seg->r = rp[j-1]->pos;
                (++seg)->l = rp[j]->pos;
            }
        if (rp[s]->pos == 1 && rp[t-1]->pos == cur->n) {
            seg_s->l = seg->l - cur->n;
            --seg;
        }
        else seg_s->l = rp[s]->pos, seg->r = rp[t-1]->pos;
        int n_seg = seg-seg_s+1;
        
        while (seg->r < 2*cur->n) {
            ++seg;
            seg->r = (seg-n_seg)->r + cur->n;
            seg->l = (seg-n_seg)->l + cur->n;
        }
        if (i == 1) seg_end = seg_s + n_seg;
        else seg_end = seg+1;
        seg = seg_s;
    
        for (Opening **p_op = s_op; p_op != t_op; ++p_op) {
            Opening *op = *p_op;	
            while (seg != seg_end && seg->r < op->apos)
                ++seg;
            while (seg != seg_end && seg->l <= op->bpos) {
                ia = cur->pos(seg->l-1);
                ib = cur->pos(seg->r+1);
                
                if (seg->l <= op->apos) {
                    a = op->a, a_con = op->a_con;
                    a_del = cur->pos(op->apos);
                    area -= cx(o, a, a_del);
                }
                else {
                    a = ia, a_con = new_convex(LEFT_CONVEX, a);
                    a_del = ia;
                }
                if (seg->r >= op->bpos) {
                    b = op->b, b_con = op->b_con;
                    b_del = cur->pos(op->bpos);
                    area -= cx(o, b_del, b);
                }
                else {
                    b = ib, b_con = new_convex(RIGHT_CONVEX, b);
                    b_del = ib;
                }
                if (b == ib) {
                    while (a_con->h < a_con->t && cx(a, b, a_con->top()) <= 0) --a_con->t;
                    a_con->push(b);
                }
                else if (a == ia) {
                    while (b_con->h < b_con->t && cx(a, b, b_con->top()) <= 0) --b_con->t;
                    b_con->push(a);
                }
                if (cx(a, b, ia) > 0 && (a_con->refine(ia) || b_con->refine(ia)))
                    a_con->push(ia), b_con->push(ia);
                if (cx(a, b, ib) > 0 && (a_con->refine(ib) || b_con->refine(ib)))
                    b_con->push(ib), a_con->push(ib);
                area -= cxsum(a_del, b_del);
            
                find_new_opening(hull, a, b, a_con, b_con);
                
                if (seg->r >= op->bpos)
                    break;
                ++seg;
            }
        }
        s_op = t_op;
        t_op = n_op + 1;
        sort(s_op, t_op, cmp_opening);
    }
}
void bruteforce(int n, Point **p, int &t, Point **q, int mode) {
    int h;
    h = 1, t = 0;
    for (int i = 1; i <= n; ++i) {
        if (mode == CONSTRUCT_LAYERS && p[i]->layer != 0)
            continue;
        if (mode == SINGLE_QUERY && removed[p[i]->idx] == true)
            continue;
        while (t > 1 && cx(q[t-1], q[t], p[i]) >= 0) --t;
        q[++t] = p[i];
    }
    h = t, --t;
    for (int i = n; i >= 1; --i) {
        if (mode == CONSTRUCT_LAYERS && p[i]->layer != 0)
            continue;
        if (mode == SINGLE_QUERY && removed[p[i]->idx] == true)
            continue;
        while (h < t && cx(q[t-1], q[t], p[i]) >= 0) --t;
        q[++t] = p[i];
    }
    if (t == 1) t = 2, q[t+1] = q[1];
    if (t <= 0) t = 1;
}
void construct_layers(int n, Point **p, Point **q) {
    int t;
    sort(p+1, p+n+1, cmp_point2d);
    for (int i = 1; i <= MAX_LAYERS; ++i) {
        bruteforce(n, p, t, q, CONSTRUCT_LAYERS);
        Hull *hull = new Hull(t-1);
        layer[i] = hull;
        if (t == 1)
            break;
        for (int j = 1; j < t; ++j) {
            q[j]->layer = i;
            q[j]->pos = j;
            hull->p[j] = q[j];
        }
        hull->p[0] = hull->p[t-1];
        hull->p[t] = hull->p[1];
        long long *vp = (long long *) malloc(sizeof(long long)*(t+2));
        for (int j = 1; j <= t; ++j)
            vp[j] = j == 1 ? 0 : vp[j-1] + cx(o, q[j-1], q[j]);
        vp[0] = vp[t];
        v[i] = vp;
    }
}
int main() {
    init();
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        Point *pt = new Point();
        scanf("%d %d", &x, &y);
        pt->x = x, pt->y = y;
        pt->idx = i;
        p[i] = p2[i] = pt;
    }
    construct_layers(n, p2, q);
    for (int i = 1; i <= m; ++i) {
        int rc = i == 1 ? -1 : (-area) % n;
        clear_for_query();
        
        int x, k, t = 0;
        scanf("%d", &k);
        for (int j = 1; j <= k; ++j) {
            scanf("%d", idx+j);
            idx[j] = (idx[j] + rc) % n + 1;
            if (p[idx[j]]->layer != 0)
                rp[++t] = p[idx[j]];
        }
        if (t >= MAX_LAYERS) {
            area = 0;
            for (int j = 1; j <= k; ++j) removed[idx[j]] = true;
            bruteforce(n, p2, t, q, SINGLE_QUERY);
            for (int j = 1; j <= k; ++j) removed[idx[j]] = false;
            for (int i = 2; i <= t; ++i)
                area += cx(o, q[i-1], q[i]);
        }
        else layer_by_layer(t, rp);
        cout << -area << endl;
    }
}

评测结果