代码

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstdarg>
#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


static const char *duck_input;
static char *duck_output;

static int duck_scanf(const char *format, ...) {
    va_list args;
    va_start(args, format);
    int got = 0;
    for (const char *f = format; *f; ++f) {
        if (*f == '%' && f[1] == 'd') {
            *va_arg(args, int *) = (int)duck_read_i64(&duck_input);
            ++got;
            ++f;
        }
    }
    va_end(args);
    return got;
}

struct DuckCin {
    DuckCin &operator>>(int &x) {
        x = (int)duck_read_i64(&duck_input);
        return *this;
    }
};
struct DuckEndl {};
struct DuckCout {
    DuckCout &operator<<(long long x) {
        duck_output = duck_write_i64(duck_output, x);
        return *this;
    }
    DuckCout &operator<<(DuckEndl) {
        *duck_output++ = '\n';
        return *this;
    }
};
static DuckCin duck_cin;
static DuckCout duck_cout;
static DuckEndl duck_endl;

#define scanf duck_scanf
#define cin duck_cin
#define cout duck_cout
#define endl duck_endl
#define main phantom_main
#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;
	}
	return 0;
}
#undef main
#undef endl
#undef cout
#undef cin
#undef scanf

static void solve(DuckInfo *info) {
    duck_input = info->stdin_ptr;
    duck_output = info->stdout_ptr;
    phantom_main();
    info->stdout_size = duck_output - info->stdout_ptr;
}

#ifdef LOCAL
int main() {
    static char in[16000000], out[4000000];
    DuckInfo info = {};
    info.stdin_size = fread(in, 1, sizeof in, stdin);
    info.stdin_ptr = in;
    info.stdout_ptr = out;
    solve(&info);
    fwrite(out, 1, info.stdout_size, stdout);
}
#else
int main(int argc, char **argv) {
    DuckInfo *info = duck_info(argc, argv);
    solve(info);
    return 0;
}
#endif

评测结果