P3309[SDOI2014]向量集

传送门

达成成就&＃xff1a;一人独霸三页提交

自己写的莫名其妙MLE死都不知道怎么回事&＃xff0c;照着题解打一直RE一个点最后发现竟然是凸包上一个点求错了……四个半小时就一直用来调代码了……

那么我们只要维护好这个凸壳&＃xff0c;因为这是一个凸函数&＃xff0c;所以只要在上面三分找最值即可

于是现在我们需要维护一个资瓷插入的凸壳。考虑线段树&＃xff0c;我们发现每一次在线段树上询问的区间必然都是已经把点插满了的。那么我们可以考虑线段树上每一个节点内的所有元素都插入完之后&＃xff0c;再构建凸壳&＃xff0c;那么显然每个节点只会被构建一次凸包&＃xff0c;所以复杂度是\(O(nlog^2n)\)

然后注意一个细节……因为我们维护好的凸包要便于分成上下凸壳&＃xff0c;所以凸包的起点应该是\(x\)坐标最小的&＃xff0c;这样才满足它左右两边分别是上凸壳和下凸壳……我按照以前的写法找\(y\)坐标最小的当起点然后就没有然后了……

//minamoto
#include
#define fp(i,a,b) for(register int i&＃61;a,I&＃61;b&＃43;1;i#define fd(i,a,b) for(register int i&＃61;a,I&＃61;b-1;i>I;--i)
#define ll long long
#define inf 1e18
using namespace std;
templateinline bool cmax(T&a,const T&b){return aint flag&＃61;0,all;ll lasans&＃61;0;
int read(){int res,f&＃61;1;char ch;while((ch&＃61;getchar())>&＃39;9&＃39;||ch<&＃39;0&＃39;)(ch&＃61;&＃61;&＃39;-&＃39;)&&(f&＃61;-1);for(res&＃61;ch-&＃39;0&＃39;;(ch&＃61;getchar())>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;;res&＃61;res*10&＃43;ch-&＃39;0&＃39;);res*&＃61;f;if(flag)res^&＃61;(lasans&0x7fffffff);return res;
}
char sr[1<<21],z[20];int C&＃61;-1,Z&＃61;0;
inline void Ot(){fwrite(sr,1,C&＃43;1,stdout),C&＃61;-1;}
void print(ll x){if(C>1<<20)Ot();if(x<0)sr[&＃43;&＃43;C]&＃61;&＃39;-&＃39;,x&＃61;-x;while(z[&＃43;&＃43;Z]&＃61;x%10&＃43;48,x/&＃61;10);while(sr[&＃43;&＃43;C]&＃61;z[Z],--Z);sr[&＃43;&＃43;C]&＃61;&＃39;\n&＃39;;
}
const int N&＃61;4e5&＃43;5;
struct node{int x,y;}b[N],st[N];
struct seg{int l,r,pos,sz;seg *ch[2];vectormp;
}pool[N<<2],*rt;
inline node operator -(node a,node b){return (node){a.x-b.x,a.y-b.y};}
inline ll operator *(node a,node b){return 1ll*a.x*b.y-1ll*b.x*a.y;}
inline ll dot(node a,node b){return 1ll*a.x*b.x&＃43;1ll*a.y*b.y;}
inline bool operator <(node a,node b){a&＃61;a-st[1],b&＃61;b-st[1];return a*b&＃61;&＃61;0?1ll*a.x*a.x&＃43;1ll*a.y*a.y<1ll*b.x*b.x&＃43;1ll*b.y*b.y:a*b>0;
}
void graham(seg *p){int top&＃61;1,sz&＃61;p->r-p->l&＃43;1,k&＃61;1;fp(i,1,sz)b[i]&＃61;p->mp[i-1];fp(i,2,sz)if(b[i].x1&&(b[i]-st[top-1])*(st[top]-st[top-1])>&＃61;0)--top;st[&＃43;&＃43;top]&＃61;b[i];}st[&＃43;&＃43;top]&＃61;b[1];p->sz&＃61;top;vector().swap(p->mp);
// p->mp.clear();fp(i,1,top)p->mp.push_back(st[i]);fp(i,1,top-1)if(st[i&＃43;1].x<&＃61;st[i].x){p->pos&＃61;i-1;break;}
}
ll calc(seg *p,node q){int l,r,m1,m2;ll ans&＃61;-inf;q.y>0?(l&＃61;p->pos,r&＃61;p->sz-1):(l&＃61;0,r&＃61;p->pos);while(r-l>&＃61;3){m1&＃61;l&＃43;(r-l)/3,m2&＃61;r-(r-l)/3;dot(q,p->mp[m1])>dot(q,p->mp[m2])?r&＃61;m2:l&＃61;m1;}fp(i,l,r)cmax(ans,dot(q,p->mp[i]));return ans;
}
void ins(seg *p,int pos,node x){p->mp.push_back(x);if(pos&＃61;&＃61;p->r)graham(p);if(p->l&＃61;&＃61;p->r)return;int mid&＃61;(p->l&＃43;p->r)>>1;pos<&＃61;mid?ins(p->ch[0],pos,x):ins(p->ch[1],pos,x);
}
ll query(seg *p,int l,int r,node x){if(l<&＃61;p->l&&r>&＃61;p->r)return calc(p,x);int mid&＃61;(p->l&＃43;p->r)>>1;ll res&＃61;-inf;if(l<&＃61;mid)cmax(res,query(p->ch[0],l,r,x));if(r>mid)cmax(res,query(p->ch[1],l,r,x));return res;
}
void build(seg *p,int l,int r){p->l&＃61;l,p->r&＃61;r;if(l&＃61;&＃61;r)return;int mid&＃61;(l&＃43;r)>>1;build(p->ch[0]&＃61;pool&＃43; &＃43;&＃43;all,l,mid),build(p->ch[1]&＃61;pool&＃43; &＃43;&＃43;all,mid&＃43;1,r);
}
int main(){
// freopen("testdata.in","r",stdin);int n,l,r,tot&＃61;0;char s[10];node x;n&＃61;read(),scanf("%s",s),flag&＃61;s[0]!&＃61;&＃39;E&＃39;;build(rt&＃61;pool&＃43; &＃43;&＃43;all,1,n);while(n--){scanf("%s",s),x.x&＃61;read(),x.y&＃61;read();if(s[0]&＃61;&＃61;&＃39;Q&＃39;)l&＃61;read(),r&＃61;read(),print(lasans&＃61;query(rt,l,r,x));else ins(rt,&＃43;&＃43;tot,x);}return Ot(),0;
}