BZOJ 3533 向量集

发表于 | 更新于

Link

Solution

好一道数据结构套计算几何题啊。。 （虽然是基础数据结构套基础计算几何。。但对我这种蒟蒻就已经有超强杀伤力了。。） 维护一个支持插入的向量序列，输出区间中的向量与给定向量最大的内积。 首先很容易看出答案向量的终点在凸包上。 还有一个看起来对但不会证的结论：给定向量与终点在凸包上的向量内积值vv是单峰的。 y>0y>0，vv在上凸壳上有最大值 y<0y<0，vv在下凸壳上有最大值 于是用线段树维护序列，每个节点维护区间的凸包。 但是凸包的合并类似Graham(Andrew)，是O(n)O(n)的，每次都合并肯定合不起。 但是：一个区间只有塞满了之后才会被查询。 于是在区间塞满的时候再合并。这样合并的总复杂度是O(nlogn)O(n\log n)的。 查询的时候在凸包上三分。一开始想得是要把查询的区间在线段树上对应的logn\log n个区间的凸包合并出来得到整个区间的凸包再三分。单次查询的复杂度就成了O(nlogn)O(n\log n)? 然后发现网上给出的做法都是分别在每个节点上三分，然后取最大值，O(log2n)O(\log^2 n)解决问题。

Tips

如果信息合并的复杂度高，就根据查询的情况来减少合并的次数。 这个在每个节点上三分的做法可以类比区间第K大的线段树套平衡树做法，只是这个可能会产生一些无用的解，但不影响正确性和复杂度。

Code

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long long LL;
const int MAXN=4e5+10;

using std::vector;
using std::max;
struct point
{
	int x,y;
	point(){}
	point(int x,int y):x(x),y(y){}
	bool operator <(const point &a)const
	{
		if(x!=a.x) return x<a.x;
		return y<a.y;
	}
};
point operator -(const point &a,const point &b){return point(a.x-b.x,a.y-b.y);}
LL inner(const point &a,const point &b){return (LL)a.x*b.x+(LL)a.y*b.y;}
LL outer(const point &a,const point &b){return (LL)a.x*b.y-(LL)a.y*b.x;}
typedef vector<point> hull;
const int UP_HULL=0,DOWN_HULL=1;
void Merge(hull& a,hull& b,hull &dest,int kind)
{
	static point stack[MAXN];int top=0;
	int na=a.size()-1,nb=b.size()-1;
	dest.clear();
	for(int pa=0,pb=0;pa<=na || pb<=nb;)
	{
		point cur;
		if(pa>na) cur=b[pb++];
		else if(pb>nb) cur=a[pa++];
		else cur=a[pa]<b[pb]?a[pa++]:b[pb++];
		while(top>=2 && outer(stack[top]-stack[top-1],cur-stack[top])*(kind==UP_HULL?1:-1)>=0) top--;
		stack[++top]=cur;
	}
	for(int i=1;i<=top;i++) dest.push_back(stack[i]);
}
LL Trisect(hull& a,const point& p)
{
	int L=0,R=a.size()-1,M1,M2;
	while(L!=R)
	{
		int M1=L+(R-L)/3,M2=R-(R-L)/3;
		if(inner(a[M1],p)>inner(a[M2],p))
			R=M2-1;
		else
			L=M1+1;
	}
	return inner(a[L],p);
}
namespace iSeg
{
	const int SIZE=MAXN<<2;
	struct Node
	{
		hull convex[2];
		Node *son[2];
		Node(Node *lc=0,Node *rc=0)
		{
			son[0]=lc,son[1]=rc;
			convex[0].clear(),convex[1].clear();
		}
		void up()
		{
			Merge(son[0]->convex[0],son[1]->convex[0],convex[0],0);
			Merge(son[0]->convex[1],son[1]->convex[1],convex[1],1);
		}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++) Node;
	Node *newNode(){return new(ME++) Node(null,null);}
	struct Seg
	{
		Node *root;
		Seg(){root=null;}
		int TL,TR;
		void Init(int l,int r){TL=l;TR=r;}
		void Edit(Node *&pos,int L,int R,int goal,const point &p)
		{
			if(pos==null) pos=newNode();
			if(L==R)
			{
				pos->convex[UP_HULL].push_back(p);
				pos->convex[DOWN_HULL].push_back(p);
			}
			else
			{
				int MID=(L+R)>>1;
				if(goal<=MID) Edit(pos->son[0],L,MID,goal,p);
				else Edit(pos->son[1],MID+1,R,goal,p);
				if(goal==R) pos->up();
			}
		}

		LL Access(Node *pos,int L,int R,int l,int r,const point &p)//一个区间只会合并一次 n log n
		{
			assert(pos!=null);
			if(L==l && R==r) return Trisect(pos->convex[p.y>0?UP_HULL:DOWN_HULL],p);
			else
			{
				int MID=(L+R)>>1;
				if(r<=MID) return Access(pos->son[0],L,MID,l,r,p);
				else if(MID+1<=l) return Access(pos->son[1],MID+1,R,l,r,p);
				else return max(Access(pos->son[0],L,MID,l,MID,p),Access(pos->son[1],MID+1,R,MID+1,r,p));
			}
		}
		void Add(point p)
		{
			static int cnt=0;
			++cnt;
			Edit(root,TL,TR,cnt,p);
		}
		LL Answer(int l,int r,point p){return Access(root,TL,TR,l,r,p);}
	}seg;
}using namespace iSeg;


int main()
{
	char dkind;int n;
	get(n);while(!isalpha(dkind=getchar()));
	seg.Init(1,n);
	#define decode(x) ( x=(dkind=='E')?x:(x^(last & 0x7fffffff)) )
	LL last=0;
	for(int i=1;i<=n;i++)
	{
		char opt;int x,y,l,r;
		while(!isalpha(opt=getchar()));
		get(x),decode(x),get(y),decode(y);
		if(opt=='A') seg.Add(point(x,y));
		else
		{
			get(l),decode(l),get(r),decode(r);
			printf("%lld\n",last=seg.Answer(l,r,point(x,y)));
		}
	}
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */