「雅礼集训 2018 Day5」Convex 题解

神秘的回滚莫队

思路

首先求出凸包（这个应该都会），然后算凸包的面积可以把凸包剖成三角形然后用叉积来算，即 $|(x1-x2)(y1-y3)-(y1-y2)(x1-x3)|$，刚好是原面积的两倍。

那么如何计算区间内的顶点组成的凸包面积？

假如题目给定的所有顶点都刚好是按照凸包逆时针排的（即题目中的特殊性质），那么可以直接维护一颗线段树，每次区间查询面积。

但是如果是一堆散点，线段树就无法维护了。

先考虑暴力，每次询问将区间内的点依次暴力加入凸包计算面积。

先考虑插入一个点时的贡献。

如图，现在我们要将红色的点插入原有凸包中。

插入完之后，新增了红色的边，删去了蓝色的边，增加了用红色和蓝色边围起来的三角形的面积。

加入一个点时，增加的面积是当前已加入的点中在凸包上的和它相邻的两个点。

考虑莫队，用一个set维护当前已经加入的点，每次加入和删除点时就在set中找前驱后继，这样时间复杂度是 $(O \sqrt{n}\log n)$ 的，无法通过。

每次用set找前驱后继太费时间了，考虑换成链表。

但用链表很难处理加入操作，只能做删除操作。

那么就想到了回滚莫队，就只需要维护删除和撤销删除操作了，而且由于是回滚，撤销删除都是即时的，每次删除只改相邻点的链表，不改自己的，这样撤销就可以直接连回去了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
struct P{
	ll x,y,id;
}a[150010],stk[150010];
int sti;
ll cross(P t,P a,P b){ // 计算向量叉积
	return (t.x-a.x)*(t.y-b.y)-(t.y-a.y)*(t.x-b.x);
} 
int p[150010]; // p[i]表示原编号为i的点在极角序中的排名
bool cmp(P a,P b){ // 按x,y排序求凸包
	if(a.x!=b.x)return a.x<b.x;
	return a.y<b.y;
}
bool cmpid(P a,P b){ // 按极角序排名排序
	return p[a.id]<p[b.id];
}
int B; // 莫队块长
struct Q{
	int l,r,id;
}q[150010];
bool cmpq(Q a,Q b){ // 莫队排序：左端点分块，同块内右端点降序
	if(a.l/B!=b.l/B)return a.l<b.l;
	return a.r>b.r;
}
ll s; // 当前维护的凸包面积的两倍
int pre[150010],nxt[150010]; // 双向链表维护极角序相邻关系
void del(int x){ // 删除点x
	x=p[x];
	int l=pre[x],r=nxt[x];
	s-=abs(cross(a[x],a[l],a[r])); // 减去该点与相邻点构成的三角形面积
	pre[r]=l;nxt[l]=r; // 链表跳过该点，但不修改该点自身的pre和nxt，以便回滚
}
void add(int x){ // 撤销删除（加回）点x
	x=p[x];
	int l=pre[x],r=nxt[x]; // 利用del时保留的原始邻居信息
	s+=abs(cross(a[x],a[l],a[r])); // 加回面积
	pre[r]=x;nxt[l]=x; // 恢复链表连接
}
ll ans[150010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;a[i].id=i;
	}
	sort(a+1,a+1+n,cmp); // 求下凸包，分配极角序排名
	for(int i=1;i<=n;i++){
		while(sti>1&&cross(stk[sti-1],stk[sti],a[i])<=0)sti--;
		stk[++sti]=a[i];
	}
	int id=0;
	for(int i=1;i<=sti;i++)p[stk[i].id]=++id;
	sti=0;
	for(int i=n;i;i--){ // 求上凸包，继续分配排名
		while(sti>1&&cross(stk[sti-1],stk[sti],a[i])<=0)sti--;
		stk[++sti]=a[i];
	}
	for(int i=2;i<sti;i++)p[stk[i].id]=++id;
	for(int i=1;i<=n;i++)p[i]=(p[i]+114514)%n+1; // 随机偏移防卡
	sort(a+1,a+1+n,cmpid); // 将点按极角序重排
	B=sqrt(n);
	for(int i=1;i<=m;i++){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmpq);
	int l=1,r=n;
	for(int i=1;i<=n;i++){ // 初始化环形双向链表
		pre[i]=i-1;nxt[i]=i+1;
		if(i==1)pre[i]=n;
		if(i==n)nxt[i]=1;
	}
	for(int i=2;i<n;i++)s+=abs(cross(a[1],a[i],a[i+1])); // 初始化总面积
	for(int i=0,j=1;i*B<=n;i++){ // 莫队主循环，i为块号
		while(r<n)add(++r); // 跨块时恢复右指针到n
		while(l<i*B)del(l++); // 跨块时左指针移动到当前块左边界
		for(;j<=m&&q[j].l/B==i;j++){ // 处理左端点在当前块内的查询
			while(r>q[j].r)del(r--); // 右指针向左移动(只删)
			while(l<q[j].l)del(l++); // 左指针向右移动(只删)
			ans[q[j].id]=s; // 记录答案
			while(l>i*B)add(--l); // 回滚左指针(逆序撤销)
		}
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<'\n'; 
	}
	return 0;
}