Loj 6546 简单的数列题

Posted on | Views:

分块 + 斜率优化.

考虑分块,对于每一块维护块内的 $\max\lbrace a_i\cdot b_i\rbrace​$ ,以及加法标记 $tag​$ .

每次 $tag$ 被更新后,需要重新计算块内的 $\max\lbrace a_i\cdot b_i\rbrace$ .

此时每个位置实际的值是 $c_i=tag\cdot b_i+a_i\cdot b_i​$ ,要找出最大的 $c_i​$ .

这是个斜率优化的形式,写成 $-a_i\cdot b_i=tag\cdot b_i-c_i$ .

块内每个点横坐标为 $b_i$ ,纵坐标为 $-a_i\cdot b_i$ ,用一条斜率为 $tag$ 的直线去截这些点,需要最小化截距.

把它们按照 $b_i$ 从小到大排序,维护一个下凸壳,用斜率为 $tag$ 的直线去截它就可以得到答案.

由于 $tag$ 只会不断增大,每次被截到的点不可能向左移动,于是不需要在凸壳上二分,不断尝试将答案向右移即可.

对于边角部分,把块重构之后暴力询问答案.

交换操作容易处理,将影响到的两个块重构一下就可以了.

每次重构需要将该块重新按 $b$ 排序.

设块大小为 $B$ ,则复杂度为 $O(n\cdot(\frac n B+B\log B))$ ,取 $B=\sqrt \frac{n}{\log n} $ ,得到时间复杂度 $O(n\sqrt{n\log n})$ .

每次重构时最多只会有 $2$ 个元素的 $b$ 是无序的,若直接用归并排序重构,时间复杂度 $O(n\sqrt n)$ .

空间复杂度 $O(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
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
//%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=1e5+10,S=81,K=1267;
int n,m,B,a[MAXN],b[MAXN],bel[MAXN];
int lp[K],rp[K],tag[K],pos[K];
ll mx[K];
void pushdown(int x)
{
	if(tag[x])
	{
		for(int i=lp[x];i<=rp[x];++i)
			a[i]+=tag[x];
		tag[x]=0;
	}
}
struct v2
{
	ll x,y;
	v2(ll x=0,ll y=0):x(x),y(y) {}
	bool operator < (const v2 &rhs) const
	{
		return x==rhs.x?y<rhs.y:x<rhs.x;
	}
	v2 operator - (const v2 &rhs) const
	{
		return v2(x-rhs.x,y-rhs.y);
	}
	ll operator * (const v2 &rhs) const
	{
		return x*rhs.y-y*rhs.x;
	}
};
void ConvexHull(v2 *p,v2 *stk,int siz,int &tp,int &pos,ll &mx)
{
	tp=0;
	stk[++tp]=p[1];
	for(int i=2;i<=siz;++i)
	{
		if(p[i].x==p[i-1].x)
			continue;
		while(tp>=2 && (p[i]-stk[tp-1])*(stk[tp]-stk[tp-1])>=0)
			--tp;
		stk[++tp]=p[i];
	}
	pos=1;
	while(pos<tp && stk[pos].y>stk[pos+1].y)
		++pos;
	mx=-stk[pos].y;
}
int tp[K];
v2 p[K][S],stk[K][S];
void ReBuild(int k)
{
	pushdown(k);
	int siz=0;
	for(int i=lp[k];i<=rp[k];++i)
	{
		++siz;
		p[k][siz].x=b[i];
		p[k][siz].y=-1LL*a[i]*b[i];
	}
	sort(p[k]+1,p[k]+1+siz);
	ConvexHull(p[k],stk[k],siz,tp[k],pos[k],mx[k]);
}
ll calc(int k,v2 pt)
{
	return pt.y-pt.x*k;
}
bool check(int x,v2 A,v2 B)
{
	return calc(x,A)>calc(x,B);
}
void upd(int L,int R,int c)
{
	if(bel[L]==bel[R])
	{
		for(int i=L;i<=R;++i)
			a[i]+=c;
		ReBuild(bel[L]);
	}
	else
	{
		for(int i=L;i<=rp[bel[L]];++i)
			a[i]+=c;
		ReBuild(bel[L]);
		for(int i=bel[L]+1;i<=bel[R]-1;++i)
		{
			tag[i]+=c;
			while(pos[i]<tp[i] && check(tag[i],stk[i][pos[i]],stk[i][pos[i]+1]))
				++pos[i];
			mx[i]=-calc(tag[i],stk[i][pos[i]]);
		}
		for(int i=lp[bel[R]];i<=R;++i)
			a[i]+=c;
		ReBuild(bel[R]);
	}
}
void Swap(int x,int y)
{
	swap(b[x],b[y]);
	ReBuild(bel[x]),ReBuild(bel[y]);
}
ll query(int L,int R)
{
	ll ans=0;
	if(bel[L]==bel[R])
	{
		ReBuild(bel[L]);
		for(int i=L;i<=R;++i)
			ans=max(ans,1LL*a[i]*b[i]);
	}
	else
	{
		ReBuild(bel[L]);
		for(int i=L;i<=rp[bel[L]];++i)
			ans=max(ans,1LL*a[i]*b[i]);
		for(int i=bel[L]+1;i<=bel[R]-1;++i)
			ans=max(ans,mx[i]);
		ReBuild(bel[R]);
		for(int i=lp[bel[R]];i<=R;++i)
			ans=max(ans,1LL*a[i]*b[i]);
	}
	return ans;
}
int main()
{
	n=read(),m=read();
	B=sqrt(n)/4;
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		bel[i]=(i-1)/B+1;
		lp[bel[i]]=(bel[i]-1)*B+1;
		rp[bel[i]]=bel[i]*B;
	}
	for(int i=1;i<=n;++i)
		b[i]=read();
	rp[bel[n]]=n;
	for(int i=1;i<=bel[n];++i)
		ReBuild(i);
	for(int i=1;i<=m;++i)
	{
		int op=read(),x=read(),y=read();
		if(op==1)
			upd(x,y,read());
		else if(op==2)
			Swap(x,y);
		else
			printf("%lld\n",query(x,y));
	}
	return 0;
}