Loj 6504 Convex

Posted on | Views:

回滚莫队.

若直接用莫队处理,插入时需要先二分找出它的前驱后继,时间复杂度 $O(n\sqrt n \log n)$ .

但删除是不需要二分查找的,用链表维护好它的前驱后继,直接断掉就可以了.

于是我们可以用回滚莫队来做,就只有删除和撤销两个操作.

具体来说,把所有询问按照左端点所在块为第一关键字,右端点为第二关键字排序.

对于所有左端点所在块相同的询问,按照右端点递减的顺序一起处理.

初始时将左端点设为该块最左侧,右端点设为 $n$ ,处理询问时,将左右端点移过来,回答后再将左端点移回去.

移回去时,暴力撤销移过来的每步操作即可,切换块时,把右端点移回 $n$ ,左端点移到下一个块的最左侧.

预处理出 $1\sim n$ 形成的凸包中,每个点的前驱后继,跑莫队时就只有删除和撤销操作了.

时间复杂度 $O(n\log n+n\sqrt n)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1.5e5+10;
struct v2
{
	int x,y,id;
	ll operator * (const v2 &rhs) const
	{
		return 1LL*x*rhs.y-1LL*y*rhs.x;
	}
	double angle;
	bool operator < (const v2 &rhs) const
	{
		return angle<rhs.angle;
	}
}p[MAXN],tmp[MAXN];
int n,m,B,pre[MAXN],nxt[MAXN];
ll cur=0,ans[MAXN];
struct Query
{
	int l,r,bel,id;
	bool operator < (const Query &rhs) const
	{
		return bel==rhs.bel?r>rhs.r:bel<rhs.bel;
	}
}q[MAXN];
void del(int x)
{
	int l=pre[x],r=nxt[x];
	cur-=p[l]*p[x]+p[x]*p[r];
	cur+=p[l]*p[r];
	nxt[l]=r,pre[r]=l;
}
void undel(int x)
{
	int l=pre[x],r=nxt[x];
	cur-=p[l]*p[r];
	cur+=p[l]*p[x]+p[x]*p[r];
	nxt[l]=pre[r]=x;
}
int main()
{
	n=read(),m=read();
	B=sqrt(n);
	for(int i=1;i<=n;++i)
	{
		p[i].x=read(),p[i].y=read();
		p[i].id=i;
		p[i].angle=atan2(p[i].y,p[i].x);
		tmp[i]=p[i];
	}
	sort(tmp+1,tmp+1+n);
	for(int i=1;i<n;++i)
	{
		pre[tmp[i+1].id]=tmp[i].id;
		nxt[tmp[i].id]=tmp[i+1].id;
		cur+=tmp[i]*tmp[i+1];
	}
	pre[tmp[1].id]=tmp[n].id,nxt[tmp[n].id]=tmp[1].id;
	cur+=tmp[n]*tmp[1];
	for(int i=1;i<=m;++i)
	{
		q[i].l=read(),q[i].r=read();
		q[i].bel=(q[i].l-1)/B,q[i].id=i;
	}
	sort(q+1,q+1+m);
	int L=1,R=n,t=0;
	for(int i=1,j=0;i<=m;++i)
	{
		int pos=q[i].bel*B+1;
		while(R<n)
			undel(++R);
		while(L<pos)
			del(L++); 
		while(j+1<=m && q[j+1].bel==q[i].bel)
		{
			++j;
			while(R>q[j].r)
				del(R--);
			while(L<q[j].l)
				del(L++);
			ans[q[j].id]=cur;
			while(L>pos)
				undel(--L);
		}
		i=j;
	}
	for(int i=1;i<=m;++i)
		printf("%lld\n",abs(ans[i]));
	return 0;
}