BZOJ 1568 BlueMary开公司

发表于 | 更新于

Link

Solution

超神线段树，又叫超哥线段树，又叫李超线段树 在线段树的节点上存储直线，当添加新的直线的时候按照交点讨论选择将一条线压到子区间 首先，如果一条直线被另一条完全覆盖，可以直接把被覆盖的扔掉(但其实不需要单独讨论) 然后对于两条直线，设在点LL处取值较大的直线为l1l_1，另一条为l2l_2。 如果两线段的交点在区间中点左侧，把l1l_1压到左半区间 否则将l2l_2压到右半区间 查询的时候，在覆盖该点的所有线段树节点存储的直线中取一个最大值即可。

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
//Code by Lucida
#include<bits/stdtr1c++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define gets(x) scanf("%s",x)
#define getd(x) scanf("%lf",&x)
#define put64(x) printf("%lld",x)
typedef long long ll;
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;}
using std::max;
using std::swap;

const int MAXN=1e5+11,DAY=50000;

struct Line
{
	double k,b;
	Line(){k=b=0;}
	Line(double k,double b):k(k),b(b){}
	double operator ()(int x){return k*x+b;}
};

namespace _ChaoSeg_
{
	const int SIZE=MAXN<<2;
	
	struct Node
	{
		Node *son[2];
		Line line;
		Node(){son[0]=son[1]=0;}
		void *operator new(size_t);
	}*Me=(Node*)malloc(SIZE*sizeof(Node));
	void *Node::operator new(size_t){return Me++;}
	struct ChaoSeg
	{
		int L,R;Node *root;
		ChaoSeg(int,int);
		void Build(Node*&,int,int);
		void Append(Node*,Line,int,int);
		void Insert(Node*,int,int,int,int,Line);
		double Query(Node*,int,int,int);
		
		void Insert(int l,int r,Line ln){Insert(root,L,R,l,r,ln);}
		double Query(int x){return Query(root,L,R,x);}
	};
	ChaoSeg::ChaoSeg(int L,int R):L(L),R(R){Build(root,L,R);}
	void ChaoSeg::Build(Node *&pos,int L,int R)
	{
		pos=new Node;
		if(L!=R)
		{
			int Mid=(L+R)>>1;
			Build(pos->son[0],L,Mid);
			Build(pos->son[1],Mid+1,R);
		}
	}
	void ChaoSeg::Insert(Node* pos,int L,int R,int l,int r,Line ln)
	{
		if(L==l && R==r) Append(pos,ln,L,R);
		else
		{
			int Mid=(L+R)>>1;
			if(r<=Mid) Insert(pos->son[0],L,Mid,l,r,ln);
			else if(Mid+1<=l) Insert(pos->son[1],Mid+1,R,l,r,ln);
			else Insert(pos->son[0],L,Mid,l,Mid,ln),Insert(pos->son[1],Mid+1,R,Mid+1,r,ln);
		}
	}
	void ChaoSeg::Append(Node *pos,Line ln,int L,int R)
	{
		if(!pos) return;
		Line hl=ln,hr=pos->line;
		if(hl(L)<hr(L)) swap(hl,hr);
		double x=-(hl.b-hr.b)/(hl.k-hr.k);//-..
		if(!(L<=x && x<=R)){pos->line=hl;return;}
		int Mid=(L+R)>>1;
		if(x<=Mid) pos->line=hr,Append(pos->son[0],hl,L,Mid);
		else pos->line=hl,Append(pos->son[1],hr,Mid+1,R);
	}
	double ChaoSeg::Query(Node *pos,int L,int R,int goal)
	{
		if(L==R) return pos->line(goal);
		else
		{
			int Mid=(L+R)>>1;double res=pos->line(goal);
			if(goal<=Mid) return max(res,Query(pos->son[0],L,Mid,goal));
			else return max(res,Query(pos->son[1],Mid+1,R,goal));
		}
	}
}using _ChaoSeg_::ChaoSeg;
int main()
{
	int m;get(m);
	ChaoSeg seg(1,DAY);
	for(int i=1;i<=m;++i)
	{
		char opt[15];gets(opt);
		int day;ll Ans;double k,b;
		switch(opt[0])
		{
			case 'P':
				getd(b),getd(k);
				seg.Insert(1,DAY,Line(k,b-k));
				break;
			case 'Q':
				get(day);
				Ans=(ll)seg.Query(day)/100;
				put64(Ans),putchar('\n');
				break;
		}
	}
	return 0;
}