题目大意

维护一个序列 支持以下操作:

  1. 序列末尾插入一个向量$(x,y)$
  2. 序列末尾删除一个向量
  3. 询问区间 $[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 分治一下应该就可以(当然直接暴力线段树维护也是资瓷的)

Last modification:April 22nd, 2020 at 11:31 pm
如果觉得我的文章对你有用,请随意赞赏