代码

#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;
Opening *open;

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));
	open = new Opening();
	open->apos = -INF;
	open->bpos = INF;
}
void clear_for_query() {
    opening[0] = open;
	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;

    int num = 0;
    Point *record = NULL;
    Point *pa, *pb;

	for (int i = 1; i <= MAX_LAYERS; ++i, s = t) {
		cur = layer[i], hull = layer[i+1];

        if (num == 1) {
            pa = find_tangle(cur, record, CLOCKWISE);
            pb = find_tangle(cur, record, ANTICLOCKWISE);
            *s_op = new_opening(record, record, pa, pb, new_convex(LEFT_CONVEX, record), new_convex(RIGHT_CONVEX, record));
            area = cxsum(pa, pb) + cx(o, record, pa) + cx(o, pb, record);
        }

		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 (cur->n - (t-s) == 1 && num == 0) {
            num = 1;
            for (int j = 0; j < cur->n; ++j)
                if (removed[cur->p[j]->idx] == false) {
                    record = cur->p[j];
                    break;
                }
            continue;
        }
        if (cur->n - (t-s) == 0 && num == 0) {
            area = v[i+1][0];
            continue;
        }

		if (t - s == cur->n) {
            if (num == 1)
                continue;
			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 (num <= 0) 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;
			}
		}
        num += cur->n - (t-s);
		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+1; ++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 ? (n-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] + 1LL*rc) % n + 1;
			
            if (removed[idx[j]] == true)
				continue;
			removed[idx[j]] = true;
			
            if (p[idx[j]]->layer != 0)
				rp[++t] = p[idx[j]];
		}

        layer_by_layer(t, rp);

		for (int j = 1; j <= k; ++j) 
            removed[idx[j]] = false;

		cout << -area << endl;
	}
}

评测结果