题目大意
维护一个序列 支持以下操作：
- 序列末尾插入一个向量$(x,y)$
- 序列末尾删除一个向量
- 询问区间 $[l,r]$ 中和向量 $(u,v)$ 叉积的最大值（设 $(x,y) \in [l,r]$,要求 $(u,v)\times(x,y)$ 最大）
$n \leq 5\times 10^5$
题解
看到叉积 先想到斜率优化。
给出 $(u,v)$，要求最大化 $uy-vx$。
设 $b=uy-vx$ 变形得 $y=\frac{vx+b}{u}$
容易看出需要维护一个斜率递减的凸壳。
基于二进制分组的做法
做法一
如果没有删除操作 就是SDOI2014 向量集。
如果还是直接莽的话 在一个块的边界一直插入删除就可以让每次操作都变成 $O(n)$。
那么我们考虑我们让每个点在它后面那个点被填满的时候重建。长度为 $2^k$ 的块这次至少需要经过 $O(2^k)$ 才能重构 复杂度就正确了。时间复杂度 $O(nlog^2n)$
#include<bits/stdc++.h>
#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 3e5 + 5;
const int ha = 998244353;
struct Point{
int x,y;
Point(int x=0,int y=0) : x(x),y(y) {}
Point operator + (const Point &t) const {
return Point(x+t.x,y+t.y);
}
Point operator - (const Point &t) const{
return Point(x-t.x,y-t.y);
}
LL operator * (const Point &t) const {
return 1ll*x*t.y-1ll*y*t.x;
}
bool operator < (const Point &t) const {
return x==t.x ? y < t.y : x < t.x;
}
};
struct Node{
std::vector<Point> a;
inline void insert(const Point &x){
while(a.size() >= 2 && (x-a[a.size()-2])*(a[a.size()-1]-a[a.size()-2]) <= 0) a.pop_back();
a.pb(x);
}
friend Node operator + (const Node &a,const Node &b){
Node res;int t1 = 0,t2 = 0;
while(t1 < a.a.size() && t2 < b.a.size()){
if(a.a[t1] < b.a[t2]) res.insert(a.a[t1++]);
else res.insert(b.a[t2++]);
}
while(t1 < a.a.size()) res.insert(a.a[t1++]);
while(t2 < b.a.size()) res.insert(b.a[t2++]);
return res;
}
inline LL query(const Point &x){
int l = 0,r = (int)a.size()-2;LL ans = x*a[(int)a.size()-1];
while(l <= r){
int mid = (l + r) >> 1;
LL t1 = x*a[mid],t2 = x*a[mid+1];
ans = std::max(ans,std::max(t1,t2));
if(t1 < t2) l = mid+1;
else r = mid-1;
}
return ans;
}
}sm[MAXN<<2];
#define lc ((x)<<1)
#define rc ((x)<<1|1)
bool vis[MAXN<<2];// 是否已经build了
int lst[64];// 最前一个满了没有 build 的
inline void build(int x,int l,int r){
sm[x].a.clear();vis[x] = 0;
if(l == r) return;
int mid = (l + r) >> 1;
build(lc,l,mid);build(rc,mid+1,r);
}
inline void pushup(int x){
vis[x] = 1;sm[x] = sm[lc]+sm[rc];
}
inline void insert(int x,int l,int r,int p,const Point &t,int dep){
if(r == p){
int t = lst[dep];
if(t) pushup(t);
lst[dep] = l==r?0:x;
}
if(l == r) {sm[x].a.pb(t);return;}
int mid = (l + r) >> 1;
if(p <= mid) insert(lc,l,mid,p,t,dep+1);
else insert(rc,mid+1,r,p,t,dep+1);
}
inline void del(int x,int l,int r,int p,int dep){
sm[x].a.clear();vis[x] = 0;
if(lst[dep] == x) lst[dep] = 0;
if(l == r) return;
int mid = (l + r) >> 1;
if(p <= mid) del(lc,l,mid,p,dep+1);
else del(rc,mid+1,r,p,dep+1);
}
inline LL query(int x,int l,int r,int L,int R,Point t){
if(l == L && r == R && (vis[x] || l==r)) {return sm[x].query(t);}
int mid = (l + r) >> 1;
if(R <= mid) return query(lc,l,mid,L,R,t);
if(L > mid) return query(rc,mid+1,r,L,R,t);
return std::max(query(lc,l,mid,L,mid,t),query(rc,mid+1,r,mid+1,R,t));
}
int n;
inline void Solve(){
build(1,1,n);int sz = 0;LL ans = 0;
CLR(lst,0);
FOR(i,1,n){
int opt;scanf("%d",&opt);
if(opt == 1){
int x,y;scanf("%d%d",&x,&y);
insert(1,1,n,++sz,Point(x,y),1);
}
if(opt == 2){
del(1,1,n,sz--,1);
}
if(opt == 3){
int l,r,x,y;scanf("%d%d%d%d",&l,&r,&x,&y);
LL t = query(1,1,n,l,r,Point(x,y));
while(t < 0) t += ha;
t %= ha;
ans ^= t;
}
}
printf("%lld\n",ans);
}
int main(){
scanf("%*d");
while(~scanf("%d",&n) && n) Solve();
return 0;
}
做法二
我们二进制分组的时候容易被插入删除这种操作欺骗。我们用类似 Treap 的方法给每一个点一个随机权值。如果比上一个块的最小值小就合并。根据 Treap 的复杂度证明应该只有大概 log 块 复杂度也是对的。。。
基于点分治的做法
但这个只能离线。
我们考虑建出版本树：每个点插入就在当前点下面新加一个儿子节点 删除就跳回自己的父亲。这样就变成了每个点到根的路径上的凸包。
然后就是这个题：「NOI2014」购票。点分治后每次枚举一个点 先处理靠近根的连通块的答案 然后按照深度排个序 cdq 分治一下应该就可以（当然直接暴力线段树维护也是资瓷的）
