【BZOJ4311】向量（线段树分治，李超树）

【BZOJ4311】向量（线段树分治，李超树）

题面

🔗

你要维护一个向量集合，支持以下操作：

1. 插入一个向量 ( x , y ) (x,y) (x,y)
2. 删除插入的第 i i i 个向量
3. 查询当前集合与 ( x , y ) (x,y) (x,y) 点积的最大值是多少。如果当前是空集输出 0 0 0.

Input

第一行输入一个整数 n n n ，表示操作个数

接下来 n n n 行，每行先是一个整数 t t t 表示类型，如果 t = 1 t=1 t=1，输入向量 ( x , y ) (x,y) (x,y) ；如果 t = 2 t=2 t=2 ，输入 i d id id 表示删除第 i d id id 个向量；否则输入 ( x , y ) (x,y) (x,y) ，查询与向量 ( x , y ) (x,y) (x,y) 点积最大值是多少。

保证一个向量只会被删除一次，不会删没有插入过的向量

Output

对于每条 t = 3 t=3 t=3 的询问，输出一个答案

Sample Input

5
1 3 3
1 1 4
3 3 3
2 1
3 3 3

Sample Output

18
15

Hint

n < = 200000 , 1 < = x , y < = 1 0 6 n<=200000,1<=x,y<=10^6 n<=200000,1<=x,y<=106

题解

首先，两个向量相乘
( x , y ) ⋅ ( x i , y i ) = x x i + y y i = y ⋅ ( x y x i + y i ) (x,y)cdot (x_i,y_i)=xx_i+yy_i=ycdot (frac{x}{y}x_i+y_i) (x,y)⋅(xi​,yi​)=xxi​+yyi​=y⋅(yx​xi​+yi​)

我们令 f i ( x ) = x i x + y i f_i(x)=x_ix+y_i fi​(x)=xi​x+yi​ ，那么就等于 y ⋅ f i ( x y ) ycdot f_i(frac{x}{y}) y⋅fi​(yx​) 。

于是我们求最大值就是求这些 f i f_i fi​ 形成的下凸包，然后查询函数值。

维护凸包方便添加不方便删除，于是我们通过线段树分治将操作全部变成添加，然后就可以用李超线段树维护下凸包了。

时间复杂度 O ( n log ⁡ 2 n ) O(nlog^2 n) O(nlog2n) 。

还有另一种巧妙的 O ( n log ⁡ n ) O(nlog n) O(nlogn) 方法，也是线段树分治。

向量点乘的最大值，就是要求投影最大，也就是凸多边形在该向量方向上的最远点。我们把所有操作和询问的向量都按照极角排序，在按序插入线段树，于是维护凸包和查询的复杂度都去掉了一个 log ⁡ log log 。这样的代码真的是太██好打了。

CODE

为了挑战自己，我打算用第一种方法。

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 200005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
int xchar() {static const int maxn = 1000000;static char b[maxn];static int pos = 0,len = 0;if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);if(pos == len) return -1;return b[pos ++];
}
//#define getchar() xchar()
LL read() {LL f = 1,x = 0;int s = getchar();while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
void putnum(LL x) {if(!x) {putchar('0');return ;}if(x<0) putchar('-'),x = -x;return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}int n,m,s,o,k;
pair<DB,int> b[MAXN];
DB to[MAXN];
struct it{DB a,b;it(){a=0;b=-1e18;}it(DB A,DB B){a=A;b=B;}DB F(DB x) {return a*x+b;}
}tre[MAXN*64];
int ls[MAXN*64],rs[MAXN*64],cnt;
int addtree(int a,int al,int ar,it y) {if(!a) {tre[++ cnt] = y;ls[cnt] = rs[cnt] = 0;return cnt;}tre[++ cnt] = tre[a]; ls[cnt] = ls[a]; rs[cnt] = rs[a];a = cnt; DB l = to[al],r = to[ar];if(tre[a].F(l) <= y.F(l) && tre[a].F(r) <= y.F(r)) return tre[a]=y,a;if(tre[a].F(l) >= y.F(l) && tre[a].F(r) >= y.F(r)) return a;int md = (al + ar) >> 1;if(tre[a].F(to[md]) < y.F(to[md])) swap(tre[a],y);if(tre[a].F(l) < y.F(l)) ls[a] = addtree(ls[a],al,md,y);if(tre[a].F(r) < y.F(r)) rs[a] = addtree(rs[a],md+1,ar,y);return a;
}
LL findtree(int a,int x,int al,int ar,it y) {if(!a || al > x || ar < x) return -1e18;LL res = tre[a].a*y.a + tre[a].b*y.b;if(al == ar) return res;int md = (al + ar) >> 1;res = max(res,max(findtree(ls[a],x,al,md,y),findtree(rs[a],x,md+1,ar,y)));return res;
}
int ti[MAXN];
int op[MAXN],ad[MAXN];
LL as[MAXN];
it vc[MAXN];
vector<it> bu[MAXN<<2];
int M;
void maketree(int n) {M=1; while(M<n+2) M<<=1;
}
void addvc(int l,int r,it y) {if(l > r) return ;for(int s = M+l-1,t = M+r+1;(s>>1)^(t>>1);s >>= 1,t >>= 1) {if(!(s&1)) bu[s^1].push_back(y);if(t & 1) bu[t^1].push_back(y);}return ;
}
void solve(int s,int rt) {int cnc = cnt;for(int i = 0;i < (int)bu[s].size();i ++) {rt = addtree(rt,1,m,bu[s][i]);}if(s >= M) {if(op[s-M] == 3) {as[s-M] = findtree(rt,ad[s-M],1,m,vc[s-M]);}}else {solve(s<<1,rt);solve(s<<1|1,rt);}cnt = cnc;return ;
}
int main() {n = read();maketree(n);int cn = 0;for(int i = 1;i <= n;i ++) {op[i] = read();if(op[i] == 1) {vc[i].a = read();vc[i].b = read();ad[i] = ++ cn; ti[cn] = i;}else if(op[i] == 2) {s = read();addvc(ti[s],i-1,vc[ti[s]]);ad[ti[s]] = 0;}else {vc[i].a = read();vc[i].b = read();b[++ m] = {vc[i].a/vc[i].b,i};}}sort(b + 1,b + 1 + m);for(int i = 1;i <= m;i ++) to[i] = b[i].FI,ad[b[i].SE] = i;for(int i = 1;i <= n;i ++) {if(op[i] == 1 && ad[i]) {addvc(i,n,vc[i]);}}solve(1,0);for(int i = 1;i <= n;i ++) {if(op[i] == 3) {AIput(max(0ll,as[i]),'n');}}return 0;
}