uoj88 Robot

发表于 | 更新于

Link

Solution

离线，对时间离散化 然后把时间当作横坐标，维护最大最小值 用超神线段树即可

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
//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 get64(x) scanf("%lld",&x)
#define put64(x) printf("%lld",x)
namespace IO
{
	template <class T>
	void get(T &x)
	{
		static int f;static char ch;
		for(f=1,ch=0;ch<'0' || ch>'9';ch=getchar()) if(ch=='-') f=-1;
		for(x=0;'0'<=ch && ch<='9';ch=getchar()) (x*=10)+=ch-'0';
		x*=f;
	}
}using IO::get;
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::swap;
using std::greater;
using std::less;
using std::unique;
using std::max;
using std::copy;
using std::sort;
const int MAXN=1e5+11,MAXQ=6e5+11;
const double inf=1e100;
struct Opt
{
	int l,r;
	bool query;
	int id,v;
}op[MAXQ+MAXN];int opc;
struct Line
{
	ll k,b;
	Line(){}Line(ll k,ll b):k(k),b(b){}
	ll operator ()(int x){return k*x+b;}
}position[MAXN];
int a[(MAXQ+MAXN)<<1];
namespace _SegTree_
{
	const int SIZE=MAXQ<<1<<2<<1;	
	struct Node
	{
		Node *son[2];Line ln;
		Node(){son[0]=son[1]=0;}
		void *operator new(size_t);
		void Append(int,int,Line);
	}*Me=(Node*)malloc(SIZE*sizeof(Node)),*Pool=Me;
	void *Node::operator new(size_t){return Me++;}
	#define template template <class Compare>
	template struct SegTree
	{
		int L,R;Node *root;
		Compare cmp;
		SegTree(int,int);
		void Build(Node*&,int,int);
		void Insert(Node*,int,int,int,int,Line);
		ll Query(Node*,int,int,int);
		void Append(Node*,int,int,Line);
		void Insert(int l,int r,Line ln)
		{
			if(l<=r)
			{
				l=lower_bound(a+L,a+R+1,l,less<int>())-(a+L-1);
				r=lower_bound(a+L,a+R+1,r,less<int>())-(a+L-1);//l?..
				Insert(root,L,R,l,r,ln);
			}
		}
		ll Query(int x)
		{
			int pos=lower_bound(a+L,a+R+1,x,less<int>())-(a+L-1);
			return Query(root,L,R,pos);
		}
	};
	template SegTree<Compare>::SegTree(int L,int R):L(L),R(R){Build(root,L,R);}
	template void SegTree<Compare>::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);
		}
	}
	template void SegTree<Compare>::Append(Node *pos,int L,int R,Line newln)
	{
		if(!pos) return;
		Line hl=pos->ln,hr=newln;
		if(!cmp(hl(a[L]),hr(a[L]))) swap(hl,hr);
		int Mid=(L+R)>>1;double x=(hr.k==hl.k)?inf:-(1.0*hr.b-hl.b)/(1.0*hr.k-hl.k);
		if(!(a[L]<=x && x<=a[R])) {pos->ln=hl;return;}
		if(x<=a[Mid]) Append(pos->son[0],L,Mid,hl),pos->ln=hr;
		else Append(pos->son[1],Mid+1,R,hr),pos->ln=hl;
	}
	template void SegTree<Compare>::Insert(Node* pos,int L,int R,int l,int r,Line newln)
	{
		if(L==l && R==r) Append(pos,L,R,newln);
		else
		{
			int Mid=(L+R)>>1;
			if(r<=Mid) Insert(pos->son[0],L,Mid,l,r,newln);
			else if(Mid+1<=l) Insert(pos->son[1],Mid+1,R,l,r,newln);
			else Insert(pos->son[0],L,Mid,l,Mid,newln),Insert(pos->son[1],Mid+1,R,Mid+1,r,newln);
		}
	}
	template ll SegTree<Compare>::Query(Node *pos,int L,int R,int goal)
	{
		if(L==R) return pos->ln(a[goal]);
		else
		{
			int Mid=(L+R)>>1;ll temp,res=pos->ln(a[goal]);
			if(goal<=Mid) temp=Query(pos->son[0],L,Mid,goal);
			else temp=Query(pos->son[1],Mid+1,R,goal);
			return cmp(res,temp)?res:temp;
		}
	}
	#undef template
}using _SegTree_::SegTree;
int main()
{
	static int pre[MAXN];
	int n,Q;get(n),get(Q);
	for(int i=1;i<=n;++i)
	{
		++opc;
		get(position[i].b),position[i].k=0;
		op[opc].v=0;op[opc].l=0;op[opc].id=i;
		pre[i]=opc;
	}
	for(int i=1;i<=Q;++i)
	{
		assert(op[i].l>=op[i-1].l);

		char opt[15];++opc;
		//op[opc]=op[opc-1];
		get(op[opc].l);
		gets(opt);
		if(opt[0]=='c')
		{
			get(op[opc].id),get(op[opc].v);
			if(pre[op[opc].id])
			{
				op[pre[op[opc].id]].r=op[opc].l-1;
				pre[op[opc].id]=opc;
			}
			op[opc].query=0;
		}
		else
			op[opc].query=1;
	}
	
	int nc=0;
	for(int i=1;i<=opc;++i)
	{
		a[++nc]=op[i].l;
		a[++nc]=op[i].r;
	}
	sort(a+1,a+1+nc);
	nc=unique(a+1,a+1+nc)-a-1;
	for(int i=1;i<=n;++i) op[pre[i]].r=a[nc];
	SegTree<greater<ll> > segmx(1,nc);
	SegTree<less<ll> > segmn(1,nc);
	for(int i=1;i<=opc;++i)
	{
		if(!op[i].query)
		{
			position[op[i].id]=Line(op[i].v,position[op[i].id](op[i].l)-(ll)op[i].l*op[i].v);
			segmx.Insert(op[i].l,op[i].r,position[op[i].id]);
			segmn.Insert(op[i].l,op[i].r,position[op[i].id]);
		}
	}
	for(int i=1;i<=opc;++i)
	{
		if(op[i].query)
		{
			ll Ans=max(segmx.Query(op[i].l),-segmn.Query(op[i].l));
			put64(Ans),putchar('\n');
		}
	}
	return 0;
}