代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
using namespace std;
typedef long long LL;
const int N=1e5+100,logn=1.3e7;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
struct P{ int x,y; }p[N];
inline bool operator < (const P &a,const P &b) { return a.x==b.x?a.y>b.y:a.x<b.x; }
inline P operator + (const P &a,const P &b) { return (P){a.x+b.x,a.y+b.y}; }
inline P operator - (const P &a,const P &b) { return (P){a.x-b.x,a.y-b.y}; }
inline LL operator * (const P &a,const P &b) { return 1LL*a.x*b.y-1LL*a.y*b.x; }
inline LL dot(const P &a,const P &b) { return 1LL*a.x*b.x+1LL*a.y*b.y; }
inline long double cross(const P &a,const P &b,const P &c,const P &d) {
	long double s1=(d-c)*(a-c),s2=(b-c)*(d-c);
	return a.x+(b.x-a.x)*s1/(s1+s2);
}
int del[N],q[N];

inline bool cmp(const int &a,const int &b) { return p[a]<p[b]; }

namespace Treap{
	int lc[logn],rc[logn],ls[logn],rs[logn],key[logn],tot;
	P p[logn];LL sum[logn];
	double mid;
	inline int node(P _p) {
		p[++tot]=_p,lc[tot]=rc[tot]=sum[tot]=0;
		ls[tot]=rs[tot]=tot;
		key[tot]=rand();
		return tot;
	}
	inline void copy(int &k) { lc[++tot]=lc[k],rc[tot]=rc[k],ls[tot]=ls[k],rs[tot]=rs[k],key[tot]=key[k],p[tot]=p[k],k=tot; }
	inline void update(int k) {
		sum[k]=0;ls[k]=rs[k]=k;
		if (lc[k]) {
			ls[k]=ls[lc[k]];
			sum[k]+=sum[lc[k]]+p[rs[lc[k]]]*p[k];
		}
		if (rc[k]) {
			rs[k]=rs[rc[k]];
			sum[k]+=sum[rc[k]]+p[k]*p[ls[rc[k]]];
		}
	}
	inline int merge(int x,int y) {
		if (!x||!y) return x|y;
		if (key[x]>key[y]) {
			copy(x);
			rc[x]=merge(rc[x],y);
			update(x);
			return x;
		} else {
			copy(y);
			lc[y]=merge(x,lc[y]);
			update(y);
			return y;
		}
	}
	inline pair<int,int>split(int a,int b) {
		int la=rs[lc[a]],ra=ls[rc[a]];
		int lb=rs[lc[b]],rb=ls[rc[b]];
		pair<int,int>pr;
		if (ra&&(p[ra]-p[b])*(p[a]-p[b])>0&&lb&&(p[lb]-p[a])*(p[b]-p[a])<0) {
			double c=cross(p[a],p[ra],p[b],p[lb]);
			if (c<mid) {
				copy(a);
				pr=split(rc[a],b);
				rc[a]=pr.first,pr.first=a;
				update(a);
				return pr;
			} else {
				copy(b);
				pr=split(a,lc[b]);
				lc[b]=pr.second,pr.second=b;
				update(b);
				return pr;
			}
		} else if (la&&(p[la]-p[b])*(p[a]-p[b])>=0) return split(lc[a],b);
		else if (rb&&(p[rb]-p[a])*(p[b]-p[a])<=0) return split(a,rc[b]);
		else if (ra&&(p[ra]-p[b])*(p[a]-p[b])>0) {//ע\xd2\xe2\xcaǷ\xf1ȡ\xb5Ⱥ\xc5
			copy(a);
			pr=split(rc[a],b);
			rc[a]=pr.first,pr.first=a;
			update(a);
			return pr;
		} else if (lb&&(p[lb]-p[a])*(p[b]-p[a])<0) {
			copy(b);
			pr=split(a,lc[b]);
			lc[b]=pr.second,pr.second=b;
			update(b);
			return pr;
		} else {
			if (rc[a]) copy(a),rc[a]=0,update(a);
			if (lc[b]) copy(b),lc[b]=0,update(b);
			return make_pair(a,b);
		}
	}
	inline int solve(int a,int b) {
		if (!a||!b) return a|b;
		mid=(p[rs[a]].x+p[ls[b]].x)*0.5;
		pair<int,int>pr=split(a,b);
		int ans=merge(pr.first,pr.second);
		return ans;
	}
};

int n;
struct seg{
#define lc (i<<1)
#define rc (lc|1)
	int id[N],rk[N];
	int T;
	int all[2000001],*All=all,*be[N<<2];
	int lev[N];
	inline void build(int i,int l,int r) {
		be[i]=All,All+=r-l+1;
		if (l==r) be[i][0]=lev[l];
		else {
			int mid=(l+r)>>1;
			build(lc,l,mid);
			build(rc,mid+1,r);
			be[i][mid-l]=lev[mid];
			be[i][mid-l+1]=lev[mid+1];
			for (int t=mid-1;t>=l;t--)
				be[i][t-l]=Treap::solve(lev[t],be[i][t-l+1]);
			for (int t=mid+2;t<=r;t++)
				be[i][t-l]=Treap::solve(be[i][t-l-1],lev[t]);
		}
	}
	inline void build() {
		int i;
		for (i=1;i<=n;i++) id[i]=i;
		sort(id+1,id+1+n,cmp);
		for (i=1;i<=n;i++) rk[id[i]]=i;
		for (i=1;i<=n;i++) lev[i]=Treap::node(p[id[i]]);
		build(1,1,n);
	}
	inline void query(int i,int l,int r,int L,int R) {
		int mid=(l+r)>>1;
		if (l!=r&&R<=mid) query(lc,l,mid,L,R);
		else if (mid<L) query(rc,mid+1,r,L,R);
		else {
			if (L<=mid) T=Treap::solve(T,be[i][L-l]);
			if (mid<R) T=Treap::solve(T,be[i][R-l]);
		}
	}
	inline LL solve(int m,P &L,P &R) {
		int i,last=1;T=0;
		for (i=1;i<=m;i++) q[i]=rk[del[i]];
		sort(q+1,q+1+m);
		for (i=1;i<=m;last=q[i++]+1)
			if (q[i]>last)
				query(1,1,n,last,q[i]-1);
		if (last<=n) query(1,1,n,last,n);
		L=Treap::p[Treap::ls[T]];
		R=Treap::p[Treap::rs[T]];
		return Treap::sum[T];
	}
#undef lc
#undef rc
}seg0,seg1;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("phantom.in","r",stdin);
	freopen("phantom.out","w",stdout);
#endif
	//cout<<(sizeof(seg0)*2+9*sizeof(Treap::lc))/1024/1024<<endl;return 0;
	n=gi();int m=gi(),i,k;LL ans=-1;
	P upL,upR,downL,downR;
	p[0]=(P){-1<<30,-1<<30};
	for (i=1;i<=n;i++) p[i].x=gi(),p[i].y=gi();
	seg0.build();
	for (i=1;i<=n;i++) p[i].y*=-1;
	seg1.build();
	const int TOT=Treap::tot;
	//fprintf(stderr,"%d\n",TOT);return 0;
	while (m--) {
		k=gi();
		for (i=1;i<=k;i++) del[i]=(ans+gi()+n)%n+1;
		ans=
			seg0.solve(k,upL,upR)+
			seg1.solve(k,downL,downR);
		downL.y*=-1;
		downR.y*=-1;
		ans+=downL*upL+upR*downR;
		printf("%lld\n",ans*=-1);
		Treap::tot=TOT;
	}
	return 0;
}

评测结果