题解 P3309 【[SDOI2014]向量集】

· · 题解

不失一般性设当前询问的y_0>0，那么\dfrac{ans}{y_0}=\max\{\dfrac{x_0}{y_0}\cdot x+y\}，然后这个东西和斜率优化长得一样，答案一定是在凸壳上的.

于是我们维护这个凸壳.因为有区间询问所以线段树维护每个区间的凸壳.具体地，插入的时候统计当前区间已经有多少个点，如果点数等于当前区间长度那么构造出这个区间的凸壳.询问的时候拆成\log个区间分别跑二分/三分即可.

求凸包这里使用按x坐标排序的那个算法.注意如果几个点的x相同那么要按y排序.

插入的时候每个区间只会被构建一次凸包，总复杂度O(n\log n)，排序用归并.

查询的时候拆成\log个区间，每个区间O(\log n)三分/二分，总复杂度O(n\log ^2 n)

使用vector可以很方便地在每个节点开一个栈，但是非常吃氧(不开O2会T最后一个点).可以不用stl，用一个大栈存下所有区间的凸包，对每个线段树节点存下它所在凸包的起止点即可.

这里当然还是用无脑的vector了233

这道题还告诉我们所有长成f[i]=\min\limits_{L(i)\leq j\leq R(i)}\{k(i)x(j)+F(j)\}+G(i)的dp都是可做的233

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N=2e6;
long long lastans;
struct Point{
    int x,y;
    bool operator <(const Point &a)const{return x!=a.x?x<a.x:y<a.y;}
    Point operator -(const Point &a)const{return (Point){x-a.x,y-a.y};}
    long long operator *(const Point &a)const{return 1ll*x*a.y-1ll*y*a.x;}
};
struct Node{vector<Point>st[2];}a[N];
int size[N],n;
char st[5];
long long calc(int rot,int x,int y)
{
    int o=0;
    if(y<0)x=-x,y=-y,o=1;
    int l=0,r=a[rot].st[o].size()-1;
//  cout<<rot<<" "<<l<<" "<<r<<endl;
    while(l<r)
    {
        int mid=(l+r)>>1;//cout<<l<<" "<<r<<" "<<mid<<endl;
        if(-1ll*x*(a[rot].st[o][mid+1].x-a[rot].st[o][mid].x)>=1ll*y*(a[rot].st[o][mid+1].y-a[rot].st[o][mid].y))r=mid;
        else l=mid+1;
    }
//  cout<<l<<endl;
    return 1ll*x*a[rot].st[o][l].x+1ll*y*a[rot].st[o][l].y;
}
long long query(int rot,int lt,int rt,int lq,int rq,int x,int y)
{
    if(lt>=lq&&rt<=rq)return calc(rot,x,y);
    int mid=(lt+rt)>>1;
    if(rq<=mid)return query(rot<<1,lt,mid,lq,rq,x,y);
    else if(lq>mid)return query(rot<<1|1,mid+1,rt,lq,rq,x,y);
    else return max(query(rot<<1,lt,mid,lq,mid,x,y),query(rot<<1|1,mid+1,rt,mid+1,rq,x,y));
}
void build(int rot,int len)
{
    for(int o=0;o<=1;o++)
    {
        vector<Point>tmp;tmp.clear();
        vector<Point>::iterator i=a[rot<<1].st[o].begin(),j=a[rot<<1|1].st[o].begin();
        for(;i!=a[rot<<1].st[o].end()||j!=a[rot<<1|1].st[o].end();)
            if(i==a[rot<<1].st[o].end()||(j!=a[rot<<1|1].st[o].end()&&*j<*i))tmp.push_back(*j++);
            else tmp.push_back(*i++);
        int top=0;
        for(vector<Point>::iterator i=tmp.begin();i!=tmp.end();++i)
        {
            while(top>1&&((a[rot].st[o][top-1]-a[rot].st[o][top-2])*(*i-a[rot].st[o][top-1]))>=0)--top,a[rot].st[o].pop_back();
            a[rot].st[o].push_back(*i);++top;
        }
    }
}
void update(int rot,int lt,int rt,int q,int x,int y)
{
    if(lt==rt){a[rot].st[0].push_back((Point){x,y}),a[rot].st[1].push_back((Point){-x,-y}),++size[rot];return;}
    int mid=(lt+rt)>>1;
    if(q<=mid)update(rot<<1,lt,mid,q,x,y);
    else update(rot<<1|1,mid+1,rt,q,x,y);
    ++size[rot];if(size[rot]==rt-lt+1)build(rot,rt-lt+1);
}
void deco(int &x)
{
    x^=(lastans&0x7fffffff);
}
void print(int rot,int lt,int rt)
{
    printf("%d %d %d\n",rot,lt,rt);
    int mid=(lt+rt)>>1;
    if(lt!=rt)print(rot<<1,lt,mid),print(rot<<1|1,mid+1,rt);
}
int main()
{
    int enc=0;
    scanf("%d%s",&n,st+1);if(st[1]!='E')enc=1;
//  cout<<enc<<endl;
//  freopen("cswa.txt","w",stdout);
    int nn=0;//print(1,1,n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",st+1);
        if(st[1]=='Q')
        {
            int l,r,x,y;
            scanf("%d%d%d%d",&x,&y,&l,&r);
            if(enc)deco(x),deco(y),deco(l),deco(r);
//          cout<<x<<" "<<y<<" "<<l<<" "<<r<<endl;
            printf("%lld\n",lastans=query(1,1,n,l,r,x,y));
        }
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(enc)deco(x),deco(y);
//          cout<<x<<" "<<y<<endl;
            update(1,1,n,++nn,x,y);
        }
//      print(1,1,n);
    }
}