「SDOI2014」向量集
维护一个向量集合, 在线支持以下操作:
A x y : 加入向量 \((x, y)\);
Q x y l r: 询问第 \(L\) 个到第 \(R\) 个加入的向量与向量 \((x, y)\) 的点积的最大值. 集合初始时为空.
对于所有的数据,\(1 \leq N \leq 4 \times 10^5\), 操作中的向量坐标满足 \(|x|,|y| \leq 10^8\), 询问满足 \(1 \leq L \leq R \leq T\), 其中 \(T\) 为已经加入的向量个数.
一眼上去, 线段树套 KD - 树???
然后觉得 4e5 根本跑不动, 就一直没写.
看了题解才知道自己还是对凸优化不够熟悉, 明明感觉可以凸优化, 但搞不清楚式子怎么化
一般的套路是, 对一个值询问一个集合, 找其中一个运算后得到最值之类的, 我们这时候把那个集合给弄成点集, 把询问搞成最大截距或者最大斜率, 就可以在凸包上三分了.
这个题询问点是 \((z,w)\), 即询问 \(ans=xz+yw\) 的最大值, 化简一下就成了
\[ y=-\frac{z}{w}x+\frac{ans}{w} \]
最大化截距就讨论一下 \(w\) 的正负, 决定在上 or 下凸包上三分就可以了.
然后我们需要支持动态插入凸包, 可以直接在线段树上模拟二进制分组, 每次给线段树的区间加点, 当某个区间加满了点, 就构建凸包 (没加满是不会被询问的)
复杂度 \(O(n\log^2 n)\),LOJ 上懒得卡了...
有个错误调了好久, 以前写凸包的时候没注意, 一定要以 \(y\) 作为第二关键字, 否则在最右边的 \(x\) 上可能出现问题.
- Code:
- #include <cstdio>
- #include <cctype>
- #include <vector>
- #include <algorithm>
- #define ll long long
- const int N=4e5+10;
- using std::max;
- int n,m,flag;
- template <class T>
- void read(T &x)
- {
- x=0;char c=getchar();bool f=0;
- while(!isdigit(c)) f=c=='-'?1:0,c=getchar();
- while(isdigit(c)) x=x*10+c-'0',c=getchar();
- x=f?-x:x;
- }
- inline int decode(int x,ll lastans){return flag?x^(lastans&0x7fffffff):x;}
- struct Point
- {
- ll x,y;
- Point(){}
- Point(ll X,ll Y){x=X,y=Y;}
- Point friend operator -(Point a,Point b){return Point(a.x-b.x,a.y-b.y);}
- bool friend operator <(Point a,Point b){return a.x==b.x?a.y<b.y:a.x<b.x;}
- };
- ll Cross(Point a,Point b){return a.x*b.y-a.y*b.x;}
- std::vector<Point> pot[N<<2],s[N<<2];
- int Endro[N<<2],endro;
- void ins(Point x,int id)
- {
- int tot=s[id].size()-1;
- while(tot>=endro&&Cross(s[id][tot]-s[id][tot-1],x-s[id][tot])<=0) --tot,s[id].pop_back();
- s[id].push_back(x);
- }
- void build(int id)
- {
- std::sort(pot[id].begin(),pot[id].end());
- endro=1;
- for(int i=0;i<pot[id].size();i++)
- ins(pot[id][i],id);
- endro=s[id].size();
- Endro[id]=endro-1;
- for(int i=pot[id].size()-2;~i;i--) ins(pot[id][i],id);
- }
- #define ls id<<1
- #define rs id<<1|1
- void change(int id,int l,int r,int p,Point ins)
- {
- pot[id].push_back(ins);
- if(s[id].empty()&&pot[id].size()==r+1-l) build(id);
- if(l==r) return;
- int mid=l+r>>1;
- if(p<=mid) change(ls,l,mid,p,ins);
- else change(rs,mid+1,r,p,ins);
- }
- ll cal(int x,int y,Point d)
- {
- return d.x*x+d.y*y;
- }
- ll yuu(int id,int x,int y)
- {
- int endro=s[id].size()-1;
- if(y==0) return max(s[id][0].x*x,s[id][Endro[id]].x*x);
- int l,r;
- if(y>0) l=Endro[id],r=endro;
- else l=0,r=Endro[id];
- while(l<r)
- {
- int mid=l+r>>1;
- if(cal(x,y,s[id][mid])<cal(x,y,s[id][mid+1])) l=mid+1;
- else r=mid;
- }
- return cal(x,y,s[id][l]);
- }
- ll query(int id,int L,int R,int l,int r,int x,int y)
- {
- if(l==L&&r==R) return yuu(id,x,y);
- int Mid=L+R>>1;
- if(r<=Mid) return query(ls,L,Mid,l,r,x,y);
- else if(l>Mid) return query(rs,Mid+1,R,l,r,x,y);
- else return max(query(ls,L,Mid,l,Mid,x,y),query(rs,Mid+1,R,Mid+1,r,x,y));
- }
- int main()
- {
- char op[10];read(n),scanf("%s",op);
- if(op[0]!='E') flag=1;
- ll las=0;
- for(int x,y,l,r,i=1;i<=n;i++)
- {
- scanf("%s",op);
- if(op[0]=='A')
- {
- read(x),read(y);
- x=decode(x,las),y=decode(y,las);
- change(1,1,n,++m,Point(x,y));
- }
- else
- {
- read(x),read(y),read(l),read(r);
- x=decode(x,las),y=decode(y,las);
- l=decode(l,las),r=decode(r,las);
- printf("%lld\n",las=query(1,1,n,l,r,x,y));
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2962536.html