集训队互测2016Unknown(UOJ191)

题目链接

前面部分和lzz的题解是一样的。

首先将输入点(x,y)变为(-y,x)然后，只需找一个向量与(-y,x)的点积最大，即找一个向量在(-y,x)上的投影最长。此时所有的点都是在x轴上方的，容易发现答案一定是在凸包上的，再继续观察，如果有一个点在凸包而不在上凸包上，那么它的右上角及左上角一定有一个点，因此这个点一定不是最优的，所以答案一定在上凸包上，且可以在上凸包上二分。

对于subtask5，使用线段树，每个节点存储这个区间的凸包，合并凸包的话可以将两个凸包上的点归并后线性做凸包。

从subtask5使用线段树维护静态凸包继续讨论线段树的做法，注意到所有操作只有在尾部加点删点，每次操作又要做到log^2n，显然不能每次操作后重构一路上的节点，那如果对于线段树上的节点[l,r]当n（序列长度）=r时就重做这个凸包呢？如果重复1,2操作这样就不行了。因此重点要考虑在什么时候重构一个节点的凸包。重构凸包的复杂度是O(len)的，所以可以当n>=r+len时重构这个凸包，这样下次再需要O(len)次撤回才能影响到这个凸包，因此这样重做凸包的次数是均摊O(1)的。查询时如果一个点的凸包没有做出来就要接着查询它的左右儿子，由于每一层只有最后一个点的凸包还没被做出，靠左的区间顶多再找一层，最右边的区间满了但是凸包没做出来，因此还要一直向右找O(logn)个节点(左边的已经做出来了)直到叶子，因此查询的总复杂度为O(log^2n)。

注意一下凸包上不能有三点共线，不然二分时可能会抛弃最优解。

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<cmath>

//#define P puts("lala")

#define cp cerr<<"lala"<<endl

#define pl puts("lala")

#define se second

#define fi first

#define ln putchar('\n')

#define mkp make_pair

#define pb push_back

using namespace std;

typedef pair<int,int> pii;

inline void read(int &re)

{

    char ch=getchar();int g=1;

    while(ch<'0'||ch>'9') {if(ch=='-') g=-1;ch=getchar();}

    re=0;

    while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+ch-48,ch=getchar();

    re*=g;

}

typedef long long ll;

inline void read(ll &re)

{

    char ch=getchar();ll g=1;

    while(ch<'0'||ch>'9') {if(ch=='-') g=-1;ch=getchar();}

    re=0;

    while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+ch-48,ch=getchar();

    re*=g;

}

const int N=300050;

const int mod=998244353;

struct point

{

    int x,y;

    point(int x=0,int y=0) : x(x),y(y) { }

};

inline bool operator < (point a,point b) {return a.x<b.x||(a.x==b.x&&a.y<b.y);}

inline bool operator == (point a,point b) {return a.x==b.x&&a.y==b.y;}

point operator + (point a,point b) {return point(a.x+b.x,a.y+b.y);}

point operator - (point a,point b) {return point(a.x-b.x,a.y-b.y);}

inline ll cross(point a,point b) {return (ll)a.x*b.y-(ll)a.y*b.x;}

inline ll dot(point a,point b) {return (ll)a.x*b.x+(ll)a.y*b.y;}

int n=0;

int tot=0;

vector<point>s[N<<2];

vector<point>c;

point p[N],poly[N];

vector<point> merge(vector<point> &a,vector<point> &b)

{

    c.clear();

    int num=0,i=0,j=0,siza=a.size(),sizb=b.size();

    while(i<siza&&j<sizb)

    {

        if(a[i]<b[j]) p[num++]=a[i],i++;

        else p[num++]=b[j],j++;

    }

    while(i<siza) p[num++]=a[i],i++;

    while(j<sizb) p[num++]=b[j],j++;

    int k=0;

    //>= !!! no three dot on a line

    for(i=0;i<num;++i)

    {

        while(k>1&&cross(p[i]-poly[k-2],poly[k-1]-poly[k-2])>=0) k--;

        poly[k++]=p[i];

    }

    int m=k;

    for(i=num-2;i>=0;--i)

    {

        while(k>m&&cross(p[i]-poly[k-2],poly[k-1]-poly[k-2])>=0) k--;

        poly[k++]=p[i];

    }

    for(i=k-1;i>=m;--i) c.pb(poly[i]);

    if(m-1>0) c.pb(poly[m-1]);

    return c;

}

ll query(int wh,point P)

{

    int l=0,r=s[wh].size()-1;

    if(s[wh].size()==1) return dot(s[wh][0],P);

    if(l==r) return max(dot(s[wh][0],P),dot(s[wh][1],P));

    while(l<r)

    {

        int mid=l+r>>1;

        if(dot(s[wh][mid],P)<dot(s[wh][mid+1],P)) l=mid+1;

        else r=mid;

    }

    return dot(s[wh][l],P);

}

point a[N];

int T,top=0;

void build(int o,int l,int r)

{

    if(l==r) {s[o].pb(a[l]);return ;}

    int mid=l+r>>1;

    build(o<<1,l,mid); build(o<<1|1,mid+1,r);

    s[o]=merge(s[o<<1],s[o<<1|1]);

}

void update(int o,int l,int r,int x,point P)

{

    if(l==r) {s[o].clear(); s[o].pb(P); return ;}

    int mid=l+r>>1;

    if(x<=mid) update(o<<1,l,mid,x,P);

    else update(o<<1|1,mid+1,r,x,P);

    if(top==r&&l!=1)

    {

        o--;

        s[o]=merge(s[o<<1],s[o<<1|1]);

    }

}

void del(int o,int l,int r,int x)

{

    if(l==r) {s[o].clear(); return ;}

    int mid=l+r>>1;

    if(x<=mid) del(o<<1,l,mid,x);

    else del(o<<1|1,mid+1,r,x);

    if(top<=r) s[o].clear();

}

ll qry(int o,int l,int r,int x,int y,point P)

{

    if(x<=l&&r<=y&&s[o].size()) return query(o,P);

    int mid=l+r>>1;

    ll maxn=-9e18;

    if(x<=mid) maxn=qry(o<<1,l,mid,x,y,P);

    if(y>mid) maxn=max(maxn,qry(o<<1|1,mid+1,r,x,y,P));

    return maxn;

}

void wj()

{

#ifndef ONLINE_JUDGE

    freopen("congroo.in","r",stdin);

    freopen("congroo.out","w",stdout);

#endif

}

int main()

{

    wj();int i,j,opt,tp;

    a[0]=point(0,0);

    read(tp);

    while(1)

    {

        read(T);

        if(!T) break;

        while((1<<tot)<T) tot++;

        tot=1<<tot;

        for(i=1;i<=(tot<<1);++i) s[i].clear();

        int ans=0; top=0;

        for(int cas=1;cas<=T;++cas)

        {

            read(opt);

            if(opt==1)

            {

                int x,y;read(x);read(y);

                top++;

                a[top]=point(x,y);

                update(1,1,tot,top,a[top]);

            }

            else if(opt==2)

            {

                a[top]=point(0,0);

                del(1,1,tot,top); top--;

            }

            else

            {

                int l,r,x,y;read(l);read(r);read(x);read(y);

                ll maxn=qry(1,1,tot,l,r,point(-y,x));

                //printf("%lld\n",maxn);

                ans^=(int)((maxn%mod+mod)%mod);

            }

        }

        printf("%d\n",ans);

    }

    return 0;

}

集训队互测2016Unknown(UOJ191)的相关教程结束。