临汾花果街网站建设,微信跳转链接生成器免费,直播视频网站,做公司网站的专业公司深圳正题
题目链接:https://www.luogu.com.cn/problem/P3309 题目大意 nnn个操作
在序列末尾加入一个向量(x,y)(x,y)(x,y)询问加入的第l∼rl\sim rl∼r个向量中的一个向量和(x,y)(x,y)(x,y)的点积最大值
强制在线#xff0c;点积的定义为x1x2y1y2x_1x_2y_1y_2x1x2y1y2 …正题
题目链接:https://www.luogu.com.cn/problem/P3309 题目大意
nnn个操作
在序列末尾加入一个向量(x,y)(x,y)(x,y)询问加入的第l∼rl\sim rl∼r个向量中的一个向量和(x,y)(x,y)(x,y)的点积最大值
强制在线点积的定义为x1x2y1y2x_1x_2y_1y_2x1x2y1y2 解题思路
如果对于一个(x,y)(x,y)(x,y)对于两个(x1,y1)(x_1,y_1)(x1,y1)和(x2,y2)(x_2,y_2)(x2,y2)如果后者更大那么有 x2xy2yx1xy1y⇒yx≤x2−x1y2−y1x_2xy_2yx_1xy_1y\Rightarrow \frac{y}{x}\leq \frac{x_2-x_1}{y_2-y_1}x2xy2yx1xy1y⇒xy≤y2−y1x2−x1 好像和斜率有关可以维护凸壳来做因为yyy可能是负数如果是负数的时候就要求的是下凸壳了所以两个凸壳都要维护。
因为强制在线所以上不了传统艺能CDQ\text{CDQ}CDQ
那怎么动态维护区间凸壳平衡树支持动态插入但不支持区间问题。所以考虑线段树因为一个位置修改了之后就不会再修改而且是从左往右加的可以利用这个性质。
每次我们修改一个位置后如果一个区间[L,R][L,R][L,R]的节点内已经插入了R−L1R-L1R−L1个向量也就是都插完了的话就直接把它的两个儿子的凸壳合并起来。
然后询问的时候分成lognlog\ nlog n个区间询问的答案取最大值就好了。
合并凸壳的是用归并排序的话时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define ll long long
using namespace std;
struct point{ll x,y;point(ll xx0,ll yy0){xxx;yyy;return;}
}z;
point operator(point x,point y)
{return point(x.xy.x,x.yy.y);}
point operator-(point x,point y)
{return point(x.x-y.x,x.y-y.y);}
ll operator^(point x,point y)
{return x.x*y.y-x.y*y.x;}
ll operator*(point x,point y)
{return x.x*y.xx.y*y.y;}
bool operator(point x,point y)
{return (x.xy.x)?x.yy.y:x.xy.x;}const ll N4e510;
char pe[3];
ll n,num,siz[N2];
vectorpoint v[N2][2],tmp;void Make(ll x){ll lsx*2,rsx*21;for(ll k0;k2;k){ll i0,j0,l1v[ls][k].size()-1,l2v[rs][k].size()-1;tmp.clear();while(il1||jl2){if(il1||(jl2v[rs][k][j]v[ls][k][i]))tmp.push_back(v[rs][k][j]),j;else tmp.push_back(v[ls][k][i]),i;}ll cnt0;for(ll i0;itmp.size();i){while(cnt1((v[x][k][cnt-1]-v[x][k][cnt-2])^(tmp[i]-v[x][k][cnt-1]))0)v[x][k].pop_back(),cnt--;v[x][k].push_back(tmp[i]);cnt;}}return;
}
ll Calc(ll x,point p){ll f0;if(p.y0)pz-p,f^1;ll l0,rv[x][f].size()-2;while(lr){ll mid(lr)1;point tmpv[x][f][mid1]-v[x][f][mid];tmp.x*-1;if(p.x*tmp.xp.y*tmp.y)rmid-1;else lmid1;}return p*v[x][f][l];
}
void Change(ll x,ll L,ll R,ll pos,point p){if(LR){v[x][0].push_back(p);v[x][1].push_back(z-p);return;}ll mid(LR)1;siz[x];if(posmid)Change(x*2,L,mid,pos,p);else Change(x*21,mid1,R,pos,p);if(siz[x]R-L1)Make(x);
}
ll Ask(ll x,ll L,ll R,ll l,ll r,point p){if(LlRr)return Calc(x,p);ll mid(LR)1;if(rmid)return Ask(x*2,L,mid,l,r,p);if(lmid)return Ask(x*21,mid1,R,l,r,p);return max(Ask(x*2,L,mid,l,mid,p),Ask(x*21,mid1,R,mid1,r,p));
}
void dc(ll x,ll lastans) {if(pe[0]E)return;xx^(lastans0x7fffffff);return;
}
signed main()
{scanf(%lld%s,n,pe);ll last0;for(ll i1;in;i){char op[3];ll x,y,l,r;scanf(%s%lld%lld,op,x,y);dc(x,last);dc(y,last);if(op[0]A){num;Change(1,1,n,num,point(x,y));}else{scanf(%lld%lld,l,r);dc(l,last);dc(r,last);printf(%lld\n,lastAsk(1,1,n,l,r,point(x,y)));}}return 0;
}
