题目
BZOJ3533: [Sdoi2014]向量集
题解
转化一下式子发现可以求凸包（意会好像也可以）
线段树维护区间凸包，这个线段树主要是为了回答询问，因为每次修改都要暴力重构这个点维护的区间的凸包。暴力重构的时间复杂度是O(n)，所以如果像普通线段树那样的话稳T，观察到如果这个点维护的区间没满（有点还没加），一定没有用（不会被问到），所以我们可以选择在每个区间恰好变有用的时候暴力建凸壳，因为线段树一层是O(n)个节点，共O(logn)层，如果用归并排序实现对点的排序的话，总共时间复杂度只需要O(nlogn)。
第一次写凸包，终于知道了为什么必须写俩循环而不是把>=和<=换一换就能解决问题。
代码
//QWsin
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll INF=1ll<<60;int n;struct vc{int x,y;vc(const int x=0,const int y=0):x(x),y(y){}bool operator < (const vc &rhs)const{return x<rhs.x||(x==rhs.x&&y<rhs.y);}
};
vc operator - (const vc &a,const vc &b){
return vc(a.x-b.x,a.y-b.y); }
inline ll cross(const vc &a,const vc &b){
return 1ll*a.x*b.y-1ll*a.y*b.x;}
inline ll dot(const vc &a,const vc &b){
return 1ll*a.x*b.x+1ll*a.y*b.y;}#define mid ((l+r)>>1)
struct Node{vc *up,*dn,*x;//用vector也行不过感觉常数很大，用点常用的对于不定长数组省空间的黑科技就好int top1,top2;Node *lc,*rc;Node (){up=dn=x=NULL;lc=rc=NULL;top1=top2=0;}inline void UP(int l,int r){int len=r-l+1;up = new vc[len+1];dn = new vc[len+1];x = new vc[len+1];//注意这里要用多少开多少，保证一共的空间是O(nlogn)int pos=0;for(int pl=1,pr=1;pl+l-1<=mid||pr+mid<=r;){ if(pl+l>mid+1||(pr+mid<=r&&rc->x[pr] < lc->x[pl])) x[++pos]=rc->x[pr++];else x[++pos]=lc->x[pl++];}top1=0,top2=0;for(int i=1;i<=len;++i){while(top1>1 && cross(up[top1]-up[top1-1],x[i]-up[top1]) >=0) --top1;up[++top1]=x[i];}for(int i=len;i>=1;--i){ while(top2>1 && cross(dn[top2]-dn[top2-1],x[i]-dn[top2]) >=0) --top2;dn[++top2]=x[i]; }}}*root;ll check(const vc *p,int n,const vc &v)
{int l=1,r=n,mid1,mid2;ll val1,val2;while(r-l+1>3){mid1=(l+l+r)/3;mid2=(l+r+r)/3;val1=dot(p[mid1],v);val2=dot(p[mid2],v);if(val1 < val2) l=mid1;else r=mid2;}ll ret=-INF;for(int i=l;i<=r;++i) ret=max(ret,dot(p[i],v));return ret;
}void build(Node* &p,int l,int r)
{p=new Node(); if(l==r) return ;build(p->lc,l,mid);build(p->rc,mid+1,r);
}void updata(Node* p,int l,int r,int pos,vc val)
{if(l==r){p->up=new vc[2];p->up[1]=val;p->dn=new vc[2];p->dn[1]=val;p->x=new vc[2];p->x[1]=val;p->top1=p->top2=1;return ;}if(pos<=mid) updata(p->lc,l,mid,pos,val);else updata(p->rc,mid+1,r,pos,val);if(r==pos) p->UP(l,r);
}ll query(Node* p,int l,int r,const int &L,const int &R,const int &x,const int &y)
{if(L<=l&&r<=R) return (y>0?check(p->up,p->top1,vc(x,y)):check(p->dn,p->top2,vc(x,y)));ll ret=-INF;if(L<=mid) ret=max(ret,query(p->lc,l,mid,L,R,x,y));if(mid<R ) ret=max(ret,query(p->rc,mid+1,r,L,R,x,y));return ret;
}ll query(int x,int y,int l,int r){return query(root,1,n,l,r,x,y);
}ll lastans=0;
inline int f(int x){return x^(lastans & 0x7fffffff) ;
}char s[10],op[10];int main()
{scanf("%d%s",&n,s);build(root,1,n);int a,b,c,d,cnt=0;for(int i=1;i<=n;++i){scanf("%s",op);if(op[0]=='A'){scanf("%d%d",&a,&b);if(s[0]!='E') a=f(a),b=f(b);updata(root,1,n,++cnt,vc(a,b));}else{scanf("%d%d%d%d",&a,&b,&c,&d);if(s[0]!='E') {a=f(a);b=f(b);c=f(c);d=f(d);}lastans=query(a,b,c,d);printf("%lld\n",lastans);}}return 0;
}